Question

Use the pumping lemma to show that the following languages are not context free.

a. $\mathbf{\left\{}{\mathbf{0}}^{\mathbf{n}}{\mathbf{1}}^{\mathbf{n}}{\mathbf{0}}^{\mathbf{n}}{\mathbf{1}}^{\mathbf{n}}\mathbf{|}\mathbf{n}\mathbf{\ge }\mathbf{0}\mathbf{\right\}}$

b.$\mathbf{\{}{\mathbf{0}}^{\mathbf{n}}\mathbf{\#}{\mathbf{0}}^{\mathbf{2}\mathbf{n}}\mathbf{\#}{\mathbf{0}}^{\mathbf{3}\mathbf{n}}\mathbf{|}\mathbf{n}\mathbf{\ge }\mathbf{0}\mathbf{\}}$

c. role="math" localid="1659701399563" $\mathbf{\left\{}\mathbf{w}\mathbf{\#}\mathbf{t}\mathbf{|}\mathbf{w}\mathbf{}\mathbf{is}\mathbf{}\mathbf{a}\mathbf{substring}\mathbf{}\mathbf{of}\mathbf{}\mathbf{t}\mathbf{,}\mathbf{where}\mathbf{w}\mathbf{,}\mathbf{t}\mathbf{\in }{\mathbf{(}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{)}}^{\mathbf{*}}\mathbf{\right\}}$

d. $\mathbf{\left(}{\mathbf{t}}_{\mathbf{1}}{\mathbf{\#}}_{\mathbf{2}}\mathbf{\#}\mathbf{.}\mathbf{.....}\mathbf{\#}{\mathbf{t}}_{\mathbf{k}}\mathbf{|}\mathbf{k}\mathbf{\ge }\mathbf{2}\mathbf{,}\mathbf{each}{\mathbf{t}}_{\mathbf{i}}\mathbf{\in }{\mathbf{\{}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{\}}}^{\mathbf{*}}\mathbf{and}\mathbf{t}\mathbf{=}\mathbf{t}\mathbf{for}\mathbf{some}\mathbf{i}\mathbf{\ne }\mathbf{j}\mathbf{\right)}$

Short answer

a). This language $\left\{0^{\mathrm{n}}{1}^{\mathrm{n}}{0}^{\mathrm{n}}{1}^{\mathrm{n}}|\mathrm{n}\ge 0\right\}$is not context free this can be proof by using pumping lemma.

b). $\{0^{\mathrm{n}}\#0^{2\mathrm{n}}\#0^{3\mathrm{n}}|\mathrm{n}\ge 0\}$is also not context free.

c). This language$\left\{\mathrm{w}\#\mathrm{t}|\mathrm{w}\mathrm{is}\mathrm{a}\mathrm{substring}\mathrm{of}\mathrm{t},\mathrm{where}\mathrm{w},\mathrm{t}\in {(\mathrm{a},\mathrm{b})}^{*}\right\}$ is not context free this can be proof by using pumping lemma.

d).$\left({\mathrm{t}}_1{\#}_2\#\mathrm{......}\#{\mathrm{t}}_{\mathrm{k}}|\mathrm{k}\ge 2,\mathrm{each}{\mathrm{t}}_{\mathrm{i}}\in {\{\mathrm{a},\mathrm{b}\}}^{*}\mathrm{and}\mathrm{t}=\mathrm{t}\mathrm{for}\mathrm{some}\mathrm{i}\ne \mathrm{j}\right)$is also not context free.

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 so${\mathrm{uv}}^{\mathrm{k}}{\mathrm{wx}}^{\mathrm{k}}\mathrm{y}\notin \mathrm{L}$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}{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).

$\left\{0^{\mathrm{n}}{1}^{\mathrm{n}}{0}^{\mathrm{n}}{1}^{\mathrm{n}}|\mathrm{n}\ge 0\right\}$

This language$\mathrm{L}$consist of four consecutive digits or called segment where a zero segment, followed by a one segment after that another zero-segment followed by another one segment.

Let the given language is context-free and pumping lemma is showing by the variable$\mathrm{P}$for the given language $\mathrm{L}$.

Now consider the string or the given language is belonging to $\mathrm{L}$. That is $0^{\mathrm{n}}{1}^{\mathrm{n}}{0}^{\mathrm{n}}{1}^{\mathrm{n}}\in \mathrm{L}$. After that write this string as in the order of$\mathrm{uvwxy}$.

Where,

$\begin{array}{l}\left|\mathrm{vxy}\right|\le \mathrm{p}\\ \left|\mathrm{vy}\right|>1\end{array}$

Now, there are two cases according to this statement:

case 1: $\mathrm{v}\mathrm{or}\mathrm{y}$contains more than one type of character. that is at least one of contains both zeros and ones. And when pumping lemma is applied than, ${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$now insert an extra $0^{\mathrm{i}}{1}^{\mathrm{j}}$ into the prescribed sequence after the resulting string will contain at least 3 zero segments and 3 one segments.

$\mathrm{v}=0011$, then pumping once would result in an additional zero, zero segment followed by two one’s segment.

But, strings in $\mathrm{L}$contain only four segments.

case 2: $\mathrm{v}\mathrm{or}\mathrm{y}$ contain only one type of character or contain one type of language and they both are all zeros or all ones.

Since,

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

$\left|\mathrm{vxy}\right|$contains letters from at most two segments of itself.

Pumping once to${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$ increases the number of characters in one or two of the segments. From here, the number of characters in each language are not equal.

So, there it shows,

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

Therefore, the given language $\mathrm{L}$ is not context free language.

Proving the Language is not CFG.

b).

$\{0^{\mathrm{n}}\#0^{2\mathrm{n}}\#0^{3\mathrm{n}}|\mathrm{n}\ge 0\}$

Let the given language is context-free and pumping lemma is showing by the variable $\mathrm{p}$for the given language $\mathrm{L}$. Here the pumping lemma is used to find the language is context free or not.

While applying pumping lemma on the language

And 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}\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.

After this step let lies on one side of the # symbol. Then, pumping once to ${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$results in a string. Suppose $\mathrm{vxy}$that contains the # symbol. If $\mathrm{v}\mathrm{or}\mathrm{y}$either contains the # symbol, and the Pumping once to ${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$.

${\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.c).

$\left\{\mathrm{w}\#\mathrm{t}|\mathrm{w}\mathrm{is}\mathrm{a}\mathrm{substring}\mathrm{of}\mathrm{t},\mathrm{where}\mathrm{w},\mathrm{t}\in {(\mathrm{a},\mathrm{b})}^{*}\right\}$

This language$\mathrm{L}$consist of a substring containing the symbols a and b belongs to the string which shows$\mathrm{w}\#\mathrm{t}|\mathrm{w}\mathrm{is}\mathrm{a}\mathrm{substring}\mathrm{of}\mathrm{t},\mathrm{where}\mathrm{w},\mathrm{t}\in {(\mathrm{a},\mathrm{b})}^{*}$

Let the given language is context-free and pumping lemma is showing by the variable $\mathrm{p}$for the given language $\mathrm{L}$.

Now consider the string or the given language is belonging to$\mathrm{L}$. That is$\mathrm{w}\#\mathrm{t}$. After that write this string as in the order of $\mathrm{uvwxy}$.

Where,

$\begin{array}{l}\left|\mathrm{vxy}\right|\le \mathrm{p}\\ \left|\mathrm{vy}\right|>1\end{array}$

Pumping once to${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$increases the number of characters in one or two of the segments. From here, the number of characters in each language are not equal.

So, there it shows,

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

Therefore, the given language $\mathrm{L}$is not context free language.

Proving for Language is not CFG by Pumping Lemma.

d).

${\mathrm{t}}_1{\#}_2\#\mathrm{......}\#{\mathrm{t}}_{\mathrm{k}}|\mathrm{k}\ge 2,\mathrm{each}{\mathrm{t}}_{\mathrm{i}}\in {\{\mathrm{a},\mathrm{b}\}}^{*}\mathrm{and}\mathrm{t}=\mathrm{t}\mathrm{for}\mathrm{some}\mathrm{i}\ne \mathrm{j}$

Let $\mathrm{L}$ is context free and let p denote its pumping length. and pumping lemma is showing by the variable $p$for the given language $L$.

Now, let

$\mathrm{s}=0^{\mathrm{p}}{1}^{\mathrm{p}}\#0^{\mathrm{p}}{1}^{\mathrm{p}}\in \mathrm{L}$

After applying pumping lemma, also write s as $\mathrm{uvwxy}$where,

$\begin{array}{c}\left|\mathrm{vxy}\right|\le \mathrm{p}\\ \left|\mathrm{vy}\right|>1\end{array}$

After this step let $\mathrm{vxy}$lies on one side of the # symbol. Then, pumping once to ${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$results in a string. Suppose $\mathrm{vxy}$that contains the # symbol. If $\mathrm{v}\mathrm{or}\mathrm{y}$either contains the # symbol, and the Pumping once to ${\mathrm{uv}}^2{\mathrm{xy}}^2\mathrm{z}$increases the number of characters in one or two of the segments. From here, the number of characters in each language are not equal.

than only pump to $u{v}^{2}x{y}^{2}z$, which will not contain the # symbol and hence will not be in $\mathrm{L}$. As, this is not a context free grammar.