Counter automaton

In computer science, a counter automaton is a pushdown automaton with only two symbols, $A$ and the initial symbol in $\Gamma$ , the finite set of stack symbols. This class of automata can recognize a subset of context-free languages, for instance the language

$\{\ a^{n}b^{n}:n\in \mathbb {N} \}.$

To accept the above language, let $x$ be a word of the form above. The automaton can use the symbol $A$ to count the number of $a$ s in $x$ (writing an $A$ for each $a$ in $x$ ) and deleting an $A$ for each $b$ in $x$ .

This article is issued from Wikipedia - version of the 2/16/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.