Question

Show that F = { ${\mathbf{a}}^{\mathbf{i}}{\mathbf{b}}^{\mathbf{j}}\mathbf{|}\mathbf{i}\mathbf{=}\mathbf{kj}$for some positive integer$\mathbf{k}$ } is not context free

Short answer

F = {${\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{j}}|\mathrm{i}=\mathrm{kj}$ for some positive integer $\mathrm{k}$}

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

$\begin{array}{l}{\mathrm{uv}}^2{\mathrm{wx}}^2\mathrm{y}\notin \mathrm{L}\\ \end{array}$

Therefore, L is not context free language.

Proving for Language is not CFG by Pumping Lemma.

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

Assume B is CFG and their L is 0s and 1s. where Z is belongs to Land the context free language is a grammar where its language is supports pushdown deterministic automata. Also evaluate that from the given grammar’s language follows only one parse tree, and it is also a way to detect it is context free grammar or not.

Let pumping length is pp and suppose take string for pumping lemma test.

F = { ${\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{j}}|\mathrm{i}=\mathrm{kj}$for some positive integer $\mathrm{k}$}

The language produces by this grammar is given as below:

L = { ${\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{i}},{\mathrm{a}}^{\mathrm{j}}{\mathrm{b}}^{\mathrm{j}},{\mathrm{a}}^{2\mathrm{j}}{\mathrm{b}}^{2/\mathrm{i}}$}

Here the language is context free language then it must accept by the pushdown deterministic automata. Which also accept context free grammar.

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

${\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{i}},{\mathrm{a}}^{\mathrm{j}}{\mathrm{b}}^{\mathrm{j}},{\mathrm{a}}^{2\mathrm{j}}{\mathrm{b}}^{2/\mathrm{i}}$$\notin$ CFG

Any of the conditions are not applicable for the given language as evaluate by the pumping lemma. Hence, the language L = {${\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{i}},{\mathrm{a}}^{\mathrm{j}}{\mathrm{b}}^{\mathrm{j}},{\mathrm{a}}^{2\mathrm{j}}{\mathrm{b}}^{2/\mathrm{i}}$ } does not follows the pumping lemma property so this grammar and as well as the language from this language is not a context free grammar.

F = {${\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{j}}|\mathrm{i}=\mathrm{kj}$ for some positive integer $\mathrm{k}$}

This language is not context free this proved by using pumping lemma.