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.

Sipser 3.9 Let a k-PDA be a pushdown automaton that has k stacks. Thus a 0-PDA is an NFA and 1-PDA is a conventional PDA. You already know that 1-PDAs are more powerful(recognize a larger class of languages) than 0-PDAs.

3.9 Let a k-PDA be a pushdown automaton that has k stacks. Thus a 0-PDA is an NFA and 1-PDA is a conventional PDA. You already know that 1-PDAs are more powerful(recognize a larger class of languages) than 0-PDAs.

a. Show that 2-PDAs are more powerful than 1-PDAs.

Solution:  Clearly, 2 PDA can do any thing which 1-PDA can. Now I will give a language which is accepted by 2-PDA not 1-PDA.  { w |w ∈ aⁿbⁿcⁿ } is one I want to consider. This is not A CFL and so not accepted by a 1-PDA. But if there are 2 stacks then do as follow:
Read input a^*b^*c^*
1. Initially PDA is in state q_accept. If an 'a' is read then push it in stack 1 and go to q₁. Else if read a 'b'        or 'c', go to q_reject and stay there for rest of input.
2.Being in state q₁ and reading input 'a', push it inside stack 1. Go to state q₂ if a 'b' is read and pop one 'a' from stack 1 and also push a 'b' on stack 2. If a 'c' is read then go to q_reject and stay there for rest of input.
3. Being in state q2 and reading input 'b', pop 'a' and push 'b' in stack 2. If a 'c' is read then go to state q3 and pop 'b' from stack 2. If no a is remaining on stack with 'b' still in hand, go to q_reject. Reject if 'a' is read again.
4. Being in state q3 and reading input 'c', pop 'b' from stack 2. Reject if 'a' or 'b' is read.
5. Accept if both of the stacks are empty otherwise reject.






b. Show that 3-PDAs are not more powerful than 2-PDAs.


Solution: 3-PDAs can do whatever 2-PDAs can do. With a 2-PDA, I can simulate a Turing Machine so anything solvable can be done by 2-PDAs as well.
                       
1. Put a input tape in stack 2 such that its left end is on top. Well if some one objects that input is read from left and so left most will be at bottom of stack, then I will suggest to put whole string in stack 1. And pop from stack 1, push the popped symbol into stack 2.  Finally we will get what we require.
2. The symbol at top of stack 2 is the currant symbol, TM is reading.
3. Suppose current symbol to be read is 'a' and TM will write here a 'b' and moves left, then we will pop 'a' from stack 2 and push 'b' into stack and further pop a symbol from stack1 to push it into stack 2.
4. If machine have made a right move then we would have poped 'a' from stack 2 and push 'b' in stack1.