Counter automaton

Diagram of a counter automaton. Each cell of its stack either contains an "A" or a space symbol.

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, $A$ and the initial symbol in $\mathrm{\Gamma }$, 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 $\{a^n{b}^n:n\in \mathbb{\mathbb{N}}\}$ is a non-regular language accepted by a counter automaton: It can use the symbol $A$ to count the number of $a$s in a given input string $x$ (writing an $A$ for each $a$ in $x$), after that, it can delete an $A$ for each $b$ in $x$.

A two-counter automaton, that is, a two-stack Turing machine with a two-symbol alphabet, can simulate an arbitrary Turing machine.