Proving Non-Regularity with the Pumping Lemma

In our last lesson, we completed our understanding of Kleene's Theorem, establishing that finite automata and regular expressions are two sides of the same coin—equivalent in their power to define the class of regular languages. This naturally leads to a crucial question that aligns with your goal of understanding the theory of computation: What are the limits of this power? What kinds of languages can these simple, finite-memory machines not recognize?

Today, we will answer that question by introducing one of the most important tools in automata theory: the Pumping Lemma for Regular Languages. This lemma formalizes the inherent limitation of finite memory and gives us a powerful, rigorous method to prove that a given language is not regular. This lesson will focus on understanding the lemma's proof and mastering the strategy for applying it.

1. The Core Idea: Finite Memory and Inevitable Loops

Before diving into the formal lemma, let's build the intuition. A Deterministic Finite Automaton (DFA) has a finite number of states. If we feed it a string that is longer than the number of states, the machine must revisit a state it has been in before. This is a direct consequence of the Pigeonhole Principle. This revisited state creates a loop in the computation path.

Any string that causes the machine to traverse this loop can have the part of the string corresponding to the loop repeated ("pumped") any number of times, or removed entirely, and the resulting new string will still be accepted by the automaton. The Pumping Lemma is the formal expression of this observation.

The following notes from an MIT course offer a concise argument that uses the Pigeonhole Principle to show why a language like $L = {0^{n} 1^{n} ∣ n \geq 0}$ cannot be regular. This is the foundational idea behind the lemma.

Non-regular languages and the pumping lemma

These notes from a course by Prof. Scott Aaronson at MIT provide a crisp, formal argument.

Please read the section titled "Showing specific languages are non-regular". Focus on Example 1, for the language L_1 = \{ 0^n1^n \mid n \ge 0 \}. Observe how the states of the DFA are the "holes" and the prefixes 0^i are the "pigeons," leading to the conclusion that two different prefixes, 0^i and 0^j, must land in the same state.

2. The Pumping Lemma: Formal Statement and Proof

The argument you just read can be generalized to prove a property that all regular languages must satisfy. This is the Pumping Lemma.

Theorem (The Pumping Lemma for Regular Languages):
If $L$ is a regular language, then there exists a number $p$ (the pumping length) such that for any string $s \in L$ with length $∣ s ∣ \geq p$ , $s$ can be divided into three parts, $s = x y z$ , satisfying the following three conditions:

$x y^{i} z \in L$ for every integer $i \geq 0$ .
$∣ y ∣ > 0$ .
$∣ x y ∣ \leq p$ .

Let's break this down:

The first condition is the "pumping" part. It states that the middle piece, $y$ , can be repeated any number of times (including zero times, which removes it), and the resulting string must still be in the language.
The second condition is crucial: the piece being pumped, $y$ , must not be empty. Otherwise, we could pump nothing and the theorem would be trivial.
The third condition is also vital for many proofs. It tells us that the loop ( $y$ ) must occur within the first $p$ characters of the string.

The proof of this theorem formalizes the pigeonhole argument. Please read the proof in the same set of notes.

Non-regular languages and the pumping lemma

This section presents the formal statement and proof of the lemma.

Read the section titled "The Pumping Lemma", up to (but not including) "Example 1, revisited". The proof maps the states visited while processing a long string to the pigeons and holes. Pay close attention to how the division of the string s into u,v,w (or x,y,z) corresponds to the path taken in the DFA before, during, and after the first detected loop.

Caption: This diagram illustrates the core of the Pumping Lemma's proof. For a string longer than the number of states, a state (`pi=pj`) must be revisited. The string is then broken into `x` (path to the loop), `y` (the loop itself), and `z` (path after the loop). Traversing the `y` loop multiple times (or zero times) generates new strings that must also be accepted.

3. The Pumping Lemma as an Adversarial Game

The Pumping Lemma is an "if...then..." statement. Its primary use is its contrapositive: if a language fails to have the pumping property, then it cannot be regular. This is the basis for proofs by contradiction.

Applying the lemma can be thought of as a game between you and an opponent. The steps are always the same, and your goal is to force a contradiction.

Assume your language $L$ is regular (to set up the contradiction).
The Pumping Lemma guarantees a pumping length $p$ exists. You don't know what $p$ is, so your proof must work for any $p$ .
You choose a specific string $s \in L$ where $∣ s ∣ \geq p$ . This is the most creative step. The string must be chosen cleverly to expose the language's "weakness."
The lemma guarantees that $s$ can be split into $s = x y z$ satisfying the three conditions. Since you don't know the split, your argument must work for all possible valid splits (all decompositions where $∣ y ∣ > 0$ and $∣ x y ∣ \leq p$ ).
You choose a value for $i$ (usually $i = 0$ or $i = 2$ ) such that the "pumped" string $x y^{i} z$ is demonstrably not in $L$ .
This violates the lemma's guarantee, creating a contradiction. Your initial assumption that $L$ was regular must be false.

