Queue automaton
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A queue machine, queue automaton, or pullup automaton is a finite-state machine with the ability to store and retrieve data from an infinite-memory queue. Its design is similar to a pushdown automaton but differs by replacing the stack with this queue. A queue machine is a model of computation equivalent to a Turing machine, and therefore it can process the same class of formal languages.
A queue machine, queue automaton, or pullup automaton is a finite-state machine with the ability to store and retrieve data from an infinite-memory queue. Its design is similar to a pushdown automaton but differs by replacing the stack with this queue. A queue machine is a model of computation equivalent to a Turing machine, and therefore it can process the same class of formal languages. M = (Q, \Sigma, \Gamma, \$, s, \delta) where \,Q is a finite set of states; \,\Sigma \subset \Gamma is the finite set of the input alphabet; \,\Gamma is the finite queue alphabet; \,\$ \in \Gamma \setminus \Sigma is the initial queue symbol; \,s \in Q is the start state; \,\delta : Q \times \Gamma \rightarrow Q \times \Gamma^* is the transition function. A machine configuration is an ordered pair of its state and queue contents \,(q,\gamma)\in Q\times\Gamma^* , where \,\Gamma^* denotes the Kleene closure of \,\Gamma . The starting configuration on an input string \,x is defined as \,(s,x\$) , and the transition \rightarrow_M^1 from one configuration to the next is defined as: \,(p,A\alpha) \rightarrow_M^1 (q,\alpha\gamma) where A is a symbol from the queue alphabet, \alpha is a sequence of queue symbols ( \alpha \in \Gamma^* ), and (q, \gamma) = \delta(p, A) . Note the "first-in-first-out" property of the queue in the relation. The machine accepts a string \,x\in\Sigma^* if after a finite number of transitions the starting configuration evolves to exhaust the string (reaching the null string \,\epsilon ), or otherwise stated, if \,(s,x\$)\rightarrow_M^*(q,\epsilon).
Text derived from https://en.wikipedia.org/w/index.php?oldid=1374353780 under CC BY-SA 4.0; modifications have been made.