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^nb^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 as 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 Tuesday, February 16, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.