Question

Refer to Problem 1.42 for the definition of the shuffle operation. Show that the class of context-free languages is not closed under shuffle.

$\left\{w|w=a_1{b}_1........a_k{b}_k\mathrm{where}{a}_1.......a_k\in A\mathrm{and}{b}_1.......b_k\in B,\mathrm{each}{a}_i{b}_i\in {\sum }^{*}\right\}\mathbf{.}$

Short answer

Shuffle property is not Closed under Context Free Language.

Step-by-step solution

Prove the CFG is not closed under shuffle operation

The class of context-free languages is not closed under shuffle this is proved by the example is given below and also by showing that the language $\left\{\mathrm{w}|\mathrm{w}={\mathrm{a}}_1{\mathrm{b}}_1........{\mathrm{a}}_{\mathrm{k}}{\mathrm{b}}_{\mathrm{k}}\mathrm{where}{\mathrm{a}}_1.......{\mathrm{a}}_{\mathrm{k}}\in \mathrm{A}\mathrm{and}{\mathrm{b}}_1.......{\mathrm{b}}_{\mathrm{k}}\in \mathrm{B},\mathrm{each}{\mathrm{a}}_{\mathrm{i}}{\mathrm{b}}_{\mathrm{i}}\in {\sum }^{*}\right\}.$is not context free by using pumping lemma.

Step 2: Shuffle operation.

Let the given two languages $\mathrm{A}$and$\mathrm{B}$over the alphabet $\sum$,let the shuffle of$\mathrm{A}$and$\mathrm{B}$be,

$\left\{\mathrm{w}|\mathrm{w}={\mathrm{a}}_1{\mathrm{b}}_1\mathrm{........}{\mathrm{a}}_{\mathrm{k}}{\mathrm{b}}_{\mathrm{k}}\mathrm{where}{\mathrm{a}}_1\mathrm{.......}{\mathrm{a}}_{\mathrm{k}}\in \mathrm{A}\mathrm{and}{\mathrm{b}}_1\mathrm{.......}{\mathrm{b}}_{\mathrm{k}}\in \mathrm{B},\mathrm{each}{\mathrm{a}}_{\mathrm{i}}{\mathrm{b}}_{\mathrm{i}}\in {\sum }^{*}\right\}.$

Here the $\mathrm{A}$and $\mathrm{B}$as follows:

$\mathrm{A}=\{\mathrm{w}\in {\{0,1\}}^{*}|{\mathrm{n}}_0\left(\mathrm{w}\right)={\mathrm{n}}_1\left(\mathrm{w}\right)\}$

$\text{B={w}\in \left\{\text{a,b}\right\}{\text{*|n}}_a\left(\text{w}\right){\text{=n}}_b\left(\text{w}\right)\text{},}$

where ${\mathrm{n}}_0\left(\mathrm{w}\right)$denotes the number of zeros in $\mathrm{w}$, ${\mathrm{n}}_{\mathrm{a}}\left(\mathrm{w}\right)$denotes the number of a’s in $\mathrm{w}$ and so on.

The shuffle of$\mathrm{A}$ and$\mathrm{B}$is the language,

$\begin{array}{l}\mathrm{S}=\{\mathrm{w}\in \{0,1,\mathrm{a},\mathrm{b}\}*|{\mathrm{n}}_0\left(\mathrm{w}\right)={\mathrm{n}}_1\left(\mathrm{w}\right){\mathrm{andn}}_{\mathrm{a}}\left(\mathrm{w}\right)={\mathrm{n}}_{\mathrm{b}}\left(\mathrm{w}\right)\},\\ \end{array}$

Which is not context-free, and assume that S is context-free and let p be its pumping length.

By the pumping lemma, s can be written as: $\mathrm{uvxyz}$, where

$\begin{array}{l}\left|\mathrm{vy}\right|>1\mathrm{and}\\ \left|\mathrm{vxy}\right|\le \mathrm{p}\\ \begin{array}{l}\mathrm{Since},\\ \left|\mathrm{vxy}\right|\ge \mathrm{p},\end{array}\end{array}$

it cannot contain both zeros and ones or both a’s and b’s. Hence, pumping once${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$ will result in a string with either an unbalanced number of zeros and ones or an unbalanced number of a’s and b’s or both.

Thus,${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$, so this is not context-free.

We showed in class that$\mathrm{A}$ is context-free and$\mathrm{B}$ is similarly context-free.

Since the shuffle of $\mathrm{A}$and$\mathrm{B}$ is not context-free,

we conclude that the class of context free language (CFLs) is not closed under the shuffle operation.