Question

Let $\mathbf{A}\mathbf{=}\mathbf{\left\{}{\mathbf{wtw}}^{\mathbf{R}}\mathbf{\right|}\mathbf{w}\mathbf{,}\mathbf{t}\mathbf{\in }{\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{\}}}^{\mathbf{*}}\mathbf{and}\mathbf{\left|}\mathbf{w}\mathbf{\right|}\mathbf{=}\mathbf{\left|}\mathbf{t}\mathbf{\right|}\mathbf{\}}\mathbf{.}$ Prove that A is not a CFL.

Short answer

$\mathrm{A}=\left\{{\mathrm{wtw}}^{\mathrm{R}}\right|\mathrm{w},\mathrm{t}\in {\{0,1\}}^{*}\mathrm{and}\left|\mathrm{w}\right|=\left|\mathrm{t}\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 ${\mathrm{uv}}^{\mathrm{k}}{\mathrm{wx}}^{\mathrm{k}}\mathrm{y}\notin \mathrm{L}$that 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.a).

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|\le \mathrm{p}\\ \left|\mathrm{vy}\right|\ge 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|\times (\mathrm{i}+1)\ge 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{'}\ne {\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{'}\ne {\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|\ge \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{'}\ne {\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.