47.01.04 · theoretical-cs / formal-languages-automata

Pumping Lemma for Regular Languages: Proving Non-Regularity

shipped3 tiersLean: nonepending prereqs

Anchor (Master): Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §1.4; Hopcroft, Motwani & Ullman 2006 Introduction to Automata Theory, Languages, and Computation 3e (Pearson) §2.4 (Myhill-Nerode characterisation as the structural reason behind the pumping lemma, closure properties under homomorphism)

Intuition Beginner

Imagine a hotel with only five rooms. Six guests arrive, each needing a private room. By the pigeonhole principle, at least two guests must share a room. No matter how you assign the rooms, you cannot give each guest a separate one.

A DFA faces the same problem. It has a fixed number of states. When it reads a long string, it passes through many states — one per symbol. If the string is longer than the number of states, some state gets visited twice. The DFA has looped back on itself.

That loop is the key. The substring that caused the DFA to go around the loop can be repeated any number of times, or skipped entirely, and the DFA will still end up in the same final state. The string "pumps" through the loop.

This is the pumping lemma. It says: in any regular language, every sufficiently long string contains a loop that can be pumped. If you can find a language where pumping breaks things — where repeating a substring kicks you out of the language — then that language is not regular.

For example, the language of all strings with equal numbers of 0s and 1s is not regular. A DFA has finite memory. It cannot count arbitrarily high to verify that the number of 0s matches the number of 1s. The pumping lemma turns this intuition into a rigorous proof.

Visual Beginner

A DFA reading a long string must revisit a state:

States:  q0 → q1 → q2 → q3 → q2 → q4
Symbols:  a    b    c    d    e    f
                       ↑         ↑
                       └── y ────┘
                 ↑↑↑          ↑↑↑
                  x            z

String s = abcdef, with y = de (the loop).
s = xyz where:
  x = abc  (leads to first visit of q2)
  y = de   (loop: q2 → q3 → q2)
  z = f    (continues from q2)

Pumping the loop:

Version	String	In language?
$x y^{0} z = x z$	abcf	Depends on language
$x y^{1} z = x y z$	abcdef	Yes (original)
$x y^{2} z = x y y z$	abcdedef	Depends on language
$x y^{3} z = x y y y z$	abcdedededef	Depends on language

The pumping lemma guarantees that if the original string is in a regular language, then all pumped versions are also in the language. If any pumped version escapes, the language is not regular.

Worked example Beginner

We prove that $L = {0^{n} 1^{n} : n \geq 0}$ is not regular.

Suppose for contradiction that $L$ is regular. Then there is a pumping length $p$ . Consider the string $s = 0^{p} 1^{p}$ (that is, $p$ zeroes followed by $p$ ones). This string is in $L$ and has length $2 p \geq p$ .

By the pumping lemma, we can write $s = x y z$ where $∣ y ∣ > 0$ , $∣ x y ∣ \leq p$ , and $x y^{i} z \in L$ for all $i \geq 0$ .

Since $∣ x y ∣ \leq p$ , the substring $x y$ lies entirely within the first $p$ symbols. So $y$ consists only of 0s. Say $y = 0^{k}$ for some $k \geq 1$ .

Now pump down: consider $x y^{0} z = x z$ . This removes $k$ zeroes from the string, giving $0^{p - k} 1^{p}$ . But $p - k \neq = p$ (because $k \geq 1$ ), so this string has fewer 0s than 1s. It is not in $L$ .

This contradicts the pumping lemma. So $L$ is not regular.

Check your understanding Beginner

Formal definition Intermediate+

Lemma (Pumping lemma for regular languages). Let $L$ be a regular language. Then there exists a constant $p \geq 1$ (the pumping length) such that every string $s \in L$ with $∣ s ∣ \geq p$ can be written as $s = x y z$ where:

For each $i \geq 0$ , $x y^{i} z \in L$ .
$∣ y ∣ > 0$ (the pumpable part is nonempty).
$∣ x y ∣ \leq p$ (the loop occurs within the first $p$ symbols).

Proof. Let $M = (Q, Σ, δ, q_{0}, F)$ be a DFA recognising $L$ with $∣ Q ∣ = n$ states. Set $p = n$ . Let $s = s_{1} s_{2} \dots s_{m} \in L$ with $m \geq n$ . Consider the sequence of states visited:

q_{0}, q_{1} = δ (q_{0}, s_{1}), q_{2} = δ (q_{1}, s_{2}), \dots, q_{m} = δ (q_{m - 1}, s_{m}) .

