91Ó°ÊÓ

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}\text{ â¶ÄŠâ¶ÄŠ}{\mathrm{a}}_1.......{\mathrm{a}}_{\mathrm{k}}∈\mathrm{A}\text{ â¶ÄŠâ¶ÄŠ}\mathrm{and}\text{ â¶ÄŠâ¶ÄŠ}{\mathrm{b}}_1.......{\mathrm{b}}_{\mathrm{k}}∈\mathrm{B},\mathrm{each}\text{ â¶ÄŠ}{\mathrm{a}}_{\mathrm{i}}{\mathrm{b}}_{\mathrm{i}}∈{∑}^{*}\right\}.$is not context free by using pumping lemma.

Let the given two languages $\mathrm{A}$and$\mathrm{B}$over the alphabet $∑$,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}\text{ â¶ÄŠâ¶ÄŠ}{\mathrm{a}}_1\mathrm{.......}{\mathrm{a}}_{\mathrm{k}}∈\mathrm{A}\text{ â¶ÄŠâ¶ÄŠ}\mathrm{and}\text{ â¶ÄŠâ¶ÄŠ}{\mathrm{b}}_1\mathrm{.......}{\mathrm{b}}_{\mathrm{k}}∈\mathrm{B},\mathrm{each}\text{ â¶ÄŠâ¶ÄŠâ€Š}{\mathrm{a}}_{\mathrm{i}}{\mathrm{b}}_{\mathrm{i}}∈{∑}^{*}\right\}.$

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

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

$\text{B={w}∈\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}∈\{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|≤\mathrm{p}\\ \begin{array}{l}\mathrm{Since},\\ \left|\mathrm{vxy}\right|â‰\yen \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.