Content deleted Content added
Rich Farmbrough (talk | contribs) m Date maintenance tags and general fixes: build 586: using AWB |
m Stub-sorting. You can help! Edit tags. |
||
Line 1: | Line 1: | ||
{{multiple issues |
|||
⚫ | |||
|orphan=November 2008 |
|||
⚫ | |||
|expert=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 11: | Line 14: | ||
[[Category:Computational models]] |
[[Category:Computational models]] |
||
⚫ | |||
⚫ |
Revision as of 01:44, 18 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.