In computer science, more particular in the theory of formal languages, a counter automaton, or counter machine, is a pushdown automaton with only two symbols, and the initial symbol in , the finite set of stack symbols.[1]: 171
Equivalently, a counter automaton is a nondeterministic finite automaton with an additional memory cell that can hold one nonnegative integer number (of unlimited size), which can be incremented, decremented, and tested for being zero.[2]: 351
Properties
The class of counter automata can recognize a proper superset of the regular[note 1] and a proper subset of the context-free languages.[note 2]
For example, the language is a non-regular[note 3] language accepted by a counter automaton: It can use the symbol to count the number of s in a given input string (writing an for each in ), after that, it can delete an for each in .
A two-counter automaton, that is, a two-stack Turing machine with a two-symbol alphabet, can simulate an arbitrary Turing machine.[1]: 172
Notes
- ^ Every regular language L is accepted by some finite automaton F (see Regular language#Equivalent formalisms). Enriching F with a two-symbol stack which is ignored by F’s control makes it a counter automaton accepting L.
- ^ Any pushdown automaton can at best accept a context-free language.[1]: 116 There is some[vague] context-free language that cannot be accepted by a counter automaton.[citation needed]
- ^ by the pumping lemma for regular languages
References
- ^ a b c John E. Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X.
- ^ John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman (2003). Introduction to Automata Theory, Languages, and Computation. Upper Saddle River/NJ: Addison Wesley. ISBN 0-201-44124-1.