This sequence has $m + 1 \geq n + 1$ entries drawn from a set of $n$ states. By the pigeonhole principle, some state repeats: there exist indices $0 \leq j < k \leq n$ with $q_{j} = q_{k}$ . Set $x = s_{1} \dots s_{j}$ , $y = s_{j + 1} \dots s_{k}$ , $z = s_{k + 1} \dots s_{m}$ . Then:

$∣ y ∣ = k - j > 0$ and $∣ x y ∣ = k \leq n = p$ , verifying conditions 2 and 3.
For any $i \geq 0$ , reading $x y^{i} z$ from $q_{0}$ reaches $q_{j}$ via $x$ , loops $i$ times through $y$ (returning to $q_{j}$ each time), then continues via $z$ to $q_{m} \in F$ . Hence $x y^{i} z \in L$ . $□$

Counterexamples to common slips

"If a language satisfies the pumping lemma, it must be regular." The pumping lemma is necessary but not sufficient. The language $L = {a^{i} b^{j} c^{k} : i, j, k \geq 0} \cup {a^{n} b^{n} c^{n} : n \geq 0}$ restricted appropriately can pump without issue while being non-regular. A classical counterexample is ${a^{i} b^{j} : i \neq = j}$ over a suitable alphabet extension; for a standard one see ^{[Hopcroft, Motwani & Ullman §2.4]}.
"The pumping lemma can prove a language is regular." No. The pumping lemma is exclusively a tool for proving non-regularity. The Myhill-Nerode theorem provides a necessary and sufficient condition ^{[Hopcroft, Motwani & Ullman §2.4]}.
"You get to choose how $s$ splits into $x y z$ ." No. The pumping lemma guarantees the existence of a split. In a non-regularity proof, the adversary chooses the split, and you must show that every valid split leads to a contradiction.

Key theorem with proof Intermediate+

Theorem (non-regularity via pumping). The following languages are not regular:

(a) ${0^{n} 1^{n} : n \geq 0}$ . (b) ${w w : w \in {0, 1}^{*}}$ . (c) ${0^{2^{n}} : n \geq 0}$ .

Proof of (a). Shown in the worked example above. Given pumping length $p$ , choose $s = 0^{p} 1^{p}$ . Any valid split has $y = 0^{k}$ for some $k \geq 1$ , and pumping down gives $0^{p - k} 1^{p} \in / L$ . $□$

Proof of (b). Let $p$ be the pumping length. Choose $s = 0^{p} 1 0^{p} 1 \in L$ (here $w = 0^{p} 1$ ). Then $s = x y z$ with $∣ x y ∣ \leq p$ and $∣ y ∣ > 0$ , so $y = 0^{k}$ for some $1 \leq k \leq p$ . Pumping gives $x y^{2} z = 0^{p + k} 1 0^{p} 1$ , which has more leading 0s than the 0s before the first "1" in the second copy. The resulting string is not of the form $w w$ . $□$

Proof of (c). Let $p$ be the pumping length. Choose $s = 0^{2^{p}}$ , which has length $2^{p} \geq p$ . Then $s = x y z$ with $y = 0^{k}$ for some $1 \leq k \leq p$ . Pumping once gives $x y^{2} z = 0^{2^{p} + k}$ . Since $1 \leq k \leq p < 2^{p}$ , we have $2^{p} < 2^{p} + k < 2^{p} + 2^{p} = 2^{p + 1}$ . So $2^{p} + k$ is strictly between consecutive powers of 2 and hence is not a power of 2. Thus $x y^{2} z \in / L$ . $□$

Bridge. The pumping lemma builds toward the Myhill-Nerode theorem in 47.01.02 where the pigeonhole argument reappears as the structural reason that $\equiv_{L}$ has finitely many classes for regular $L$ . This is exactly the content of the forward direction of Myhill-Nerode: finiteness of the state set forces a finite index. The lemma appears again in 47.01.05 where the context-free pumping lemma generalises the regular version by allowing two pumpable regions, and in 47.01.06 where the CYK algorithm provides a positive test for context-free membership that complements the negative test of the pumping lemma. The central insight is that the pumping lemma converts a structural property of DFAs (finite state set) into an algebraic property of languages (closure under pumping), and this is exactly why it is the primary tool for establishing language-theoretic lower bounds.

Exercises Intermediate+

Exercise 9 (hard, symbolic).

Let $L_{1} = {0^{n} 1^{n} : n \geq 0}$ and $L_{2} = {w \in {0, 1}^{*} : ∣ w ∣ \equiv 0 (mod 2)}$ . Is $L_{1} \cup L_{2}$ regular? Prove your answer.

Hint

Consider whether $L_{1} \cup L_{2}$ satisfies the pumping lemma. A language can satisfy the pumping lemma without being regular.

Answer

$L_{1} \cup L_{2}$ is not regular. Suppose it were. Then $(L_{1} \cup L_{2}) \cap \overline{L_{2}}$ would be regular by closure under complement and intersection. Now $\overline{L_{2}} = {w : ∣ w ∣ \equiv 1 (mod 2)}$ . Every string in $L_{1}$ has even length, so $L_{1} \cap \overline{L_{2}} = \emptyset$ . Thus $(L_{1} \cup L_{2}) \cap \overline{L_{2}} = L_{2} \cap \overline{L_{2}} = \emptyset$ , which is regular. This does not yield a contradiction. Instead, consider $L_{1} \cup L_{2}$ directly: any string $s \in L_{1}$ with $∣ s ∣ \geq p$ can be pumped (since the pumped versions are either in $L_{1}$ or have even length and hence are in $L_{2}$ ). So the pumping lemma does not help. Use the Myhill-Nerode theorem instead: the strings $0^{n}$ for $n \geq 0$ are pairwise inequivalent modulo $L_{1} \cup L_{2}$ (distinguished by $1^{n}$ for appropriate $n$ ), giving infinitely many equivalence classes. So $L_{1} \cup L_{2}$ is not regular.

Lean formalization Intermediate+

Mathlib has Computability.DFA and Computability.RegularLanguages with closure properties under Boolean operations and homomorphisms, but it does not formalise the pumping lemma. The foundational gap is the absence of a RegularLanguages.pumping_lemma theorem stating that for any regular language $L$ there exists $p$ such that every string $s \in L$ with $∣ s ∣ \geq p$ decomposes as $s = x y z$ with $∣ y ∣ > 0$ , $∣ x y ∣ \leq p$ , and $\forall i, x y^{i} z \in L$ . A formal proof would extract the pumping length from the state count of the minimal DFA and construct the decomposition from the repeated state. This unit ships without a lean_module.

Advanced results Master

Three results extend the pumping lemma framework.

Theorem 1 (Myhill-Nerode as the structural explanation of pumping). The pumping lemma is a consequence of the Myhill-Nerode theorem: if $L$ is regular with a $p$ -state DFA, then $\equiv_{L}$ has at most $p$ classes. For any $s \in L$ with $∣ s ∣ \geq p$ , the sequence of prefixes $ε, s_{1}, s_{1} s_{2}, \dots, s$ has $p + 1$ elements, so two prefixes $s [1.. j]$ and $s [1.. k]$ are $\equiv_{L}$ -equivalent. The substring $s [j + 1.. k]$ can then be inserted or deleted without changing membership, because equivalent prefixes behave identically under all continuations. The Myhill-Nerode theorem also provides the converse direction that the pumping lemma lacks: $L$ is regular iff $\equiv_{L}$ has finite index ^{[Hopcroft, Motwani & Ullman §2.4]}.

Theorem 2 (closure under inverse homomorphism). If $L \subseteq Γ^{*}$ is regular and $h : Σ^{*} \to Γ^{*}$ is a homomorphism, then $h^{- 1} (L) = {w \in Σ^{*} : h (w) \in L}$ is regular. This gives an alternative proof strategy for non-regularity: if $h^{- 1} (L)$ is not regular, then $L$ is not regular (contrapositive). For example, the homomorphism $h (a) = 0, h (b) = 1$ pulls ${0^{n} 1^{n}}$ back from ${a^{n} b^{n}}$ .

Theorem 3 (pumping lemma is not sufficient). Define $\overline{L}_{p} = {a^{k} b^{l} c^{m} : k, l, m \geq 0, k, l, m not all equal}$ . This language satisfies the pumping lemma conditions (any long enough string can be pumped within a region that does not disturb the non-equality), but $\overline{L}_{p}$ is not regular because its complement within $a^\astb^\astc^\ast$ is ${a^{n} b^{n} c^{n} : n \geq 0}$ , which is not regular (and not even context-free). This demonstrates that the pumping lemma is strictly weaker than the Myhill-Nerode characterisation ^{[Hopcroft, Motwani & Ullman §2.4]}.

Synthesis. The pumping lemma is the foundational reason that finite memory is detectable from the outside: the central insight is that finiteness of the DFA state set creates a loop that forces algebraic structure on the language. This builds toward the Myhill-Nerode theorem in 47.01.02 which replaces the one-directional pumping lemma with a necessary and sufficient characterisation of regularity. The lemma appears again in 47.01.05 where the context-free pumping lemma operates on parse trees rather than state sequences, and in 47.02.01 where the P-vs-NP framework asks analogous questions about the limits of polynomial-time computation. Putting these together, the pumping lemma is the first and most accessible instance of a general pattern in theoretical computer science: structural limitations of computational models manifest as algebraic properties of the languages or problems they can handle.

Full proof set Master

Proposition 1 (pumping lemma correctness). If $L$ is regular, then the pumping lemma conditions hold for $L$ .

Proof. Let $M = (Q, Σ, δ, q_{0}, F)$ recognise $L$ with $∣ Q ∣ = n$ . Set $p = n$ . Let $s \in L$ with $∣ s ∣ \geq p$ . Define $q_{j} = \hat{δ} (q_{0}, s_{1} \dots s_{j})$ for $0 \leq j \leq ∣ s ∣$ . Since $∣ s ∣ \geq p = n$ , the sequence $q_{0}, q_{1}, \dots, q_{∣ s ∣}$ has $∣ s ∣ + 1 \geq n + 1$ elements from a set of $n$ states. By the pigeonhole principle there exist $0 \leq j < k \leq n$ with $q_{j} = q_{k}$ .

Set $x = s_{1} \dots s_{j}$ , $y = s_{j + 1} \dots s_{k}$ , $z = s_{k + 1} \dots s_{∣ s ∣}$ . Then $∣ y ∣ = k - j \geq 1$ and $∣ x y ∣ = k \leq n = p$ .

For any $i \geq 0$ : reading $x y^{i} z$ from $q_{0}$ reaches $q_{j}$ after $x$ , then loops $i$ times from $q_{j}$ through $y$ back to $q_{j}$ , then reads $z$ from $q_{j}$ to $q_{∣ s ∣}$ . Since $q_{∣ s ∣} \in F$ (as $s \in L$ ), we have $x y^{i} z \in L$ . $□$

Proposition 2 ( ${0^{n} 1^{n}}$ is not regular). The language $L = {0^{n} 1^{n} : n \geq 0}$ is not regular.

Proof. Suppose $L$ is regular with pumping length $p$ . Choose $s = 0^{p} 1^{p} \in L$ . By the pumping lemma, $s = x y z$ with $∣ y ∣ > 0$ , $∣ x y ∣ \leq p$ , and $x y^{0} z \in L$ . Since $∣ x y ∣ \leq p$ , $y = 0^{k}$ for some $k \geq 1$ . Then $x z = 0^{p - k} 1^{p}$ , which has $p - k$ zeroes and $p$ ones. Since $k \geq 1$ , $p - k \neq = p$ , so $x z \in / L$ . Contradiction. $□$

Proposition 3 ( ${w w}$ is not regular). The language $L = {w w : w \in {0, 1}^{*}}$ is not regular.

Proof. Suppose $L$ is regular with pumping length $p$ . Choose $s = 0^{p} 1 0^{p} 1 \in L$ (with $w = 0^{p} 1$ ). Since $∣ s ∣ = 2 p + 2 \geq p$ , the pumping lemma applies. The split has $∣ x y ∣ \leq p$ and $∣ y ∣ > 0$ , so $y = 0^{k}$ for some $1 \leq k \leq p$ (all within the leading $0^{p}$ block). Then $x y^{2} z = 0^{p + k} 1 0^{p} 1$ . For this to be in $L$ , we need the first half to equal the second half: $0^{p + k} 1 = 0^{p} 1$ . But $p + k \neq = p$ , so this fails. Thus $x y^{2} z \in / L$ . Contradiction. $□$

Connections Master

47.01.01 — The DFA model with its finite state set provides the structural basis for the pumping lemma; the pigeonhole argument on DFA state sequences is the mechanism behind every pumping-lemma proof.
47.01.02 — Nondeterminism and the subset construction show that NFAs recognise the same regular languages as DFAs; the pumping lemma applies equally to NFA-recognisable languages since they coincide with DFA-recognisable ones.
47.01.03 — Regular expressions describe the same class as DFAs; the pumping lemma applies to the language of any regular expression, and its contrapositive proves that certain patterns cannot be expressed by any regular expression.
47.01.05 — Context-free grammars generate languages that properly contain the regular languages; the context-free pumping lemma extends the regular version by allowing two pumpable regions.
47.02.01 — The P-vs-NP question asks whether polynomial-time computation has a structural limitation analogous to the finite-memory limitation that the pumping lemma exposes for DFAs.

Historical & philosophical context Master

The pumping lemma for regular languages was implicit in the work of Rabin and Scott (1959) on finite automata, where the pigeonhole argument on state sequences appeared as a structural observation. The first explicit statement as a tool for proving non-regularity is due to Bar-Hillel, Perles, and Shamir (1961) in their paper "On Formal Properties of Simple Phrase Structure Grammars," where they also proved the context-free version ^{[Sipser §1.4]}.

The philosophical significance is that the pumping lemma provides the first instance of a recurring pattern in theoretical computer science: computational models with bounded resources (finite memory, polynomial time, logarithmic space) induce structural properties on the problems they can solve, and these properties can be used to prove impossibility results without constructing explicit counterexample machines. This pattern repeats in the time hierarchy theorem 47.02.02, the space hierarchy theorem 47.02.05, and the Baker-Gill-Solovay oracle results 47.02.04.

The pumping lemma also illustrates the gap between necessary and sufficient conditions. The Myhill-Nerode theorem (1957-1958) provides a necessary and sufficient condition for regularity, but the pumping lemma — being only necessary — is sometimes inadequate. This gap motivates the study of stronger separation techniques such as the interchange lemma and the Kolmogorov-complexity approach to non-regularity.

Bibliography Master

@book{sipser2013,
  author    = {Sipser, Michael},
  title     = {Introduction to the Theory of Computation},
  edition   = {3rd},
  publisher = {Cengage Learning},
  year      = {2013},
}
@book{hopcroft2006,
  author    = {Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D.},
  title     = {Introduction to Automata Theory, Languages, and Computation},
  edition   = {3rd},
  publisher = {Pearson},
  year      = {2006},
}
@article{barhillel1961formal,
  author  = {Bar-Hillel, Yehoshua and Perles, Micha and Shamir, Eli},
  title   = {On Formal Properties of Simple Phrase Structure Grammars},
  journal = {Zeitschrift f\"ur Phonetik, Sprachwissenschaft und Kommunikationsforschung},
  volume  = {14},
  pages   = {143--172},
  year    = {1961},
}
@article{rabin1959finite,
  author  = {Rabin, Michael O. and Scott, Dana},
  title   = {Finite Automata and Their Decision Problems},
  journal = {IBM Journal of Research and Development},
  volume  = {3},
  number  = {2},
  pages   = {114--125},
  year    = {1959},
}

Prerequisites

47.01.01 pending
47.01.02 pending

Tier anchors

beginner: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §1.4 (the pumping lemma: every regular language has a constant $p$ such that any string longer than $p$ in the language can be pumped)
intermediate: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §1.4 (formal pumping lemma statement, proof via pigeonhole principle on DFA states, applications to non-regularity proofs)
master: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §1.4; Hopcroft, Motwani & Ullman 2006 Introduction to Automata Theory, Languages, and Computation 3e (Pearson) §2.4 (Myhill-Nerode characterisation as the structural reason behind the pumping lemma, closure properties under homomorphism)

References

Sipser, M. — Introduction to the Theory of Computation (3rd ed.) · Cengage (2013). Section 1.4 states the pumping lemma: if $L$ is a regular language, then there exists a pumping length $p \geq 1$ such that every string $s \in L$ with $∣ s ∣ \geq p$ can be divided into three parts $s = x y z$ satisfying (1) for each $i \geq 0$ , $x y^{i} z \in L$ , (2) $∣ y ∣ > 0$ , and (3) $∣ x y ∣ \leq p$ ; the proof uses the pigeonhole principle on a DFA with $p$ states: reading a string of length $\geq p$ visits at least $p + 1$ states, so some state $q$ is visited twice, and the substring read between the two visits to $q$ is $y$ , which can be repeated or deleted without changing the outcome. Section 1.4 applies the lemma to prove that ${0^{n} 1^{n} : n \geq 0}$ , ${w w : w \in {0, 1}^{*}}$ , and ${0^{n^{2}} : n \geq 0}$ are not regular.
Hopcroft, J. E., Motwani, R. & Ullman, J. D. — Introduction to Automata Theory, Languages, and Computation (3rd ed.) · Pearson (2006). Section 2.4 develops the Myhill-Nerode theorem and shows that the pumping lemma is a consequence of the finiteness of the index of $\equiv_{L}$ ; the converse of the pumping lemma does not hold: there exist non-regular languages that satisfy the pumping lemma conclusion (e.g. the Ogden-like language ${a^{i} b^{j} c^{k} : i, j, k \geq 0, not all distinct}$ ), so the pumping lemma is a necessary but not sufficient condition for regularity.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m