Question

Give an example of a language that is not context free but that acts like a CFL in the pumping lemma. Prove that your example works. (See the analogous example for regular languages in Problem 1.54.)

Short answer

Pumping lemma for context free language is proved.

Step-by-step solution

Pumping lemma

If a string v is 'pumped', if v is inserted any number of times, the resultant string still remains in language. Pumping Lemma is used as a proof for irregularity of a language.

Pumping lemma for regular languages states

Here thepumping lemma is used to find the language is regular language or not.

(a) Assume B is regular language and their L is 0s and 1s. where, Z is belongs to L.

|z|$\ge$n

z=uvwxy

|v|$\ge$1

Here at least 1 is not null.

b) Find a suitable k so that $u{v}^{k}w{x}^{k}y\notin L$so L is not regular language.

L=$\left\{a^n{b}^n{c}^n|n\ge 0\right\}$

z=uvwxy,

z=$a^n{b}^n{c}^n${n=1,z=abc}

|z|=3n>n

If we equate both z then we get,

uvwxy=$a^n{b}^n{c}^n$

|vx|$\ge$1,{n$\ge$|vx|$\ge$1}

Then after that,

Let v or x is a part of -
localid="1662024162464" $\left(a^i{b}^j\right)or(b^i{c}^{j)}$u

localid="1662024188292" $v=\left(a^i{b}^j\right)$

localid="1662099738781" $v^2=\left(a^i{b}^j\right)\left(b^i{c}^j\right)$
$u{v}^{2}w{x}^{2}y=a^m{b}^m{c}^m$

From this equation, it is proof that

$u{v}^{2}w{x}^{2}y\notin L$

Therefore, L is not regular language.

However, this also follows from the fact that any regular language is context free and

in fact can be given by a very simple grammar, called a regular grammar. So, if the

conclusion of the pumping lemma for context free languages fails, then the language

is not context free, which also means that it is not regular.

Explanation with example

Consider the following language over Σ= {a,b,c,d)

$L=\left\{a{b}^n{c}^n{d}^n|n\ge 1\right\}\cup \left\{a^{i}w|w\in \left\{b,c,d\right\}*\notin 1\right\}$

L is Non-regular, On context free language (because if the string starts with a single

a

then after it the number of b,c,d should be equal and in that order.),

L , though, Not Regular and Non context free language, satisfies Pumping lemma of

Regular languages.

And Pumping Length $P\ge 2$ will work for it.

Let’s write L as Union of two languages A,B i.e.
localid="1662033940796" $A=\left\{a{b}^n{c}^c{d}^n|n\ge 1\right\}$and

B={ a i w |w∈{b, c,d}∗∧i≠1}

Let P=10 be the pumping lemma constant, so now pick any string s from L of

length $P\ge 2$, there will be two cases here:

s is chosen from B , then we can pick the first two symbols from s to pump.

s is chosen from A , then we can pick the first symbol i.e. a , to pump.

Hence, L satisfies the pumping lemma condition of Regular languages. So, it will

also satisfy the pumping lemma condition of context free languages.

But, L is non context free language.

So, A Non context free language may satisfy both the pumping lemma conditions

(of Regular and context free language).