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.