Content deleted Content added
Jochen Burghardt (talk | contribs) →top: quote the only Thm. of H+U 1979 on couter automata |
Jochen Burghardt (talk | contribs) →top: abuse general PDA image, as its stack happens to contain only an "A" |
||
Line 1: | Line 1: | ||
{{expert-subject|date=December 2010}} |
{{expert-subject|date=December 2010}} |
||
[[File:Pushdown-overview.svg|thumb|Diagram of a counter automaton. Each cell of its stack either contains an "''A''" or a space symbol.]] |
|||
In [[computer science]], a '''counter automaton''' is a [[pushdown automaton]] with only two symbols, <math>A</math> and the initial symbol in <math>\Gamma</math>, the finite set of stack symbols.<ref name="Hopcroft.Ullman.1979">{{cite book | isbn=0-201-02988-X | author=John E. Hopcroft and Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation | location=Reading/MA | publisher=Addison-Wesley | year=1979 }}</ref>{{rp|171}} This class of automata can recognize a 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 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}}|group=note}} |
In [[computer science]], a '''counter automaton''' is a [[pushdown automaton]] with only two symbols, <math>A</math> and the initial symbol in <math>\Gamma</math>, the finite set of stack symbols.<ref name="Hopcroft.Ullman.1979">{{cite book | isbn=0-201-02988-X | author=John E. Hopcroft and Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation | location=Reading/MA | publisher=Addison-Wesley | year=1979 }}</ref>{{rp|171}} This class of automata can recognize a 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 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}}|group=note}} |
||
Revision as of 20:41, 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