Jochen Burghardt (talk | contribs) equivalent def.n from Hopcroft.Motwani.Ullman.2003 |
Jochen Burghardt (talk | contribs) →top: ISBN |
||
Line 3: | Line 3: | ||
In [[computer science]], more particular in the theory of [[formal language]]s, a '''counter automaton''', or '''counter machine''', 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}} |
In [[computer science]], more particular in the theory of [[formal language]]s, a '''counter automaton''', or '''counter machine''', 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}} |
||
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.<ref>{{cite book | author=John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation | location=Upper Saddle River/NJ | publisher=Addison Wesley | year=2003 }}</ref>{{rp|351}} |
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.<ref>{{cite book | author=John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation | location=Upper Saddle River/NJ | publisher=Addison Wesley | isbn=0321210298 | year=2003 }}</ref>{{rp|351}} |
||
==Properties== |
==Properties== |
Revision as of 09:39, 20 January 2017
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.[1]: 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.[2]: 351
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
- ^ a b c 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 0321210298.