Content deleted Content added
Converted {{Multiple issues}} to new format to fix expert parameter & general fixes using AWB (8853) |
David Eppstein (talk | contribs) {{comp-sci-theory-stub}} |
||
Line 15: | Line 15: | ||
{{ |
{{comp-sci-theory-stub}} |
Revision as of 05:14, 4 October 2013
In computer science, a counter automaton is a Pushdown automaton with only two symbols, A and the initial symbol in (the finite set of stack symbols). This class of automata can recognize a subset of Context free languages, for instance the language:
To accept the above language, let x be a word on 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.