The following video provides an excellent walkthrough of this strategy.

Pumping Lemma for Regular Languages FOUR Examples and Proof Strategies!

The "Easy Theory" channel provides very clear and rigorous explanations. This segment lays out the proof framework.

Watch the segment explaining the proof strategy. The speaker breaks down the proof by contradiction into five clear steps. Think of this as a game where you must make strategic choices to win.

4. Applying the Pumping Lemma: Examples

Let's put this strategy into practice. The best way to understand the Pumping Lemma is to see it applied to different kinds of languages.

Example 1: The Classic Case — $L = {0^{n} 1^{n} ∣ n \geq 0}$

This is the canonical example of a non-regular language. It requires memory to count the number of 0s. The Pumping Lemma provides the formal machinery to prove this.

Pumping Lemma for Regular Languages FOUR Examples and Proof Strategies!

This segment provides a detailed walkthrough for the classic example.

Watch the proof for L = \{0^n1^n\} from the first example. Pay close attention to: The strategic choice of string s = 0^p1^p. How the condition |xy| \le p forces the substring y to consist only of 0s. How pumping with i=2 (or any i \ne 1) breaks the equality between the number of 0s and 1s.

Example 2: Pumping Down — $L = {0^{i} 1^{j} ∣ i > j}$

Sometimes, adding copies of $y$ doesn't lead to a contradiction. In these cases, we might need to remove $y$ by "pumping down" with $i = 0$ .

Pumping Lemma for Regular Languages FOUR Examples and Proof Strategies!

This second example introduces a new technique: pumping down.

Watch the proof for L = \{0^i1^j \mid i > j\} from the second example. Note two clever choices here: The string is chosen to be s = 0^{p+1}1^p, which is "barely" in the language. The value i=0 is chosen for pumping. Pumping up (i \ge 2) would produce strings that are still in L, so it wouldn't yield a contradiction. Pumping down, however, violates the i > j condition.

Example 3: An Algebraic Argument — $L = {0^{k} ∣ k is a perfect square}$

This example showcases how the proof can involve more intricate mathematical reasoning, which should appeal to your background. The argument here is not about the structure of the string, but about its length.

Pumping Lemma for Regular Languages FOUR Examples and Proof Strategies!

This example demonstrates a more advanced, algebraic application of the lemma.

Watch the proof for the language of strings of 0s whose length is a perfect square, from the perfect squares example. The key insight is to show that the length of the pumped string, |xy^2z|, lies strictly between two consecutive perfect squares. Let s=0^{p^2}. Then |s|=p^2. We know |y| > 0, so the length of the pumped string xy^2z is |s| + |y| = p^2 + |y|. This is strictly greater than p^2. We also know |y| \le |xy| \le p. Therefore, |xy^2z| = p^2 + |y| \le p^2 + p. For p \ge 1, p^2+p < p^2+2p+1 = (p+1)^2. So we have shown p^2 < |xy^2z| < (p+1)^2. The length of the pumped string cannot be a perfect square, which is a contradiction.

Conclusion

In this lesson, we have moved from the capabilities of regular languages to their fundamental limitations. You learned about the Pumping Lemma, a direct consequence of the finite memory of automata, and saw how to wield it as a precise tool for proving non-regularity.

Key Takeaways:

The Pigeonhole Principle is the root cause: Any DFA processing a sufficiently long string must enter a loop.
The Pumping Lemma formalizes this: It guarantees that for any regular language, long enough strings contain a "pumpable" substring near their beginning.
Proof by Contradiction is the method: To prove a language is not regular, you assume it is, then use the lemma to find a string that can be pumped out of the language, which is a contradiction.
The strategy is an art: Applying the lemma involves a clever choice of the initial string $s$ and the pumping value $i$ to expose the language's structural weakness.

We now have tools to show a language is regular (build an NFA/DFA or a regular expression) and a tool to show one is not regular (the Pumping Lemma). In the next lesson, we will explore the closure properties of regular languages. These properties (e.g., are regular languages closed under union, intersection, complement?) provide another powerful, and often simpler, way to reason about whether a language is regular.

Recommended resources

1. The Core Idea: Finite Memory and Inevitable Loops

2. The Pumping Lemma: Formal Statement and Proof

3. The Pumping Lemma as an Adversarial Game

4. Applying the Pumping Lemma: Examples

Example 1: The Classic Case — L={0n1n∣n≥0}

Example 2: Pumping Down — L={0i1j∣i>j}

Example 3: An Algebraic Argument — L={0k∣k is a perfect square}

Conclusion

Example 1: The Classic Case — $L = {0^{n} 1^{n} ∣ n \geq 0}$

Example 2: Pumping Down — $L = {0^{i} 1^{j} ∣ i > j}$

Example 3: An Algebraic Argument — $L = {0^{k} ∣ k is a perfect square}$