Question

Let

$\mathbf{y}\mathbf{=}\mathbf{\left\{}\mathbf{w}\mathbf{|}\mathbf{w}\mathbf{=}{\mathbf{t}}_{\mathbf{1}}\mathbf{\#}{\mathbf{t}}_{\mathbf{2}}\mathbf{\#}\mathbf{.}\mathbf{......}\mathbf{\#}{\mathbf{t}}_{\mathbf{k}}\mathbf{for}\mathbf{k}\mathbf{\ge }\mathbf{0}\mathbf{each}{\mathbf{t}}_{\mathbf{i}}\mathbf{\in }{\mathbf{1}}^{\mathbf{*}}\mathbf{,}\mathbf{and}{\mathbf{t}}_{\mathbf{i}}\mathbf{\ne }{\mathbf{t}}_{\mathbf{j}}\mathbf{whenever}\mathbf{i}\mathbf{\ne }\mathbf{j}\mathbf{\right\}}$.

Here$\mathbf{\Sigma }\mathbf{=}\mathbf{\{}\mathbf{1}\mathbf{,}\mathbf{\#}\mathbf{\}}\mathbf{.}$ Prove that $\mathbf{Y}$ is not context free.

Short answer

$\left\{\mathrm{w}|\mathrm{w}={\mathrm{t}}_1\#{\mathrm{t}}_2\#\mathrm{.......}\#{\mathrm{t}}_{\mathrm{k}}\mathrm{for}\mathrm{k}\ge 0\mathrm{each}{\mathrm{t}}_{\mathrm{i}}\in 1^{*},\mathrm{and}{\mathrm{t}}_{\mathrm{i}}\ne {\mathrm{t}}_{\mathrm{j}}\mathrm{whenever}\mathrm{i}\ne \mathrm{j}\right\}$

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}{l}\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}{l}\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,

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

$\left\{\mathrm{w}|\mathrm{w}={\mathrm{t}}_1\#{\mathrm{t}}_2\#\mathrm{.......}\#{\mathrm{t}}_{\mathrm{k}}\mathrm{for}\mathrm{k}\ge 0\mathrm{each}{\mathrm{t}}_{\mathrm{i}}\in 1^{*},\mathrm{and}{\mathrm{t}}_{\mathrm{i}}\ne {\mathrm{t}}_{\mathrm{j}}\mathrm{whenever}\mathrm{i}\ne \mathrm{j}\right\}$

Let’s the above string where$\mathrm{p}$ is pumping length. While pumping there can be three possibilities:

1. If either $\mathrm{v}$ or $\mathrm{y}$ has a $\#$ . If so, then pump string three times.
Let's hash is in $\mathrm{v}=1^{\mathrm{m}}\#1^{\mathrm{n}}$ . then v3 will be v = 1^m#1ⁿ, 1^m#1ⁿ1^m#1ⁿ1^m#1ⁿ. Otherwise $\#$ will be in $\mathrm{y}$, which can be shown similarly.

2. If $\#$lies in $x$,

a) v lies in $1^{\mathrm{i}}$ such that $\mathrm{j}\ge 2\mathrm{p}$.

if $\left|\mathrm{v}\right|>1$ then pump up it twice, else if $\left|\mathrm{v}\right|>1$ then pump up it once. We must get which will be equal to some and considered to pump twice if $\left|\mathrm{v}\right|>1$because that is $\left|\mathrm{y}\right|>1$.

b). $\mathrm{y}$ lies in $1^{\mathrm{i}}$ such that $\mathrm{j}⩾2\mathrm{p}$. if $\left|\mathrm{y}\right|=1$then pump down it twice, else if $\left|\mathrm{y}\right|>1$ then pump down it once.

c). If one of the $\mathrm{v}$and $\mathrm{y}$ is empty then pump other up or down once depending on where it lies i.e.$1^{\mathrm{i}}$ j is greater than 2p or other way.

3). If both$\mathrm{v}$ and$\mathrm{y}$ lies in same$1^{\mathrm{i}}$, and$\mathrm{j}\ge 2\mathrm{p}$then pump up it once. Else if$\mathrm{j}\ge 2\mathrm{p}$then pump down it once.

$\left\{\mathrm{w}|\mathrm{w}={\mathrm{t}}_1\#{\mathrm{t}}_2\#\mathrm{.......}\#{\mathrm{t}}_{\mathrm{k}}\mathrm{for}\mathrm{k}\ge 0\mathrm{each}{\mathrm{t}}_{\mathrm{i}}\in 1^{*},\mathrm{and}{\mathrm{t}}_{\mathrm{i}}\ne {\mathrm{t}}_{\mathrm{j}}\mathrm{whenever}\mathrm{i}\ne \mathrm{j}\right\}$is not context free proved by using pumping lemma.