Proving Nonregularity with the Pumping Lemma

Hello. In the previous lesson, you constructed product DFAs to show that regular languages remain regular under Boolean combinations. This lesson takes the complementary direction: how to prove that a language cannot be recognized by any DFA.

The pumping lemma formalizes a limitation of finite automata. A DFA has only finitely many states, so while reading a sufficiently long input, it must revisit some state. The segment read between those visits is a loop: it can be repeated or removed without changing the machine’s eventual acceptance. We will turn that necessary property of regular languages into contradiction proofs.

---

The pumping lemma: a necessary condition

Let $L$ be a regular language. Then there is an integer $p\ge 1$, called a pumping length, such that every string $w\in L$ with $|w|\ge p$ can be written as

$$w=xyz$$

where:

$$|xy|\le p$$ $$|y|\ge 1$$

and

$$x{y}^{i}z\in L$$

for every integer $i\ge 0$.

The notation $y^i$ means $i$ copies of $y$. In particular:

$$y^0=ϵ,y^1=y,y^2=yy.$$

The three conditions have distinct roles:

Condition	What it guarantees
$	xy
$	y
$x{y}^{i}z\in L$ for all $i\ge 0$	Removing, repeating, or multiplying the loop must preserve membership in $L$.

Why should this be true for a DFA? Suppose a DFA has $p$ states and reads the first $p$ characters of a long accepted string. Including its starting position, the machine occupies $p+1$ state positions. Since only $p$ states are available, two of those positions must have the same state. The input portion read between those two visits is a nonempty loop. Call the input before the loop $x$, the loop $y$, and the rest of the input $z$. Traversing the loop zero, one, two, or any number of times leaves the machine in the same state before it continues through $z$.

The lemma does not say that you may select a convenient decomposition yourself. It says that, if the language is regular, some suitable decomposition must exist for every sufficiently long string.

---

The quantifier order: who gets to choose what?

Most pumping-lemma errors are logical rather than algebraic. The lemma has this structure:

$$\exists p\ge 1\forall w\in L\text{ with }|w|\ge p\exists x,y,z\forall i\ge 0.$$

To disprove regularity, your proof must defeat this claim in the correct order. The most useful way to remember the order is as a game:

1. Assume $L$ is regular. The opponent supplies a pumping length $p$.
2. You choose a string $w\in L$ whose length is at least $p$.
3. The opponent chooses a decomposition $w=xyz$, subject to $|xy|\le p$ and $|y|\ge 1$.
4. You choose a value $i\ge 0$ for which $x{y}^{i}z\notin L$.

Your argument succeeds only if it works for every legal decomposition chosen in step 3. The value of $i$ may depend on the decomposition, although in clean proofs a single choice such as $i=0$ or $i=2$ often handles all cases.

A compact statement of the proof target is:

$$\forall p\ge 1\exists w\in L\text{ with }|w|\ge p\forall x,y,z\left[\begin{array}{c}w=xyz,|xy|\le p,|y|\ge 1\end{array}\right]⟹\exists i\ge 0\text{ such that }x{y}^{i}z\notin L.$$

This makes the strategic purpose of choosing $w$ clear: choose it so that the bound $|xy|\le p$ forces $y$ into a region where pumping breaks an essential feature of the language.

---

A complete proof: equal numbers of zeros and ones

Consider the language

$$L=\{0^n{1}^n\mid n\ge 0\}.$$

Its strings consist of some number of zeros followed by exactly the same number of ones:

$$ϵ,01,0011,000111,\dots$$

We will prove that $L$ is not regular.

Proof

Assume, for contradiction, that $L$ is regular. Let $p$ be the pumping length supplied by the pumping lemma.

Choose

$$w=0^p{1}^p.$$

This is a valid choice because

$$w\in L$$

and

$$|w|=2p\ge p.$$

Now let

$$w=xyz$$

be any decomposition satisfying

$$|xy|\le p$$

and

$$|y|\ge 1.$$

The first $p$ symbols of $w$ are all zeros. Since $xy$ is a prefix of $w$ of length at most $p$, both $x$ and $y$ consist only of zeros. Therefore there are integers $a\ge 0$ and $b\ge 1$ such that

$$x=0^a$$ $$y=0^b.$$

The remaining suffix is

$$z=0^{p-a-b}{1}^p.$$

Now choose $i=0$. The pumping lemma would require $xz\in L$. But

