Content deleted Content added
134.82.133.52 (talk) No edit summary |
84.234.240.151 (talk) stubified, improved language |
||
Line 1: | Line 1: | ||
{{orphan|date=November 2008}} |
{{orphan|date=November 2008}} |
||
{{unreferenced|date=November 2008}} |
{{unreferenced|date=November 2008}} |
||
In [[computer science]], |
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: |
||
<math> \{\ a^nb^n : n \in \mathbb{N} \} </math> |
<math> \{\ a^nb^n : n \in \mathbb{N} \} </math> |
||
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''. |
|||
{{stub}} |
|||
[[Category:Automata theory]] |
[[Category:Automata theory]] |
Revision as of 20:59, 15 December 2010
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.