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.

Sipser 2.45 Let A = {wtwR | w,t ∈ {0,1}* and |w| = |t|}. Prove that A is not context free language.

2.45 Let A = {wtw^R | w,t ∈ {0,1}* and |w| = |t|}. Prove that A is not context free language.

Solution:
Consider a string 1^2p(01)^p1^2p, where p is the pumping length. If you pump up only in leftmost 1^2p then number of 1's will be not equal to rightmost 1^2p. Similarly if pumped from leftmost 1^2p.
If we pump up somewhere in (01)^p, then we must have to consider (2p+1)st element from left and right in w and w^R but (2p+1)st from left will be a 0 and and (2p+1)st from right it will be a 1.
If I pump across boundary 1^2p(01)^p such that v is in 1^2p and y is in (01)^p. In this case pump up twice, we will see that (2p+2)nd symbol from left is 1 and from right is 0. 

Sipser 2.44 If A and B are languages, define A ◊ B = {xy | x ∈ A and y ∈ B and |x| = |y|}. Show that if A abd B are regular languages then A ◊ B is a CFL.

Sipser 2.44 If A and B are languages, define A ◊ B = {xy | x ∈ A and y ∈ B and |x| = |y|}. Show that if A abd B are regular languages then A ◊ B is a CFL.

Solution:

Consider M1 and M2 be DFAs for A and B respectively. Now we will construct PDA P for A ◊ B using M1 and M2. On input string z to P, start running it on M1 and go on pushing symbols on stack. When you see that M1 is in final state at some point of time, guess non-deterministically that machine have seen first half i.e. x. And now P have to run remaining. So now start running it on B and go on poping symbols from stack. If input is done and stack is empty at same time and also M2 is in final state then accept, else reject.

Sipser 2.42 Let E = {1,#} and Y = { w | w = t1#t2# ...... #tk for k ≥ 0, each ti ∈ 1*, and ti ≠ tj whenever i ≠ j}. Prove that Y is not context free.

2.42

Let E = {1,#} and Y = { w | w = t₁#t₂# ...... #t_k for k ≥ 0, each ti ∈ 1^*, and t_i ≠ t_j whenever i ≠ j}. Prove that Y is not context free.

Solution: 

consider  a string 1^p#1^p+1# ... #1^2p-1#1^2p#1^2p+1# ... #1^3p where p is pumping length. While pumping there can be three possibilities :
1. If either v or y has a #. If so, then pump string 3 times.
Let's say hash is in v s.t. v = 1^m#1ⁿ, then v3 will be 1^m#1ⁿ1^m#1ⁿ1^m#1ⁿ = 1^m#1^n+m#1^n+m#1ⁿ. Otherwise # will be in y, which can be shown similarly.
2. If # lies in x,
     a. v lies in 1^j such that j < 2p. if |v| = 1 then pump up it twice, else if |v| > 1 then pump up it once. We must get t_i which will be equal to some t_j.  I have considered to pump twice if |v| = 1 because it may happen that |y| ≠ 0. Think what am I talking.
     b. y lies in 1^j such that j >= 2p. if |y| = 1 then pump down it twice, else if |y| > 1 then pump down it once.
     c. If one of the v and y is empty then pump other up or down once depending on where it lies i.e. 1^j   j is greater than 2p or other way.
3. If both v and y lies in same 1^j, and j ≤ 2p then pump up it once. Else if j > 2p then pump down it once.

I might not have explained properly, but think. You must get it.

Refer to Problem 1.41 for the definition of shuffle operation. Show that the class of context free languages is not closed under shuffle.

2.39

Refer to Problem 1.41 for the definition of shuffle operation. Show that the class of context free languages is not closed under shuffle.

Solution: 

A = {0ⁿ1ⁿ}
B = {aⁿbⁿ}

so  0^pa^p1^pb^p ∈ SHUFFLE(A,B). Consider p to be pumping length.
Now it is clear if you pump from only from single type, then it won't be equal to its counter part like 1 for 0. If you consider to pump in two types, like 0s and a then also it will disturb count equality. 

Sipser 2.28 c. {w | the number of a's is at least the number of b's}

2.28 c. {w | the number of a's is at least the number of b's}

Solution:

S → aSbS | bSaS | aS | ε

aSbS | bSaS generates equal number of a and b. Then aS will help you to generate as many a you want. But it is ambiguous.