context-free-grammarfinite-automatapumping-lemma

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


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.


Solution

  • 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!