Pumping lemma errors usually come from reversing who chooses p, the string, the split, and the exponent. The adversary fixes p and then the split; you choose only the witness string w and the exponent i. Reverse that order and a regular language will look non-regular, or a non-regular one will walk straight through your proof. Commit to an option before reading each explanation. If the quantifiers feel slippery, start with the pumping lemma refresher.
Fix the pumping lemma quantifiers before solving
If L is regular, some pumping length p lets every w in L with |w| >= p be split as w = xyz, where |xy| <= p, |y| >= 1, and xy^i z in L for every integer i >= 0. For finite L, set p above its maximum string length.
To prove non-regularity, receive arbitrary p, choose w, handle every valid opponent-selected split, then choose i that sends the result outside L. One convenient y proves nothing.
For L_eq = {a^n b^n | n >= 0}, calibrate with p = 5 and w = a^5b^5. Since |xy| <= 5, every legal y is a^t, where 1 <= t <= 5. With i = 0, the result is a^(5-t)b^5; for t = 3, this is a^2b^5, outside L_eq. Replace 5 by arbitrary p to complete the proof. No finite automaton can hold the unbounded count that this equality needs.
Pumping Lemma MCQs 1-3: purpose, the nonempty loop, and pigeonholes
Question 1, UGC NET 2017
Pumping lemma for regular language is generally used for proving :
A. whether two given regular expressions are equivalent
B. a given grammar is ambiguous
C. a given grammar is regular
D. a given grammar is not regular
Answer: D. a given grammar is not regular.
The lemma applies to the grammar's language. Its necessary condition supports a contradiction proving non-regularity, but one pumpable split cannot prove regularity.
Question 2, UGC NET 2022
In Pumping Lemma for regular languages, to say a language is satisfying pumping lemma, what is the minimum length of ' y ' if you consider the string as ' xyz '.
A. n
B. 2
C. 1
D. 0
The loop obeys |y| >= 1; an empty y leaves the string unchanged under pumping, so the lemma would assert nothing at all. In the a^5b^5 split above, the shortest legal loop is y = a, with x empty and z = a^4b^5.
Question 3, UGC NET 2017
The logic of pumping lemma is an example of __________ .
A. iteration
B. recursion
C. the divide and conquer principle
D. the pigeon - hole principle
Answer: D. the pigeon - hole principle.
A DFA with p = 5 states visits six state positions while reading five symbols, including its start. Two positions share a state; the nonempty input between them is repeatable y.
Pumping Lemma MCQs 4-6: finite languages, pumping lengths, and the converse trap
Question 4, HPSC 2021
For a language whose strings never exceed length x, what is the smallest pumping length p guaranteed by the pumping lemma?
A. x+1
B. x
C. x-1
D. x^2
Set p = x + 1; no w in L reaches length p, so the condition holds vacuously. Taking p = x instead would still oblige every string of length exactly x to pump, which a finite language cannot promise. For x = 7, p = 8, and no string needs testing.
Question 5, GATE 2019
For Σ = {𝑎, 𝑏}, let us consider the regular language 𝐿 = { 𝑥 |𝑥 = 𝑎^(2+3𝑘) or 𝑥 = 𝑏^(10+12𝑘) , 𝑘 ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for 𝐿 ?
A. 3
B. 5
C. 9
D. 24
For a^26, choose a three-symbol loop, giving length 26 + 3(i-1), still 2 modulo 3. For b^34, choose a 12-symbol loop, giving 34 + 12(i-1), still 10 modulo 12. Both branches therefore pump for every i >= 0. Values 3, 5, and 9 fail on b^10 because they cannot contain a 12-symbol loop.
Question 6, GATE 2005
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 context-free language, but not necessarily a regular language
C. L is necessarily a non-regular language
D. None of the above
Both pumping properties are necessary, not sufficient. Passing them does not establish that L is regular or context-free, nor does it prove non-regularity.
Pumping Lemma MCQs 7-9: classify languages before choosing a proof
Question 7, GATE 2001
Consider the following languages:
L1 = { ww | w ∈ {a, b}* }
L2 = { ww^R | w ∈ {a, b}+, w^R is the reverse of w }
L3 = { 0^(2i) | i is an integer }
L4 = { 0^(i^2) | i is an integer }
Which of the languages are regular?
A. Only L1 and L2
B. Only L2, L3 and L4
C. Only L3 and L4
D. Only L3
L3 is the even-length unary language. L1 copies a word, and L2 requires an even palindrome. For L4, choose 0^(p^2). Pumping up adds d, where 1 <= d <= p, placing the new length strictly between p^2 and (p+1)^2, so it is not square.
Question 8, UGC NET 2021
Which of the following languages are not regular?
A. L={ (01)^n 0^k | n > k, k>=0 }
B. L={ c^n b^k a^(n+k) | n >= 0, k>=0 }
C. L={ 0^n 1^k | n≠k }
Choose the correct answer from the options given below:
A. A and B only
B. A and C only
C. B and C only
D. A, B and C
For A, use (01)^p0^(p-1) and pump down. An aligned deletion makes n <= k; any partial deletion breaks the repeated form. For B, use c^p b^p a^(2p) and remove initial c symbols. For C, regularity plus complement inside 0*1* would make {0^n1^n} regular. Each route contradicts regularity.
Question 9, GATE 1996
Let L be a language over Sigma = {a, b}. Which of the following statements is true?
A. L = {x | x has an equal number of a and b symbols} is regular
B. L = {a^n b^n | n >= 1} is regular
C. L = {x | x has more a symbols than b symbols} is regular
D. L = {a^m b^n | m >= 1, n >= 1} is regular
Answer: D. L = {a^m b^n | m >= 1, n >= 1} is regular.
Option D is a+b+; ab, aaab, and aabbbb all match without comparing counts. A, B, and C require unbounded count balances that a finite automaton cannot store.
Pumping Lemma MCQs 10-12: paired languages and comparison constraints
Question 10, UGC NET 2013
Consider the following two languages:
L₁ = { aⁿ bˡ aᵏ | n + l + k > 5 }
L₂ = { aⁿ bˡ aᵏ | n > 5, l > 3, k ≤ l }
Which of the following is true?
A. L₁ is regular language and L₂ is not regular language
B. Both L₁ and L₂ are regular languages
C. Both L₁ and L₂ are not regular languages
D. L₁ is not regular language and L₂ is regular language
Answer: A. L₁ is regular language and L₂ is not regular language.
L1 is a*b*a* minus the finitely many strings of length 5 or less, so a DFA that counts up to 6 and then stops counting decides it. For L2 take w = a^6 b^(p+4) a^(p+4), which sits in L2 for every p because 6 > 5, p + 4 > 3, and k equals l. Since |xy| <= p, the loop is a run of a's from the opening block, a run of b's, or a block straddling the a-to-b boundary. Setting i = 0 leaves fewer than six leading a's in the first case and drops l below k = p + 4 in the second, while i = 2 in the third plants a second a-block before the b's, a shape no string of a*b*a* has. Every legal split leaves L2.
Question 11, UGC NET 2016
Given the following two languages:
L₁ = { u w wᴿ v | u, v, w ∈ {a, b}⁺ }
L₂ = { u w wᴿ v | u, v, w ∈ {a, b}⁺, |u| > |v| }
Which of the following is correct?
A. L₁ is regular language and L₂ is not regular language
B. L₁ is not regular language and L₂ is regular language
C. Both L₁ and L₂ are regular languages
D. Both L₁ and L₂ are not regular languages
Answer: A. L₁ is regular language and L₂ is not regular language.
Every ww^R repeats the last symbol of w at its centre, so L1 is exactly the strings carrying a doubled letter with at least one symbol on each side: (a|b)+(aa|bb)(a|b)+, which a DFA recognises. L2 adds the comparison |u| > |v|. Intersect it with the regular set (ab)+aa(ba)+, where the central aa is the only doubled letter, so any legal reading of (ab)^n aa (ba)^m has to centre the palindrome there. If that palindrome has length 2k, then |u| = 2n + 1 - k and |v| = 2m + 1 - k, and membership reduces to n > m. Regular languages are closed under intersection, and no finite automaton can decide { (ab)^n aa (ba)^m | n > m }, so L2 is not regular.
Question 12, UGC NET 2014
Given two languages :
L1 = {(ab)n ak | n > k, k ≥ 0}
L2 = {an bm | n ≠ m} Using pumping lemma for regular language, it can be shown that
A. L1 is regular and L2 is not regular.
B. L1 is not regular and L2 is regular.
C. L1 is regular and L2 is regular.
D. L1 is not regular and L2 is not regular.
Answer: D. L1 is not regular and L2 is not regular.
Here (ab)n and ak denote (ab)^n and a^k. For L1, use (ab)^p a^(p-1); pumping down either breaks the repeated form or makes n <= k. If L2 were regular, its complement inside regular a*b* would be {a^n b^n}, which is non-regular. Closure supplies the contradiction, so both are non-regular.
The short version and next practice step
A finite automaton can hold a fixed threshold, so counting up to a constant, testing a length modulo a constant, and spotting a doubled letter all stay regular. Unbounded comparison does not survive: equality of two counts, copying a word, reversing it, and landing on a perfect square each fall to the lemma. Continue with Finite Automata MCQs, then place the topic in GATE CS Exam Preparation.
Redo Questions 2, 4, and 5 for pumping lengths, then Questions 7, 8, and 12 with a witness and chosen i. Use GATE Guidance by Sanchit Sir for the full Theory of Computation path and the GATE Test Series for timed practice. In every proof, cover every legal split.
