Counter automaton
 | It has been suggested that this article be merged into Counter machine. (Discuss) Proposed since January 2024. |
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, [math]\displaystyle{ A }[/math] and the initial symbol in [math]\displaystyle{ \Gamma }[/math], 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
For example, the language [math]\displaystyle{ \{ a^nb^n : n \in \mathbb{N} \} }[/math] is a non-regular[note 2] language accepted by a counter automaton: It can use the symbol [math]\displaystyle{ A }[/math] to count the number of [math]\displaystyle{ a }[/math]s in a given input string [math]\displaystyle{ x }[/math] (writing an [math]\displaystyle{ A }[/math] for each [math]\displaystyle{ a }[/math] in [math]\displaystyle{ x }[/math]), after that, it can delete an [math]\displaystyle{ A }[/math] for each [math]\displaystyle{ b }[/math] in [math]\displaystyle{ x }[/math].
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). Enriching F with a two-symbol stack which is ignored by F’s control makes it a counter automaton accepting L.
- ↑ by the pumping lemma for regular languages
References
- ↑ 1.0 1.1 John E. Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X. https://archive.org/details/introductiontoau00hopc.
- ↑ 2.0 2.1 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.
 |  |
