Question

Let $\mathbf{\sum }\mathbf{=}\mathbf{\{}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{3}\mathbf{,}\mathbf{4}\mathbf{\}}$and$\mathbf{C}\mathbf{=}\mathbf{\{}\mathbf{w}\mathbf{\in }\mathbf{\Sigma }\mathbf{*}\mathbf{|}\mathbf{in}\mathbf{}\mathbf{w}\mathbf{,}$ the number of 1s equals the number of 2s, and the number of 3s equals the number of 4s} Show that$\mathbf{C}$is not context free.

Short answer

This language is not context free this can be proof by using pumping lemma.

Step-by-step solution

pumping lemma for CFG

Here the pumping lemma is used to find the language is context free or not.

a. Assume B is CFG and their L is 0s and 1s. where Z is belongs to L.

$\begin{array}{c}\left|\mathrm{z}\right|\ge \mathrm{n}\\ \mathrm{z}=\mathrm{uvwxy}\\ \left|\mathrm{v}\right|\ge 1\end{array}$

Here at least 1 is not null.

b. Find a suitable k so that${\mathrm{uv}}^{\mathrm{k}}{\mathrm{wx}}^{\mathrm{k}}\mathrm{y}\notin \mathrm{L}$so L is not context free language.

$\begin{array}{c}\mathrm{L}=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{n}}{\mathrm{c}}^{\mathrm{n}}\right|\mathrm{n}\ge 0\}\\ \mathrm{z}=\mathrm{uvwxy},\\ \mathrm{z}={\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{n}}{\mathrm{c}}^{\mathrm{n}}\{\mathrm{n}=1,\mathrm{z}=\mathrm{abc}\}\\ \left|\mathrm{z}\right|=3\mathrm{n}>\mathrm{n}\end{array}$

If we equate both z then we get,

$\begin{array}{c}\mathrm{uvwxy}={\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{n}}{\mathrm{c}}^{\mathrm{n}}\\ \left|\mathrm{vx}\right|\ge 1,\{\mathrm{n}\ge |\mathrm{vx}|\ge 1\}\end{array}$

Then after that,

Let v or x is a part of -

$\begin{array}{l}\left({\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{j}}\right)\mathrm{or}\left({\mathrm{b}}^{\mathrm{i}}{\mathrm{c}}^{\mathrm{j}}\right)\\ \mathrm{v}=\left({\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{j}}\right)\\ {\mathrm{v}}^2=\left({\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{j}}\right)\left({\mathrm{b}}^{\mathrm{i}}{\mathrm{c}}^{\mathrm{j}}\right)\\ {\mathrm{uv}}^2{\mathrm{wx}}^2\mathrm{y}={\mathrm{a}}^{\mathrm{m}}{\mathrm{b}}^{\mathrm{m}}{\mathrm{c}}^{{}^{\mathrm{m}}}\end{array}$

From this equation, it is proof that

${\mathrm{uv}}^2{\mathrm{wx}}^2\mathrm{y}\notin \mathrm{L}$

Therefore, L is not context free language.

Proving for Language is not CFG by Pumping Lemma.a).

Suppose$\mathrm{C}$is a context free language and Let $\mathrm{p}$be the pumping length and$\mathrm{s}=1^{\mathrm{p}}{3}^{\mathrm{p}}{2}^{\mathrm{p}}{4}^{\mathrm{p}}\in \mathrm{C}$.

Since, $\left|\mathrm{s}\right|\ge \mathrm{p},$then write,

$\mathrm{s}=\mathrm{uvxyz}$

and satisfying the condition of the pumping lemma.

Since, $\left|\mathrm{vxy}\right|\le \mathrm{p},$

$\begin{array}{c}\mathrm{L}=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{n}}{\mathrm{c}}^{\mathrm{n}}\right|\mathrm{n}\ge 0\}\\ \mathrm{z}=\mathrm{uvwxy},\\ \mathrm{z}={\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{n}}{\mathrm{c}}^{\mathrm{n}}\{\mathrm{n}=1,\mathrm{z}=\mathrm{abc}\}\\ \left|\mathrm{z}\right|=3\mathrm{n}>\mathrm{n}\end{array}$

If we equate both z then we get,

$\begin{array}{l}\mathrm{uvwxy}={\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{n}}{\mathrm{c}}^{\mathrm{n}}\\ \left|\mathrm{vx}\right|\ge 1,\{\mathrm{n}\ge |\mathrm{vx}|\ge 1\}\end{array}$

Then after that,

there are three possible cases

1) If $\mathrm{vxy}$is substring of $1^{\mathrm{p}}{3}^{\mathrm{p}}$, then in ${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$, either the number of 1s is greater than the number of two’s, or the number of three’s is greater than number of four, or both. Thus, uv2xy2 z $\notin C$, which is a contradiction.

2) If$\mathrm{vxy}$ is substring of $2{}^{\mathrm{p}}4{}^{\mathrm{p}}$, then similar to ${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$$\notin \mathrm{C}$, which is a contradiction.

3) If $\mathrm{vxy}$is a substring of $3{}^{\mathrm{p}}2{}^{\mathrm{p}}$ them in${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$ , either the number of twos is greater than the number of one’s or the number of three’s is greater than number of fours, or both. Thus,${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$$\notin \mathrm{C}$ , which is a contradiction.