Content deleted Content added
84.234.240.151 (talk) stubified, improved language |
Rich Farmbrough (talk | contribs) m Date maintenance tags and general fixes: build 586: using AWB |
||
Line 1: | Line 1: | ||
{{orphan|date=November 2008}} |
{{orphan|date=November 2008}} |
||
{{unreferenced|date=November 2008}} |
{{unreferenced|date=November 2008}} |
||
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: |
||
<math> \{\ a^nb^n : n \in \mathbb{N} \} </math> |
<math> \{\ a^nb^n : n \in \mathbb{N} \} </math> |
||
Line 7: | Line 7: | ||
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''. |
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''. |
||
{{DEFAULTSORT:Counter Automaton}} |
|||
⚫ | |||
[[Category:Automata theory]] |
[[Category:Automata theory]] |
||
[[Category:Computational models]] |
[[Category:Computational models]] |
||
⚫ |
Revision as of 01:27, 17 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.