In computer science, a counter automaton is a pushdown automaton with only two symbols, and the initial symbol in , the finite set of stack symbols.[1]: 171 This class of automata can recognize a superset of regular[note 1] and a subset of context-free languages.[note 2]
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 ) and deleting an for each in ).
Notes
- ^ Every regular language L is accepted by some finite automaton F (see Regular language#Equivalent formalisms). Enriching F with a two-symbol stack which is ignored by F’s control makes it a counter automaton accepting L.
- ^ Any pushdown automaton can at best accept a context-free language.[1]: 116
References