GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 1

Question

Which of the following statements is/are TRUE regarding pumping lemma for regular languages? (Mark all the appropriate choices)

• A. Satisfying pumping lemma is a necessary condition for a language to be regular
• B. Satisfying pumping lemma is a sufficient condition for a language to be regular
• C. Not satisfying pumping lemma is a necessary condition for a language to be not regular
• D. Not satisfying pumping lemma is a sufficient condition for a language to be not regular

Answer 1

Pumping Lemma for Regular Languages is as follows:

If $A$ is a regular language, then there is a number $p,$ such that if $s$ is any string in $A$ of length at least $p,$ $s$ may be divided into three pieces $x,y,z,$ i.e., $s = xyz,$ such that all of the following hold:

1. for each $i \geq 0, xy^i z$ is in $A$
2. $|y| > 0$
3. $|xy| \leq p$

So, pumping lemma is a necessary condition for a language to be regular. In other words, not satisfying pumping lemma is a sufficient condition for a language to be not regular.

Now, even if a language satisfies pumping lemma it may not be regular.

Reference: https://cs.stackexchange.com/questions/41442/a-non-regular-language-satisfying-the-pumping-lemma

So, correct answer is A and D

Comments

there should necessarily exist some string w in L such that pumping lemma is not satisfied.

Pumping lemma is for a LANGUAGE – so what’s the meaning of saying it is not satisfied for a string.

---

@Arjun sir, is there a regular language which does not satisfy pumping lemma and still a regular language? 

---

pumping lemma is a necessary condition for a language to be regular

This statement should answer that