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.