Content deleted Content added
No edit summary |
Converted {{Multiple issues}} to new format to fix expert parameter & general fixes using AWB (8853) |
||
Line 1: | Line 1: | ||
{{multiple issues |
{{multiple issues| |
||
{{orphan|date=November 2008}} |
|||
{{unreferenced|date=November 2008}} |
|||
{{expert-subject|date=December 2010}} |
|||
}} |
}} |
||
In [[computer science]], a '''counter automaton''' is a [[Pushdown automaton]] with only two symbols, ''A'' and the initial symbol in <math>\Gamma\,</math> (the finite set of stack symbols). This class of automata can recognize a subset of Context free languages, for instance the language: |
In [[computer science]], a '''counter automaton''' is a [[Pushdown automaton]] with only two symbols, ''A'' and the initial symbol in <math>\Gamma\,</math> (the finite set of stack symbols). This class of automata can recognize a subset of Context free languages, for instance the language: |
||
Line 13: | Line 13: | ||
[[Category:Automata theory]] |
[[Category:Automata theory]] |
||
[[Category:Models of computation]] |
[[Category:Models of computation]] |
||
{{Comp-sci-stub}} |
{{Comp-sci-stub}} |
Revision as of 17:50, 6 March 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.