$$xz=0^a{0}^{p-a-b}{1}^p=0^{p-b}{1}^p.$$

Because $b\ge 1$, the number of zeros is $p-b$, which differs from the number $p$ of ones. Hence

$$xz\notin L.$$

This contradicts the pumping lemma’s requirement that $x{y}^{i}z\in L$ for every $i\ge 0$. Therefore the original assumption was false:

$$L\text{ is not regular.}$$

$\square$

---

What made the proof work?

The proof has a deliberate design.

First, $w=0^p{1}^p$ depends on the unknown pumping length $p$. Choosing a fixed string such as $0011$ would be invalid, because its length might be smaller than $p$.

Second, the first block has length exactly $p$. This combines with

$$|xy|\le p$$

to trap all of $y$ inside the zeros. We never need to know the exact length of $y$; we only need to know that it is a positive number of zeros.

Finally, pumping down with $i=0$ changes one count but not the other. The defining invariant of the language, equal counts in the prescribed order, is destroyed.

This pattern generalizes:

Choose a long string with a protected region of length at least $p$. Use the prefix bound to force $y$ into that region. Then pump in a way that violates the language’s defining condition.

For instance, the same proof idea immediately shows that

$$\{a^n{b}^n\mid n\ge 0\}$$

is nonregular: choose $a^p{b}^p$, force $y$ to contain only $a$'s, and pump down.

---

A reusable proof template

For many languages, a polished pumping-lemma proof can follow this structure.

1. State the assumption.
   “Assume for contradiction that $L$ is regular.”

2. Introduce the pumping length.
   “Let $p\ge 1$ be the pumping length guaranteed by the pumping lemma.”

3. Choose a strategic string.
   Define $w$ as a function of $p$. Verify both:

   $$w\in L$$

   and

   $$|w|\ge p.$$

4. Keep the decomposition arbitrary.
   “Let $w=xyz$, where $|xy|\le p$ and $|y|\ge 1$.”

5. Use the constraints.
   Derive what $y$ must look like. This is usually the proof’s central observation.

6. Choose a pumping exponent.
   Choose $i=0$, $i=2$, or another nonnegative integer that makes the pumped string fail the language definition.

7. Identify the contradiction precisely.
   State why

   $$x{y}^{i}z\notin L$$

   contradicts the lemma’s claim that the string must be in $L$ for every $i\ge 0$.

8. Conclude nonregularity.
   “Therefore $L$ is not regular.”

A proof becomes rigorous not by displaying many sample decompositions, but by taking an arbitrary legal decomposition and deriving a contradiction from the length constraints.

---

Common invalid arguments

Choosing the pumping length yourself

You cannot write, “Let $p=5$,” and find a string that does not pump. If $L$ were regular, it might have a different pumping length. Your proof must begin with an arbitrary pumping length supplied under the regularity assumption.

Choosing the pumpable substring yourself

Writing

$$x=ϵ,y=0^p,z=1^p$$

does not prove nonregularity. It only shows that one particular decomposition fails. The pumping lemma promises that some legal decomposition works, so you must defeat all legal decompositions.

Forgetting the prefix bound

The condition is not merely that $y$ is nonempty. You must use

$$|xy|\le p$$

to constrain where $y$ occurs. In the $0^p{1}^p$ proof, this is exactly what prevents $y$ from containing ones.

Pumping without checking the language definition

After choosing $i$, explicitly explain why the resulting string is outside the language. “The result looks wrong” is not a proof. For $0^n{1}^n$, the exact failure is that the two block lengths differ.

Trying to prove regularity with the pumping lemma

The pumping lemma is one-way:

$$\text{regular}⟹\text{pumpable}.$$

It is useful when you can show a language fails the pumping condition. But a language’s apparent ability to pump does not establish that it is regular; to prove regularity, construct a DFA, NFA, regular expression, or use an appropriate closure argument.

---

Key takeaways

The pumping lemma captures the fact that every sufficiently long string accepted by a finite automaton contains a loop that can be repeated any number of times. To prove a language nonregular with it, assume regularity, let $p$ be the resulting pumping length, and choose a string $w$ whose structure forces every possible pumpable segment into a vulnerable region.

The logical order is essential: you choose $w$ after seeing $p$, but the decomposition is adversarial. A valid proof establishes that every legal decomposition can be pumped to yield a string outside the language.

Next, you will prove nonregularity by a different method: combining closure properties of regular languages with a known nonregular language.