Pumping lemma for regular languages — proof and using to show non-regularity: Visual walkthrough

We assume nothing. If you have never seen a DFA, the first two steps build one for you.

Step 1 — What a machine that "reads" a string even is

WHAT. Picture a tiny robot that reads a word one letter at a time, left to right. At any moment the robot is standing in exactly one room. When it reads a letter, an arrow tells it which room to walk to next. The set of rooms is fixed and finite — the robot cannot build new rooms while it reads.

WHY. This "finite set of rooms" is the whole reason the lemma exists. The robot's only memory is which room it is standing in. If there are, say, 4 rooms, the robot can remember at most 4 different situations. It literally cannot remember "I have counted 500 letters" — that would need at least 501 different rooms. Hold onto this: finite rooms = finite memory = cannot count without bound.

PICTURE. Below: three rooms (circles), letters on the arrows. Reading the word a a b walks the robot along the highlighted path. One room is a start (thick incoming arrow); a double circle means "if you stop here, the word is accepted."

Figure — Pumping lemma for regular languages — proof and using to show non-regularity

Step 2 — Recording the robot's walk as a list of rooms

WHAT. Feed the robot a word $w = a_{1} a_{2} \dots a_{n}$ (so $n = ∣ w ∣$ is its length, the number of letters). As it reads, write down the room it stands in before the first letter, then after each letter. That gives a list of rooms.

$r_{0} = q_{0}, r_{k} = δ (r_{k - 1}, a_{k})$

Reading term by term:

$r_{0}$ — the room before reading anything; it is the start room $q_{0}$ .
$a_{k}$ — the $k$ -th letter of the word.
$r_{k - 1}$ — the room we were in just before reading $a_{k}$ .
$δ (r_{k - 1}, a_{k})$ — follow the arrow labelled $a_{k}$ out of that room; where it lands is $r_{k}$ .

WHY. We want to see the walk, not the word. The proof will be about this list of rooms, because rooms are finite but the word can be as long as we like. Turning "a word" into "a sequence of rooms" is the move that lets pigeonhole strike.

PICTURE. The word a a b a written along the bottom; above each gap between letters sits the room the robot is in. Reading $n$ letters produces $n + 1$ rooms: $r_{0}, r_{1}, \dots, r_{n}$ .

Step 3 — More rooms visited than rooms exist (Pigeonhole)

WHAT. Let $p$ = the number of rooms, $p = ∣ Q ∣$ . Now take a word that is at least $p$ letters long, $∣ w ∣ \geq p$ . Look only at the first $p + 1$ rooms of the walk: $r_{0}, r_{1}, r_{2}, \dots, r_{p} .$ That is $p + 1$ entries in the list, but there are only $p$ distinct rooms in the whole building.

WHY this tool — the Pigeonhole Principle. We reach for pigeonhole because it is the exact tool that answers "if I place more items than boxes, must a box get two items?" — yes, always. Here the pigeons are the $p + 1$ rooms in our list; the holes are the $p$ actual rooms. $p + 1$ pigeons into $p$ holes forces two list-entries to be the same room. No other tool is needed: it is a pure counting fact.

$\exists j, k with 0 \leq j < k \leq p and r_{j} = r_{k} .$

$j$ — the position of the first visit to the repeated room.
$k$ — the position of the second (later) visit; $k > j$ so the two visits are genuinely different moments.
$k \leq p$ — both visits happen inside the first $p$ steps.

PICTURE. Nine numbered slots (the list) with only three colours available (the rooms). By slot count alone, one colour must appear twice — circled in red. That red pair is $r_{j} = r_{k}$ .

Step 4 — The revisited room is a loop; name the three chunks

WHAT. Between the two visits to the same room $r_{j} = r_{k}$ , the robot read the letters $a_{j + 1} \dots a_{k}$ and came right back to where it started. That is a loop. Cut the word at these two moments into three pieces:

$x = a_{1} \dots a_{j}, y = a_{j + 1} \dots a_{k}, z = a_{k + 1} \dots a_{n} .$

$x$ — everything read before the first visit; it drives the robot $q_{0} \to r_{j}$ .
$y$ — the letters read between the two visits; it drives $r_{j} \to r_{k} = r_{j}$ : a loop back to the same room.
$z$ — everything read after the second visit; it drives $r_{j} \to r_{n}$ (the finish).

WHY. We split exactly at the repeated room because that is where the loop lives. Naming the loop $y$ lets us talk about running it a different number of times.

PICTURE. The walk drawn as a path with a self-loop drawn around room $r_{j}$ . The $x$ segment leads in, the $y$ segment is the loop, the $z$ segment leads out to an accepting room.

Two facts fall out immediately:

$∣ y ∣ = k - j \geq 1$ — the loop reads at least one letter, because $j < k$ . (This is condition 1.)
$∣ x y ∣ = k \leq p$ — the loop finishes within the first $p$ letters, because $k \leq p$ . (This is condition 2.)

