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 subset of the deterministic context free languages.^{[2]:352}

A two-counter automaton, that is, a two-stack Turing machine with a two-symbol alphabet, can simulate an arbitrary Turing machine.^{[1]:172}

References

- ^ Jump up to:
^{a}^{b}*John E. Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X.* - ^ Jump up to:
^{a}^{b}*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.*