edited by
14,846 views
29 votes
29 votes

A language $L$ satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about $L$ is TRUE?

  1. $L$ is necessarily a regular language.
  2. $L$ is necessarily a context-free language, but not necessarily a regular language.
  3. $L$ is necessarily a non-regular language.
  4. None of the above
edited by

4 Answers

Best answer
35 votes
35 votes

Answer is (D). If a language is regular, it definitely satisfies pumping lemma. But converse need not  be true. If a language satisfies pumping lemma then it may or may not be regular.

edited by
33 votes
33 votes
By pumping lemma we can never say that a language is regular or cfg .it can only be used to prove that a certain lang is not reg or not cfg
18 votes
18 votes

Answer : D


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).


$\color{Red}{\text{Understand Complete Pumping Lemma, 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
10 votes
10 votes

Answer is (D)

Satisfying  pumping lemma does not prove anything.

Answer:

Related questions

23 votes
23 votes
1 answer
1
Ishrat Jahan asked Nov 3, 2014
6,378 views
The language $\{0^n 1^n 2^n \mid 1 \leq n \leq 10^6\}$ isregularcontext-free but not regularcontext-free but its complement is not context-freenot context-free
41 votes
41 votes
3 answers
2
30 votes
30 votes
5 answers
4
Ishrat Jahan asked Nov 3, 2014
9,233 views
Let $T(n)$ be a function defined by the recurrence$T(n) = 2T(n/2) + \sqrt n$ for $n \geq 2$ and$T(1) = 1$Which of the following statements is TRUE?$T(n) = \Theta(\log n)$...