Content deleted Content added
m Stub-sorting. You can help! Edit tags. |
m Robot - Moving category Computational models to Models of computation per CFD at Wikipedia:Categories for discussion/Log/2011 February 19. |
||
Line 12: | Line 12: | ||
{{DEFAULTSORT:Counter Automaton}} |
{{DEFAULTSORT:Counter Automaton}} |
||
[[Category:Automata theory]] |
[[Category:Automata theory]] |
||
[[Category: |
[[Category:Models of computation]] |
||
{{Comp-sci-stub}} |
{{Comp-sci-stub}} |
Revision as of 17:22, 28 February 2011
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.