m Robot - Moving category Computational models to Models of computation per CFD at Wikipedia:Categories for discussion/Log/2011 February 19. |
m Dating maintenance tags: {{Mergeto}} |
||
(22 intermediate revisions by 10 users not shown) | |||
Line 1: | Line 1: | ||
{{mergeto|Counter machine|date=January 2024}}[[File:Pushdown-overview.svg|thumb|Diagram of a counter automaton. Each cell of its stack either contains an "''A''" or a space symbol.]] |
|||
{{multiple issues |
|||
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 | url-access=registration | url=https://archive.org/details/introductiontoau00hopc }}</ref>{{rp|171}} |
|||
|orphan=November 2008 |
|||
|unreferenced=November 2008 |
|||
|expert=December 2010 |
|||
}} |
|||
In [[computer science]], a '''counter automaton''' is a [[Pushdown automaton]] with only two symbols, ''A'' and the initial symbol in <math>\Gamma\,</math> (the finite set of stack symbols). This class of automata can recognize a subset of Context free languages, for instance the language: |
|||
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 name="Hopcroft.Motwani.Ullman.2003">{{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 | <!---almost unknown:---isbn=0321210298---> isbn=0-201-44124-1 | year=2003 }}</ref>{{rp|351}} |
|||
<math> \{\ a^nb^n : n \in \mathbb{N} \} </math> |
|||
==Properties== |
|||
To accept the above language, let ''x'' be a word on the form above. The automaton can use the symbol A to count the number of ''a'''s in ''x'' (writing an ''A'' for each ''A'' in ''x'') and deleting an ''A'' for each ''b'' in ''x''. |
|||
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 subset of the [[deterministic context free language]]s.<ref name="Hopcroft.Motwani.Ullman.2003"/>{{rp|352}} |
|||
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>. |
|||
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== |
|||
{{reflist|group=note}} |
|||
==References== |
|||
{{reflist}} |
|||
{{Formal languages and grammars}} |
|||
{{DEFAULTSORT:Counter Automaton}} |
{{DEFAULTSORT:Counter Automaton}} |
||
[[Category:Automata |
[[Category:Automata (computation)]] |
||
[[Category:Models of computation]] |
[[Category:Models of computation]] |
||
{{Comp-sci-stub}} |
Latest revision as of 08:37, 8 January 2024
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 subset of the deterministic context free languages.[2]: 352
For example, the language is a non-regular[note 2] 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.
- ^ by the pumping lemma for regular languages
References
- ^ a b John E. Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X.
- ^ a b 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 0-201-44124-1.