Content deleted Content added
Jochen Burghardt (talk | contribs) found a reference; fixing exm. description; elaborating on place in Chomsky hierarchy |
Jochen Burghardt (talk | contribs) →top: quote the only Thm. of H+U 1979 on couter automata |
||
Line 3: | Line 3: | ||
For example, the language <math>\{ a^nb^n : n \in \mathbb{N} \}</math> is a non-regular language accepted by a counter automaton: It can use the symbol <math>A</math> to count the number of <math>a</math>s in a given input string <math>x</math> (writing an <math>A</math> for each <math>a</math> in <math>x</math>) and deleting an <math>A</math> for each <math>b</math> in <math>x</math>). |
For example, the language <math>\{ a^nb^n : n \in \mathbb{N} \}</math> is a non-regular language accepted by a counter automaton: It can use the symbol <math>A</math> to count the number of <math>a</math>s in a given input string <math>x</math> (writing an <math>A</math> for each <math>a</math> in <math>x</math>) and deleting an <math>A</math> for each <math>b</math> in <math>x</math>). |
||
A two-counter automaton, that is, a [[Multitape Turing machine#Two-stack Turing machine|two-stack Turing machine]] with a two-symbol alphabet, can simulate an arbitrary [[Turing machine]].<ref name="Hopcroft.Ullman.1979"/>{{rp|172}} |
|||
==Notes== |
==Notes== |
Revision as of 20:36, 19 January 2017
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 ).
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#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