Saturday 21 December 2013

Sipser Queue automaton vs Turing machine

Sipser 3.14

A queue automaton is like a push-down automaton except that the stack is replaced
by a queue. A queue is a tape allowing symbols to be written only on the left-hand
end and read only at the right-hand end. Each write operation (we'll call it a push)
adds a symbol to the left-hand end of the queue and each read operation (we'll
call it a pull) reads and removes a symbol at the right-hand end. As with a PDA,
the input is placed on a separate read-only input tape, and the head on the input
tape can move only from left to right. The input tape contains a cell with a blank
symbol following the input, so that the end of the input can be detected. A queue
automaton accepts its input by entering a special accept state at any time. Show that
a language can be recognized by a deterministic queue automaton iff the language
is Turing-recognizable.


Solution:
Turing machine can simulate a Queue Automaton easily. Consider whole tape as queue.
Pop operation of queue: alter a symbol and move to right. If more than one symbols are to be pushed
then do it by shifting the contents right and insert symbols. Once you hit end of tape, go to leftmost symbol of tape.

Now simulating Turing machine in a Queue automata.
Insert a left end marker say # first to queue. Then push all the symbols of tape in queue and finally a blank symbol. We are pushing symbols to the left and reading(popping) from right.
When ever this blank symbol is read and overwritten by some other symbol, push a blank symbol to queue before pushing overwritten symbol. For example : ABCDEF_ was the configuration of queue and T.M. write a G on place of _ . Then new configuration is G_ABCDEF.
Whenever a symbol is read and pushed back to queue, you push a symbol which will tell queue that next symbol to be read is actually last symbol read. e.g. -  
ABCDEF
F is read and overwritten by symbol say 'f' then insert last symbol read marker ( | ) before you push f.
f|ABCDE
Now I am reading symbol E and moving to left on T.M. tape then we will have to push 'e' on behalf of E and this is new 'last symbol read' . so new configuration should be e|f|ABCD . Now we have to remove marker before 'f' keeping in mind that next symbol to read is 'D'. Now roll whole queue. Insert $ i.e. next symbol to read marker.
D$e|f|ABC
CD$e|f|AB    rolled once.
roll until you get first '|' on rightmost of the queue.
ABCD$e|f|
remove this marker '|'.
ABCD$e|f
now roll until we reach to $
e|fABCD$
remove $.
e|fABCD

If T.M. wants to move to last symbol read. then roll until do e| and roll until first | is exposed to right side like below
e|f|ABCD
ABCDe|f|
remove rightmost |
ABCDe|f
now you are reading f as desired.




1 comment:

  1. How about two consecutive right shift operations?
    I think you can't find the right position of the iterator.

    ReplyDelete