Question

Prove the following stronger form of the pumping lemma, wherein both pieces $\mathbf{v}\mathbf{}\mathbf{and}\mathbf{}\mathbf{y}$ must be nonempty when the string$\mathbf{S}$ is broken up.

If $\mathbf{A}$is a context-free language, then there is a number k where, if s is any string in$\mathbf{A}$ of length at least$\mathbf{k}$ , then s may be divided into five pieces,role="math" localid="1659706026393" $\mathbf{s}\mathbf{=}\mathbf{uvxyz}$ , satisfying the conditions:

role="math" localid="1659706054658" $\begin{array}{l}\mathbf{a}\mathbf{.}\mathbf{}\mathbf{for}\mathbf{}\mathbf{each}\mathbf{}\mathbf{i}\mathbf{\ge }\mathbf{0}\mathbf{,}{\mathbf{uv}}^{\mathbf{i}}{\mathbf{xy}}^{\mathbf{i}}\mathbf{z}\mathbf{\in }\mathbf{A}\mathbf{,}\\ \mathbf{b}\mathbf{.}\mathbf{v}\mathbf{\ne }\mathbf{\epsilon }\mathbf{}\mathbf{and}\mathbf{}\mathbf{y}\mathbf{\ne }\mathbf{\epsilon }\mathbf{,}\mathbf{and}\\ \mathbf{c}\mathbf{.}\mathbf{\left|}\mathbf{vxy}\mathbf{\right|}\mathbf{\le }\mathbf{k}\mathbf{,}\end{array}$

Short answer

$\begin{array}{l}\mathrm{a}).\mathrm{for}\mathrm{each}i\ge 0,{\mathrm{uv}}^{\mathrm{i}}{\mathrm{xy}}^{\mathrm{i}}\mathrm{z}\in \mathrm{A},\mathrm{is}\mathrm{proved}.\\ \mathrm{b}).\mathrm{v}\ne \mathrm{\epsilon andy}\ne \mathrm{\epsilon },\mathrm{isprovedand}\\ \mathrm{c}).\left|\mathrm{vxy}\right|\ge \mathrm{k},\mathrm{is}\mathrm{proved}\mathrm{by}\mathrm{pumping}\mathrm{lemma}\mathrm{for}\mathrm{CFG}\end{array}$

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$\mathrm{L}$is zeros and one’s. where$\mathrm{Z}$is belongs to$\mathrm{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}{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

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

Therefore, L is not context free language.2

Step 2: Pumping lemma for context-free languages.a)

If $\mathrm{A}$is a context-free language, then there is a number p (the pumping length) where, if s is any string in $\mathrm{A}$of length at least p, then s may be divided into five pieces $\mathrm{s}=\mathrm{uvxyz}$satisfying the conditions.

$\begin{array}{l}\\ 1.\mathrm{foreachi}\ge 0,\mathrm{uvixyiz}\in \mathrm{A},\\ 2.\left|\mathrm{vy}\right|>0,\mathrm{and}\\ 3.\left|\mathrm{vxy}\right|\le \mathrm{p}.\\ \end{array}$

When s is being divided into $\mathrm{uvxyz}$, condition two says that either $\mathrm{v}\mathrm{or}\mathrm{y}$is not the empty string. Otherwise the theorem would be trivially true. Condition three.

states that the pieces$\mathrm{v},\mathrm{x},\mathrm{and}\mathrm{y}$ together have length at most $\mathrm{p}$. This technical condition sometimes is useful in proving that certain languages are not context free.

$\mathrm{for}\mathrm{each}\mathrm{i}\ge 0,\mathrm{uvixyiz}\in \mathrm{A}$hence, this condition is proved as for each and every$\mathrm{i}$ is greater than or equals to zero and its each and every element is belongs to $\mathrm{A}$.

Step 3: Pumping lemma for context-free languages.b)

Let $\mathrm{A}$be a context free language and let $\mathrm{G}$be a context free grammer that generates it. We must show that any sufficiently long string s in $\mathrm{A}$can be pumped and remain in $\mathrm{A}$. The idea behind this approach is simple. Let s be a very long string in $\mathrm{A}$. (We make clear later what we mean by “very long.”) Because string is in $\mathrm{A}$,

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

it is derivable from that grammar and so has a parse tree.

The parse tree for s must be very tall because s is very long. That is, the parse tree must contain some long path from the start variable at the root of the tree called at the source node or source vertex to one of the terminal symbols at a leaf.

On this long path, some variable symbol$\mathrm{R}$ must repeat because of the pigeonhole principle.

$\mathrm{v}\ne \mathrm{\epsilon }\mathrm{and}\mathrm{y}\ne \mathrm{\epsilon },$hence, this condition is valid for the pumping lemma in context free language and with its string made by context free grammar.

Step 4: Pumping lemma for context-free languages.c)

As the following figure shows, this repetition allows us to replace the subtree under the second occurrence of $\mathrm{R}$ with the subtree under the first occurrence of $\mathrm{R}$and still get a legal parse tree. Therefore, we may cut the string into five pieces $\mathrm{uvxyz}$as the figure indicates, and we may repeat the second and fourth pieces and obtain a string still in the language. In other words,

${\mathrm{uv}}^{\mathrm{i}}{\mathrm{xy}}^{\mathrm{i}}\mathrm{z}$ is in A for any $\mathrm{i}\ge 0.$

When s is being divided into $\mathrm{uvxyz}$, condition two says that either$\mathrm{v}\mathrm{or}\mathrm{y}$ is not the empty string. Otherwise the theorem would be trivially true. Condition three.

states that the pieces$\mathrm{v},\mathrm{x},\mathrm{and}\mathrm{y}$ together have length at most$\mathrm{p}$ . This technical condition sometimes is useful in proving that certain languages are not context free.

$\left|\mathrm{vxy}\right|\le \mathrm{k}$, hencethis condition is valid for the pumping lemma in context free language and with its string made by context free grammar.