91Ó°ÊÓ

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

$\begin{array}{l}\left|\mathrm{z}\right|â‰\yen \mathrm{n}\\ \mathrm{z}=\mathrm{uvwxy}\\ \left|\mathrm{v}\right|â‰\yen 1\end{array}$

Here at least 1 is not null.

$\begin{array}{l}\mathrm{L}=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{n}}{\mathrm{c}}^{\mathrm{n}}\right|\mathrm{n}â‰\yen 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|â‰\yen 1,\{\mathrm{n}â‰\yen |\mathrm{vx}|â‰\yen 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}∉\mathrm{L}$

Therefore, L is not context free language.

Suppose$\mathrm{A}$is context-free. Then, let $\mathrm{p}$be the pumping length for$\mathrm{A}$, such that any string in$\mathrm{A}$of length at least $\mathrm{p}$will satisfy the pumping lemma.

Now, select a string in $\mathrm{A}$with,

$\mathrm{s}=0^{2\mathrm{p}}{0}^{\mathrm{p}}{1}^{\mathrm{p}}{0}^{2\mathrm{p}}$

For string to satisfy the pumping lemma, there is a way that string can be written as,

$\begin{array}{l}\mathrm{Uvxyz}\\ \left|\mathrm{vxy}\right|≤\mathrm{p}\\ \left|\mathrm{vy}\right|â‰\yen 1,\end{array}$

and for any$\mathrm{i},{\mathrm{uv}}^{\mathrm{i}}{\mathrm{xy}}^{\mathrm{i}}\mathrm{z}$, is a string in$\mathrm{A}$.

There are only three cases to write string with the above conditions:

Case 1:

$\mathrm{vy}$contains only zeros and these zeros are chosen from the last $0^{2\mathrm{p}}$of string. Let $\mathrm{i}$be a number with $7\mathrm{p}>\left|\mathrm{vy}\right|×(\mathrm{i}+1)â‰\yen 6\mathrm{p}$. Then, either the length of ${\mathrm{uv}}^{\mathrm{i}}{\mathrm{xy}}^{\mathrm{i}}\mathrm{z}$is not a multiple of three, or this string is of the form ${\mathrm{wtw}}^{\text{'}}$ such that | $\left|\mathrm{w}\right|=\left|\mathrm{t}\right|=|\mathrm{w}\text{'}|$with $\mathrm{w}\text{'}$ is all zeros and w is not all zeros (this is, $\mathrm{w}\text{'}≠{\mathrm{w}}^{\mathrm{R}}$).

Case 2:

$\mathrm{vy}$does not contain any zeros in the last $0^{2\mathrm{p}}$of string.

Then, either the length of ${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$ is not a multiple of three, or this string is of the form wtw0 such that $\left|\mathrm{w}\right|=\left|\mathrm{t}\right|=|\mathrm{w}\text{'}|$with w is all zeros and ${\mathrm{w}}^1$ is not all zeros (that is, $\mathrm{w}\text{'}≠{\mathrm{w}}^{\mathrm{R}}$).

Case 3:

$\mathrm{vy}$are not all zeros, and some zeros are from the last $0^{2\mathrm{p}}$of string.

As |vxy| ≤ p $\left|\mathrm{vxy}\right|â‰\yen \mathrm{p}$,$\mathrm{vxy}$in this case must be a substring in 1 p0 $\mathrm{p}$. Then, either the length of ${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$is not a multiple of three, or this string is of the form wtw0 such that , $\left|\mathrm{w}\right|=\left|\mathrm{t}\right|=|\mathrm{w}\text{'}|$with w is all zeros and${\mathrm{w}}^1$ is not all zeros (that is,$\mathrm{w}\text{'}≠{\mathrm{w}}^{\mathrm{R}}$ ).

In summary, just observe that there is no way string to satisfy the pumping lemma. Thus, a contradiction occurs, and then conclude that $\mathrm{A}$is not a context-free language.