in Theory of Computation edited by
1,660 views
1 vote
1 vote
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$.$ $\text{(See the analogous example for regular languages in Question 54.)}$
in Theory of Computation edited by
by
1.7k views

1 Answer

4 votes
4 votes
Best answer

A language that is not context free but that acts like a $CFL$ in the pumping lemma :

Basically it wants some Non-CFL language which satisfies the "Pumping lemma for CFLs". Let me give such language along with some extra amount of facts which might be interesting to know.


The pumping lemma for regular languages states : If $L$ is a regular language then there exists a positive integer $P>0 (pumping\,\, length\,/\,\,constant)$, such that for any $x∈L$ with $|x|≥P$ there exist strings $u,v,w$  such that $x=uvw$ , $|uv|≤P$ , $|v|>0$ and for all $m≥0$ , $uv^mw∈L$.

The pumping lemma for context free languages states : If $L$ is context free then there exists a positive integer $P>0 (pumping\,\, length\,/\,\,constant)$ such that for any $x∈L$ with $|x|≥P$ there exist strings $v,w,x,y,z$ such that $u=vwxyz$, $|wxy|≤P$ , $|wy|>0$  and for all $m≥0$ , $uw^mxy^mz∈L$.

Now, if a language $L$ satisfies the conclusion/condition of the pumping lemma for regular languages, then it also satisfies the conclusion/condition of the pumping lemma for context free languages by picking $v=w=ϵ$ and $x=u$  and $y=v$  and $z=w$, where $u,v,w$  are strings from the conclusion/condition of the pumping lemma for regular languages.

And so, contrapositive,  If the conclusion/condition of the pumping lemma for context free languages fails for a particular language $L$ then the language cannot be regular, because the conclusion/condition of the pumping lemma for regular languages must fail for $L$.

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. 

Consider the following language  over $\Sigma = \{ a,b,c,d \}$ : 

$L = \{ a b^nc^nd^n| n \geq1 \}  \cup \,\, \{a^ i w | w \in \{ b,c,d \}^* \wedge i \neq 1 \} $ 

$L$ is Non-regular,Non-CFL (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- CFL, satisfies Pumping lemma of Regular languages. And Pumping length $P \geq 2$ will work for it. Let’s write $L$ as Union of two languages $A,B$ i.e. $A = \{ a b^nc^nd^n| n \geq1 \}$ and $B =  \{a^ i w |  w \in \{ b,c ,d\}^* \wedge i \neq 1 \}$

Let $P = 10$ be the pumping lemma constant, so now pick any string $s$ from $L$ of length $\geq P$, 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 CFLs. But $L$ is Non-CFL. So, A Non-CFL may satisfy both the Pumping lemma conditions(of Regular and CFL).


Refer Here for a GATE question involving around the ideas shared in this above answer :

https://gateoverflow.in/3787/gate2005-it-40?show=296671#a296671


$\color{Red}{\text{Understand Complete Pumping Lemma of Regular Languages, Crystal Clear:}}$

Here is Complete Pumping Lemma Lecture: https://youtu.be/8cdPjuYbIrU 

This Pumping Lemma lecture contains EVERYTHING about Pumping Lemma of Regular Languages, i.e. Proof, Examples, Variations, GATE PYQs, Finding minimum pumping length etc. Watch this lecture for Complete, Correct & Clear Understanding.

edited by

3 Comments

@Deepakk Poonia (Dee)

how i this language $L = \{ a b^nc^nd^n| n \geq1 \}  \cup \,\, \{a^ i w | w \in \{ b,c,d \}^* \wedge i \neq 1 \} $ r u getting pumping length $2$?

Can u explain a bit more??

0
0

@srestha

MPL will be 2

see this

https://gateoverflow.in/311034/michael-sipser-edition-3-exercise-1-question-54-page-no-91?show=311034#q311034

for w=uvxyz

I take u=v=x=ε and y=aa, z=bc(or b or c or ε)

here the pumping string is aa

so for all i$\geq$0 w belongs to L

 

1
1
yes....
0
0

Related questions