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. :)