A deterministic queue automaton (DQA) is like a PDA except the stack is replaced

Question

A deterministic queue automaton (DQA) is like a PDA except the stack is replaced by a queue. A queue is a tape allowing symbols to be written (push) on the left-end and read (pull) on the right-end.

Actually I've proved that a 2-tape Turing Machine can simulate the DQA. Now I'm proving the DQA can simulate Turing Machine TM. Let the queue store all the input and the right-end symbol is the one being read. Suppose a is the right-end symbol in the queue.

For the transition ?(q,a)=(r,b,L) in TM, it's easy to simulate. Just pull a and push b. Now the right-end symbol would be the symbol on the left of a. It's like move the head in TM to the left.

My problem is I cannot find a way to simulate the transition ?(q,a)=(r,b,R). Since the symbol on the right of a is actually the left-end symbol, how can I let this symbol move to the right-end? I spend several hours on this and I think answers on Internet are not very clear. Could anyone give me some hint?

Explanation / Answer

How do you simulate the tape? Place end/beginning marker in the queue, and see how you handle "move past end" (basically, replace "end of tape" by "space, end of tape" and redo the move you were trying to do).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.