Counter automaton
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