||This article needs attention from an expert on the subject. (December 2010)|
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.: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.:351
For example, the language is a non-regular[note 2] 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 .
- John E. Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X.
- 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.
|P ≟ NP||This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.|