Ullman (TOC) Edition 3 Exercise 7.3 Question 4 (Page No. 297 - 298)

Question

The $\text{shuffle}$ of two strings $w$ and $x$ is the set of all strings that one can get by interleaving the positions of $w$ and $x$ in any way. More precisely  $,\text{shuffle(w,x)}$ is the set of strings $z$ such that

1. Each position of $z$ can be assigned to $w$ or $x,$but not both.
2. The positions of $z$ assigned to $w$ form $w$ when read from left to right.
3. The positions of $z$ assigned to $x$ form $x$ when reading from left to right.

For example, if $w=01$ and $x=110,$ then  $\text{shuffle(01,110)}$ is the set of strings $\{01110,01101,10110,10101,11010,11001\}.$ To illustrate the necessary reasoning the fourth string  $,10101,$ is justified by assigning the second and fifth positions to $01$ and positions one three and four to $110.$ The first string $,01110,$ has three justifications.Assign the first position and either the second, third,or fourth to $01,$and the other three to $110.$We can also define the  $\text{shuffle}$ of languages , $\text{shuffle($L_{1},L_{2}$)},$ to be the union over all pairs of strings, $w$ from $L_{1}$ and $x$ from $L_{2},$ of $\text{shuffle(w,x)}.$

1. What is $\text{shuffle(00,111)}?$
2. What is $\text{shuffle($L_{1},L_{2}$)}$ if $L_{1}=L(0^{*})$ and $L_{2}=\{0^{n}1^{n}|n\geq 0\}?$
3. Show that if $L_{1}$ and $L_{2}$ are both regular languages,then so is $\text{shuffle($L_{1},L_{2}$)}$ Hint$:$ Start with $DFA's$ for $L_{1}$ and $L_{2}.$
4. Show that if $L$ is a $CFL$ and $R$ is a regular language , then $\text{shuffle($L_{1},L_{2}$)}$ is a $CFL$ Hint$:$ Start with a $PDA$ for $L$ and a $DFA$ for $R.$
5. Give a counterexample to show that if $L_{1}$ and $L_{2}$ are both $CFL's,$ then $\text{shuffle($L_{1},L_{2}$)}$ need not be a $CFL.$