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.

2.28 b. { w | the number of a's and b's in w are equal}

2.28 b. { w | the number of a's and b's in w are equal}

Solution:

S → aSbS | bSaS | ε

Don't ask me why? Work it out.

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

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

Hint:
Replace a with open bracket ( and b with closing  bracket ). You will get the big picture that he is talking about set of prefixes of balanced paranthesis language.

Solution:
Finding ambiguity free context free grammer is not that trivial.
Very first step to find an unambiguous grammar is finding a grammar, unambiguous or ambiguous.
Secondly, If you see the ambiguity in it then explore it to know it deeper. And set a priority rules set which will tell you which of the parse tree (derivation) you have to pick. And now set production rules.

Initially what clicked me is:
S → SS | (S) | ε
but it is ambiguous. Think !!

After trying a day or a couple, I figured out the grammar should be
S → (S)S | ε

But this is not what we were looking for but grammar in which every string's prefix have more ( than number of  ).
S → (S)S | (S | ε

Please correct me if I am wrong.

Sipser 2.25: CFLs are closed under SUFFIX(A).

2.25 For any language (A), let SUFFIX(A) = { v | uv ∈ A for some string u }. Show that the class of CFLs is closed under the SUFFIX operation.

Hint: Add epsilon transitions to skip symbols.

Solution: For every state A, add a state A′. And new start  state will be S′. For every transition δ(A,0,a) → (B,b) add a transition δ(A′,ε,a) → (B′,b). And δ(A′,ε,ε) → (A,ε).

2.24 Sipser: Let E = { aibj i ≠ j and 2i ≠ j } Show that D is context-free language.

2.24 Let E = { aⁱb^j  | i ≠ j and 2i ≠ j } Show that D is context-free language.

solution:

Split it as unions of  3 languages.

{ aⁱb^j | i > j } ∪ { aⁱb^j | i < j and 2i > j } ∪ { aⁱb^j | 2i < j }

G¹ = { aⁱb^j | i > j }

G² = { aⁱb^j | i < j and 2i > j }

G³ = { aⁱb^j | 2i < j }

G¹ and G³ are quite easy to figure out.
for G¹

S →   aSb | aS¹
S¹ → aS¹ |ε

for G³

S → aSbb | S¹b
S¹ → S¹b | ε

Now tricky part is G2.

S → aSb | aS¹b
S¹ → aS¹bb | aS²bb
S² → ε

Very clearly, S will generate aⁿa^mb^2mbⁿ that is equivalent to a^n+mb^n+2m where m,n must be greater than 0.

Feel free to comment and correct me if I am wrong. :)

2.23 Let D = {xy | x,y ∈ {0,1}* |x| = |y| but x ≠ y} Show that D is context-free language.

2.23 Let D = {xy | x,y ∈ {0,1}^* |x| = |y| but x ≠ y} Show that D is context-free language.

Solution:

It is a bit tricky. 
Strategy is, x and will be first and second half respectively of a string w ∈ D. If we are able to show that after skipping some n position from start in x and y, we get different symbols, consider the problem done. 

<n symbols>0<m symbols>    <n symbols>1<m symbols>

or 

<n symbols>1<m symbols>    <n symbols>0<m symbols>

where m,n ∈ non negative intezers. 


Grammar : 

S →  AB | BA
A → 0A0 | 0A1 | 1A0 | 1A1 | 0
B → 0B0 | 0B1 | 1B0 | 1B1 | 1 

this grammar will generate strings of type 

<n symbols>0<n symbols> <m symbols>1<m symbols>

which is actually equivalent to 

<n symbols>0<m symbols>  <n symbols>1<m symbols>


Feel free to comment to clear doubt. :)

Sipser Second Edition 2.19

2.19
Let CFG G be
S → aSb | bY | Ya
Y → bY | aY | ε
Give a simple description of L(G) in English. Use that description to give a CFG for L(G)^c, the complement of L(G).

Solution.
I don't know the exact solution. Here I am discussing what I am thinking.
Clearly, Y generates all strings over a,b. So if we consider only last two rules for S those are bY| Ya, then they will generate all strings { w | w has length at least 1 and w either starts with a 'b' or ends with
a 'a' }. That means these two rule will not generate a string starting with a and ending with b. Now consider S → aSb. This rule generates string starting with a, ending with b and middle will not contain a string ba.
Hence L(G) have every string over a,b but not the strings of even length whose middle(center) have 'ab'. Like it will never generate <substring of length k>ab<substring of length k>.

So its complement will have all strings which look like <substring of length k>ab<substring of length k>.

S → aSb | bSa | aSa | bSb | ba



I expect it to be right, but in case I am not then please comment.

Sipser 2.2 b. CFLs are not closed under Intersection.

2.2 b. Use part (a) and DeMorgan's law to show that the class of CFLs is not closed under complementation.

Sol.

A = {a^mbⁿcⁿ | m,n ≥ 0}

B = {aⁿbⁿc^m | m,n ≥ 0}

A ∩ B = {aⁿbⁿcⁿ | n ≥ 0}
Clearly, A ∩ B is not CFL(pumping lemma). Demorgans' law :

(A ∩ B)^c = A^c ∪ B^c

A^c  = {a^mbⁱc^j | m, i, j ≥ 0 & i ≠ j} = {a^mbⁱc^j | m, i, j ≥ 0 & i > j} ∪ {a^mbⁱc^j | m, i, j ≥ 0 & i < j}

now prove that {a^mbⁱc^j | m, i, j ≥ 0 & i > j} is CFL.
{a^mbⁱc^j | m, i, j ≥ 0 & i  <  j} :
S → S₁S₂
S₁ → aS₁
S₂ → bS₂c | S₂c | c

Similarly {a^mbⁱc^j | m, i, j ≥ 0 & i < j} is CFL and so is A^c. Similar argument holds for B^c. So A^c ∪ B^c is also CFL(Union of CFL is CFL) . Hence proved complement of CFL is not closed.

Sipser 1.63 Let A be an infinite regular language. Prove that A can be split into two infinite disjoint regular subsets.

Sipser 1.63

(a) Let A be an infinite regular language. Prove that A can be split into two infinite disjoint regular subsets.

Hint: An infinite regular language must be having a loop in its trasistion diagram for DFA (if complement operation is not given). Unroll the loop to make two DFA, first of which accepts strings which have odd number of iterations of concerned loops and second accepts strings which have even number of iteration of concerned loops.

Now, don't ask me solution u dumbo. this is the solution.

(b) Let B and D be two languages. Write B⊂⊂D if B ⊂ D and D contains infinitely many strings that are not in B. Show that, if B and D are two languages where B⊂⊂D, then we can find a regular language C where B⊂⊂C⊂⊂D.

Solution: by part (a), I can always split D into B and A which both are infinite and disjoint regular subsets. And similarly, I can split A into A₁ and A₂, both of them regular infinite and disjoint. Consider C = B ∪ A₁. Of course C is regular (union of two regular languages is regular) and infinite.
And B,C,D holds B⊂⊂C⊂⊂D true.

Sipser 1.62: Dk be the language consisting of all strings that have at least one 'a' among last k symbols. Thus Dk = Σ* a (Σ ∪ ε)k-1 , Give a DFA with at most k+1 states which accepts this language.

Sipser 1.62: D_k be the language consisting of all strings that have at least one 'a' among last k symbols.
Thus D_k  = Σ^* a (Σ ∪ ε)^k-1  , Give a DFA with at most k+1 states which accepts this language.

Solution: