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.

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

$\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.