Pumping lemma is used to show a language is non-regular /non-CFL.

2
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 ?

A. L is necessarily a regular language.

B. L is necessarily a CFL but not Regular.

C. L is necessarily a non-regular.

D. None

I'll clear where I'm having doubt. If L satisfies pumping lemma for regular languages then it is not necessarily regular. Same with context free. So it can be Regular or non-regular. CFL or non-CFL. Answer given is B but in my opinion it should be D. Can anyone point out what I'm missing.

2
context-free-grammarfinite-automatapumping-lemma
Erm.. this site isn't a way of getting people to do your homework for free you know. – Ben Clayton
This isn't my homework. I'm having doubt in this question. I know if a language satisfies pumping lemma for regular language then it is not necessary that it is regular. – Prashant Bhardwaj
"Answer given is B but in my opinion it should be B. Can anyone point out what I'm missing." - You seem to be missing that if the answer given is B and in your opinion it should be B, then nothing seems to be missing. – Prateek
Sorry my mistake I edited the question. In my opinion answer should be D. – Prashant Bhardwaj
It seems this question would be better suited at cs.stackexchange.com (It also reads like a homework/exam question.) – Fizz

2 Answers

1
votes

Answer B is definitely not right. Try the language Σ*, which is absolutely regular and definitely context-free. It also passes the conditions of both pumping lemmas. Therefore, it's definitely not the case that the language is context-free but not regular.

Both pumping lemmas give necessary conditions for a language to be regular or context-free, rather than sufficient conditions for those languages to be regular or context-free. Therefore, if a language passes both of the pumping lemmas, it might be regular and it might be context-free, but there's no guarantee that this must necessarily be the case.

I'm pretty sure D is the correct choice here.

Hope this helps!

0
votes

Hint:

  1. Pumping Lemma: ¬q → ¬p where, q is pumping lemma and p is regular language. It is Contrapositive that means if a language does not satisfies pumping lemma, then it can not be regular language. It is always true.
  2. Then, it is also correct that p → q. It is implication that means if a language is regular then it is always satisfies pumping lemma.

Also, note that its inverse ¬p → ¬q and converse q → p need not be true according to prepositional logic.