Content deleted Content added
m Robot - Moving category Automata theory to Category:Automata (computation) per CFD at Wikipedia:Categories for discussion/Log/2015 October 22. |
fixing basics of typography and link |
||
Line 3: | Line 3: | ||
{{expert-subject|date=December 2010}} |
{{expert-subject|date=December 2010}} |
||
}} |
}} |
||
In [[computer science]], a '''counter automaton''' is a [[ |
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. This class of automata can recognize a subset of [[context-free languages]], for instance the language |
||
<math> \{\ a^nb^n : n \in \mathbb{N} \} </math> |
<math> \{\ a^nb^n : n \in \mathbb{N} \}. </math> |
||
To accept the above language, let |
To accept the above language, let <math>x</math> be a word of the form above. The automaton can use the symbol <math>A</math> to count the number of <math>a</math>s in <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>. |
||
{{DEFAULTSORT:Counter Automaton}} |
{{DEFAULTSORT:Counter Automaton}} |
Revision as of 00:53, 16 February 2016
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. This class of automata can recognize a subset of context-free languages, for instance the language
To accept the above language, let be a word of the form above. The automaton can use the symbol to count the number of s in (writing an for each in ) and deleting an for each in .