Pumping Lemma for Regular Languages: Quantifiers, Worked Proofs and GATE Traps
Learn who chooses the pumping length, witness, split and index. Then follow two checked examples and a reusable method for proving a language is not regular.
KnowledgeGate Team
Exam prep & CS education

The pumping operation is simple, but the proof game feels backwards. You control the witness and, later, the pumping index, while the decomposition must survive every valid adversarial choice. The quantifier order turns that tension into a repeatable method: first test a regular language, then complete a non-regularity proof.
Pumping lemma for regular languages: the exact statement and its limits
If L is regular, there exists an integer p >= 1 such that every string w in L with |w| >= p can be written w = xyz, where |xy| <= p, |y| > 0, and xy^i z in L for every integer i >= 0.
Here, p is a pumping length, y is the non-empty repeated segment, and i = 0 deletes y.
This implication is one-way. A violation proves non-regularity, but passing an exercise does not prove regularity. Use a DFA, regular expression or closure construction for a positive proof. Decision Properties of Regular Languages: DFA TestsThat sibling owns the closure and decision-property toolkit; this post focuses on pumping-lemma quantifiers and witnesses.
Each condition has a job. |xy| <= p confines y to the first p symbols, |y| > 0 forces change, and for every i >= 0 permits i = 0, 2 or another useful value.
Pumping lemma quantifiers decide who is allowed to choose what
exists p, for every long w, there exists a valid split x,y,z, for every i >= 0.
For a contradiction proof, assume regularity. The lemma supplies an arbitrary p; you choose w; you cover every split satisfying both length conditions; after describing a general split, you choose one i that pushes the result outside L.
Negating the property gives the exact target: for every p, there exists w in L with |w| >= p, such that for every valid split w = xyz, there exists i >= 0 with xy^i z not in L. You never get to choose a convenient y in a non-regularity proof.
A regular-expression proof can provide a positive construction; this post concentrates on quantifier control and alternate pumping examples.

Pumping a regular language first clarifies the mechanics
Consider E = {w in {0,1}* | w contains an even number of 0s} and choose pumping length p = 2. For every w in E of length at least 2, inspect its prefix:
If
wstarts with1, choosex = epsilon, y = 1.If it starts with
00, choosex = epsilon, y = 00.If it starts with
01, choosex = 0, y = 1.
Each split has |xy| <= 2 and |y| > 0. Pumping changes the zero count by 0 or an even number, preserving membership for every i >= 0.
For w = 1001, take x = epsilon, y = 1, and z = 001. Values i = 0, 1, and 2 give 001, 1001, and 11001. Each has two zeros and remains in E.
The split may depend on w. This does not reverse the lemma to prove regularity. The two-state even-or-odd-zero DFA is the positive proof. Regularity Identification in Automata Theory: DFA/NFA Tests and Worked Proofs chooses among DFA, closure and pumping approaches; this post stays with the pumping lemma's quantifier order and witness construction.
Pumping lemma worked proof: 0^n 1^(2n) is not regular
Define L = {0^n 1^(2n) | n >= 0}. Assume that L is regular and let p be its pumping length. Choose
w = 0^p 1^(2p).
This string belongs to L, and |w| = p + 2p = 3p >= p. Now take an arbitrary valid split w = xyz. Since |xy| <= p, both x and the non-empty y lie entirely inside the leading zero block. Therefore, y = 0^k for some 1 <= k <= p.
Pump down with i = 0. The resulting string is
xz = 0^(p-k) 1^(2p).
For this string to belong to L, the number of ones would have to equal twice the number of zeros. That would require 2p = 2(p-k), which simplifies to k = 0. This contradicts k >= 1. The argument covers every k from 1 through p, so every valid decomposition fails. Hence L is not regular.
A concrete check with p = 4 and k = 2 makes the contradiction visible. Then w = 000011111111, with x = 00, y = 00, and z = 11111111. Pumping with i = 0 gives 0011111111. It has 2 zeros and 8 ones, but membership would require 2 x 2 = 4 ones. Pumping with i = 2 gives 00000011111111. It has 6 zeros and 8 ones, but membership would require 2 x 6 = 12 ones. This numerical split illustrates the failure. The symbolic 1 <= k <= p argument is what completes the proof.

Witness and pumping-index choices follow repeatable patterns
Useful patterns are:
Language shape | Witness | Forced | Useful |
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
In row two, pumping gives p + k >= p + 1 zeros, destroying m < n. In row three, p^2 + k lies strictly between p^2 and (p+1)^2 = p^2 + 2p + 1, so it is not a square.
Choose w before the split, express every y with a variable such as k, then choose i to break the invariant. One failed witness proves nothing. If a valid decomposition pumps for every i, find a stronger witness or another technique.
Pumping lemma traps and the exact repair for each
Trap | Error | Repair |
|---|---|---|
Choosing | Covers only one split | Describe every valid split |
Checking one numerical | Leaves other lengths open | Keep |
Choosing | Returns | Try |
Forgetting | Loses control of | Apply the prefix bound |
Allowing | Makes no change | Enforce |
Claiming the property proves regularity | Reverses the implication | Use a DFA, regular expression or closure proof |
Using the three-part xyz split for a context-free language ignores its separate five-part lemma. If closure or Myhill-Nerode is shorter, pumping adds needless casework. Identify the language class and proof direction first.
Use this self-check: Did I choose only p, w or y that the quantifier order actually lets me choose, and did I cover every permitted decomposition?
How exam questions test the pumping lemma without always asking for a full proof
Question shapes include identifying the valid theorem, finding a split that violates |xy| <= p or |y| > 0, completing a missing witness or index, and detecting the false converse. Two quick checks help: i = 1 returns the original string, while i = 0 deletes y.
For a mini-check, let p = 5 and w = 000001111111111 in {0^n1^(2n)}. A proposed y = 01 cannot satisfy |xy| <= 5, because the first five symbols are all 0. Every valid non-empty y must be 0^k with 1 <= k <= 5.
KnowledgeGate has over 20 Pumping Lemma questions for practice. GATE CS & IT 2027 Guidance by Sanchit Sir provides a structured wider GATE CS route, while All Courses is the broader exam hub.
Pumping lemma proof checklist and the next step
Use this five-step checklist:
State the regularity assumption and arbitrary
p.Choose a long witness in
L.Describe every valid split with
|xy| <= pand|y| > 0.Choose an
i.Show that the pumped string violates the language definition.
Violation proves non-regularity; satisfaction does not. Continue with the GATE CS Theory of Computation Course | PYQs. Alternatively, reproduce the proof using p = 5, k = 3, x = 00, y = 000, and z = 1111111111. At i = 0, xz has 2 zeros and 10 ones, so it is outside L.
Keep learning
Regular expressions and the pumping lemma, with the exam angle
Regular expressions and the pumping lemma explained: the operators, closure properties, and a worked proof that a^n b^n is not regular, with the exam angle.
Pumping Lemma MCQs: 12 Solved Questions with Explanations
Twelve GATE, UGC NET and HPSC pumping lemma MCQs, worked with concrete witness strings, every legal split handled, and closure arguments where they are needed.
Closure Properties of Regular, Context-Free and Recursive Languages for GATE: The Complete Table with MSQ Drills
Learn the closure table through the few cells that cause most mistakes, then test the logic on four solved MSQ statements.
Decidability in Regular Languages: DFA Tests, Worked Example and Exam Traps
Learn why DFA decision problems halt, how graph searches settle key language properties, and how a product automaton exposes the counterexample 10.





