Content deleted Content added
Jochen Burghardt (talk | contribs) →top: factor-out "Properties" section; language inclusions are proper |
Jochen Burghardt (talk | contribs) →Properties: insert "the" |
||
Line 6: | Line 6: | ||
==Properties== |
==Properties== |
||
The class of counter automata can recognize a proper superset of [[regular language|regular]]{{#tag:ref|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''.|group=note}} and a proper subset of [[context-free languages]].{{#tag:ref|Any pushdown automaton can at best accept a context-free language.<ref name="Hopcroft.Ullman.1979"/>{{rp|116}} There is some{{vague|reason=Give an example.}} context-free language that cannot be accepted by a counter automaton.{{cn}}|group=note}} |
The class of counter automata can recognize a proper superset of the [[regular language|regular]]{{#tag:ref|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''.|group=note}} and a proper subset of the [[context-free languages]].{{#tag:ref|Any pushdown automaton can at best accept a context-free language.<ref name="Hopcroft.Ullman.1979"/>{{rp|116}} There is some{{vague|reason=Give an example.}} context-free language that cannot be accepted by a counter automaton.{{cn}}|group=note}} |
||
For example, the language <math>\{ a^nb^n : n \in \mathbb{N} \}</math> is a non-regular<ref group=note>by the [[pumping lemma for regular languages#Use of the lemma|pumping lemma for regular languages]]</ref> 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>), after that, it can delete 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<ref group=note>by the [[pumping lemma for regular languages#Use of the lemma|pumping lemma for regular languages]]</ref> 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>), after that, it can delete an <math>A</math> for each <math>b</math> in <math>x</math>. |
Revision as of 09:22, 20 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
Properties
The class of counter automata can recognize a proper superset of the regular[note 1] and a proper subset of the context-free languages.[note 2]
For example, the language is a non-regular[note 3] 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 .
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 There is some[vague] context-free language that cannot be accepted by a counter automaton.[citation needed]
- ^ by the pumping lemma for regular languages
References