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

Updated 3 Nov 20266 min read
Pumping Lemma for Regular Languages: Quantifiers, Worked Proofs and GATE Traps

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.

Five numbered boxes show the pumping-lemma contradiction order, from assuming regularity through choosing p, w, each split, and i = 0.

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 w starts with 1, choose x = epsilon, y = 1.

  • If it starts with 00, choose x = epsilon, y = 00.

  • If it starts with 01, choose x = 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.

A split diagram for p = 4 and k = 2 shows x, y, z, deletion at i = 0, resulting counts, and the i = 2 audit.

Witness and pumping-index choices follow repeatable patterns

Useful patterns are:

Language shape

Witness

Forced y

Useful i

{0^n 1^(2n) | n >= 0}

0^p 1^(2p)

0^k, 1 <= k <= p

0

{0^m 1^n | m < n}

0^p 1^(p+1)

0^k, 1 <= k <= p

2

{0^(n^2) | n >= 0}

0^(p^2)

0^k, 1 <= k <= p

2

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 y

Covers only one split

Describe every valid split

Checking one numerical p

Leaves other lengths open

Keep p arbitrary

Choosing i = 1

Returns w

Try 0, 2 or another useful value

Forgetting |xy| <= p

Loses control of y

Apply the prefix bound

Allowing y = epsilon

Makes no change

Enforce |y| > 0

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:

  1. State the regularity assumption and arbitrary p.

  2. Choose a long witness in L.

  3. Describe every valid split with |xy| <= p and |y| > 0.

  4. Choose an i.

  5. 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.