Note also that $x$ and $z$ are allowed to be empty. If $j = 0$ then $x = ε$ (the loop is the very first thing read); and if $k = n$ then $z = ε$ (the loop runs right up to the last letter, so there is nothing left after it). Both are perfectly legal — only $y$ is forbidden from being empty. We revisit these corners with pictures in Step 6.

Step 5 — Running the loop any number of times stays legal

WHAT. Because $y$ starts and ends at the same room $r_{j}$ , we can splice in as many copies of $y$ as we like and the robot still ends at the same finish room $r_{n}$ : $q_{0} x r_{j} i loops y r_{j} y r_{j} \dots y r_{j} z r_{n} \in F .$ So for every $i \geq 0$ : $x y^{i} z \in L .$

$y^{i}$ — the loop-word $y$ written $i$ times in a row.
$y^{0} = ε$ — running the loop zero times (skip it entirely); the robot goes $x$ then straight to $z$ , still legal because it is standing at $r_{j}$ either way.
$i = 1$ — the original word $w = x y^{1} z$ .
$i = 2, 3, \dots$ — extra laps of the loop.
$L$ — the language of accepted words from Step 1; landing in $r_{n} \in F$ is exactly what puts $x y^{i} z$ into $L$ .

WHY. This is the payoff. A loop is "free repetition." Since every lap returns to $r_{j}$ , the room the robot stops in never changes — so acceptance never changes. This is exactly condition 3, and it completes the lemma.

PICTURE. Three filmstrip frames: $i = 0$ (loop skipped), $i = 1$ (one lap), $i = 2$ (two laps). In all three the path enters $r_{j}$ , does its laps, exits via $z$ , and lands on the same double-circle finish.

Step 6 — The degenerate cases (nothing is swept under the rug)

WHAT & WHY. A careful walkthrough must survive every corner case. Here they are, each pictured.

Case A — $y$ at the very front ( $j = 0$ ). Then $x = ε$ (empty) and the loop is the first thing read. Perfectly allowed: $r_{0} = r_{k}$ means the loop touches the start room. $∣ x y ∣ = k \leq p$ still holds.

Case B — the loop runs to the very end ( $k = n$ ). Then $z = ε$ (empty) — there is nothing left after the second visit, so the finish room is the repeated room, $r_{n} = r_{j}$ . Still fine: $y^{0} = ε$ gives $x z = x$ , and pumping up appends more laps at the tail. Empty $z$ is allowed exactly like empty $x$ .

Case C — pumping down, $i = 0$ . The robot skips the loop. We must confirm it is at $r_{j}$ to hand over to $z$ — and it is, because $x$ already brought it to $r_{j}$ . So $x z \in L$ too. Beginners forget this case; it is often the sharpest weapon (see Example 2 in the parent).

Case D — could the first $p + 1$ rooms be all distinct? No — that would need $p + 1$ distinct rooms, but only $p$ exist. Pigeonhole forbids this. The repeat is guaranteed, never optional.

PICTURE. Four mini-panels, one per case, each highlighting what changes (empty $x$ , empty $z$ with $k = n$ , skipped loop, the impossible all-distinct list crossed out in red).

The one-picture summary

Everything above compressed into a single diagram: a long word along the bottom, its walk as a path that necessarily loops (pigeonhole), the three chunks $x, y, z$ coloured, and the loop $y$ shown running $0$ , $1$ , $2$ times — all landing on the same accepting room.

Recall Feynman retelling — say the whole proof in plain words

A regular language runs on a machine with a fixed number of rooms, call it $p$ ; the machine's only memory is which room it stands in. The language $L$ is just "the words this machine says yes to." Now feed it a word longer than $p$ letters. As it reads, it visits a room after each letter — more visits than rooms exist, so by simple counting (pigeonhole) it must step into some room twice. The letters it read between those two visits form a loop that starts and ends in the same room. Because a loop returns you to where you began, the machine can run that loop zero, one, or a hundred times and always finish in the very same room — so all those pumped words $x y^{i} z$ are accepted too. That is the whole lemma. To prove a language is not regular, you find one word where adding or removing a loop must break membership (like unbalancing the $a$ 's and $b$ 's in $a^{n} b^{n}$ ); since the lemma promised the loop couldn't break anything, you have a contradiction, and no such machine can exist.

Recall In one line: which two facts about the DFA make the loop unavoidable?

The rooms are finite ( $p$ of them) and a long word forces $p + 1$ visits — more visits than rooms, so a room repeats.

Related tools that reach the same conclusion differently: Myhill–Nerode Theorem (counts distinguishable prefixes), and note that pumping also has a cousin for grammars, the Pumping Lemma for Context-Free Languages. For what regular languages are closed under, see Closure Properties of Regular Languages.