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.
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.
Properties
The class of counter automata can recognize a proper superset of the regular and a subset of the deterministic context free languages.
For example, the language is a non-regular 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.
Notes
References
Automata (computation) Models of computation