Pumping lemma for regular languages — proof and using to show non-regularity: Worked examples

This page is a catalogue of cases. The parent note gave you the skeleton; here we walk every kind of non-regularity proof you can meet, so no exam string surprises you. Prerequisites we lean on: Finite Automata (DFA NFA), Pigeonhole Principle, and the pumping lemma statement itself.

The scenario matrix

Read this as: "what makes $x y^{i} z$ fall out of $L$ ?" — the mechanism of the contradiction.

Cell	Case class	Trap mechanism	Which $i$	Example
A	Equal-count $a^{n} b^{n}$	pumping changes one block's count only	$i = 2$	Ex 1
B	Symmetry / palindrome	pumping breaks front–back mirror	$i = 0$	Ex 2
C	Sparse lengths ( $n^{2}$ , $2^{n}$ , primes)	pumped length lands in a forbidden gap	$i = 2$	Ex 3
D	Multi-block relation ( $a^{n} b^{m} c^{...}$ )	$	xy	\le p $p in s$ y$ to leftmost block
E	Degenerate / edge string ( $n = 0$ , tiny $p$ )	show the method still works at boundaries	—	Ex 5
F	Non-regular but PASSES the lemma (must NOT conclude regular)	pumping cannot fail — lemma gives no info	any	Ex 6
G	Real-world word problem (balanced brackets)	same as equal-count in disguise	$i = 0$	Ex 7
H	Exam twist: complement / intersection	pump the derived language, or use closure	$i = 2$	Ex 8

Every cell A–H below gets a full worked example. Cells that are geometric-on-the-automaton get a figure.

Example 1 — Cell A: the classic equal-count

Worked example

$L = {a^{n} b^{n} : n \geq 0}$ is not regular Forecast: if we add extra $a$ 's but leave the $b$ 's alone, will the counts still match? Guess before reading.

Step 1. Assume $L$ regular, so a pumping length $p \geq 1$ exists. Why this step? The lemma only speaks if $L$ is regular. We assume it to derive a contradiction.

Step 2. Choose $w = a^{p} b^{p}$ . Note $∣ w ∣ = 2 p \geq p$ and $w \in L$ . Why this step? We need one string that (a) is genuinely in $L$ and (b) forces the adversary's hand. Packing $p$ copies of $a$ first means the "first $p$ symbols" are all $a$ .

Step 3. The adversary splits $w = x y z$ with $∣ y ∣ \geq 1$ (condition 1) and $∣ x y ∣ \leq p$ (condition 2). Since the first $p$ symbols are all $a$ , both $x$ and $y$ live inside the $a$ -block. So $y = a^{m}$ with $1 \leq m \leq p$ . Why this step? Condition 2 ( $∣ x y ∣ \leq p$ ) is our leash on the adversary. We used it to guarantee $y$ is pure $a$ 's.

Step 4. Pump up, $i = 2$ : $x y^{2} z = a^{p + m} b^{p}$ . Why this step? One extra copy of $y$ adds $m$ more $a$ 's and touches no $b$ . That is exactly the imbalance we want.

Step 5. Since $m \geq 1$ (condition 1), we have $p + m \neq = p$ , so $a^{p + m} b^{p} \in / L$ . But condition 3 demands $x y^{2} z \in L$ — contradiction. Why this step? Condition 3 is the lemma's promise that pumping stays inside $L$ ; producing a pumped string outside $L$ is precisely what refutes the assumption that $L$ is regular.

Verify: take $p = 3, m = 1$ : pumped string is $a^{4} b^{3}$ . Count check $4 \neq = 3$ ✓ (not in $L$ ). The proof used only $m \geq 1$ , so it holds for every legal split. $■$ ⇒ $L$ not regular.

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

Example 2 — Cell B: palindromes (pump down)

Worked example

$L = {w w^{R} : w \in {0, 1}^{*}}$ is not regular Forecast: if we delete a couple of leading $0$ 's, is the string still a mirror of itself? Guess.

Step 1. Assume regular ⇒ $p$ exists. Why this step? We are trying to prove non-regularity by contradiction, so we begin by supposing the opposite — that $L$ is regular — which hands us a pumping length $p$ to exploit.

Step 2. Choose $s = 0^{p} 11 0^{p}$ . This equals $u u^{R}$ for $u = 0^{p} 1$ , so $s \in L$ , and $∣ s ∣ = 2 p + 2 \geq p$ . Why? We want a long block of identical symbols at the front so the leash $∣ x y ∣ \leq p$ (condition 2) traps $y$ there.

Step 3. Adversary picks $s = x y z$ , $∣ y ∣ \geq 1$ (condition 1), $∣ x y ∣ \leq p$ (condition 2). First $p$ symbols are all $0$ , so $y = 0^{m}$ , $1 \leq m \leq p$ . Why? The leash again — $y$ is pure leading zeros.

Step 4. Pump down, $i = 0$ : $x y^{0} z = 0^{p - m} 11 0^{p}$ . Why $i = 0$ ? Here removing symbols is the cleaner attack: it shortens the front block while the back block stays at $p$ , destroying the mirror. Pumping up would also work, but down is tidy.

Step 5. For $0^{p - m} 11 0^{p}$ to be a palindrome, front zeros must equal back zeros: $p - m = p$ , impossible for $m \geq 1$ . So it's not in $L$ , contradicting condition 3.

Verify: $p = 3, m = 1$ : $0^{2} 11 0^{3} = 0011000$ . Reverse it: $0001100 \neq = 0011000$ ✓ not a palindrome. $■$

Example 3 — Cell C: sparse lengths (the gap argument)

Worked example

$L = {a^{n^{2}} : n \geq 0}$ is not regular Forecast: perfect squares are $0, 1, 4, 9, 16, 25, \dots$ — they spread further apart as they grow. If we bump a big square by a small amount, can it land on another square? Guess.

Step 1. Assume regular ⇒ $p$ . Why this step? Contradiction proof: assume the thing we want to disprove ( $L$ regular) so the lemma gives us a concrete $p$ to attack.

Step 2. Choose $w = a^{p^{2}}$ . Length $p^{2}$ is a perfect square, and $p^{2} \geq p$ for $p \geq 1$ . Why? We attack near a large square where the gap to the next square is wide.

Step 3. Adversary: $w = x y z$ , $1 \leq m = ∣ y ∣ \leq ∣ x y ∣ \leq p$ (conditions 1 and 2). Why? Here every symbol is $a$ , so we can't pin where $y$ is — but the leash (condition 2) still bounds how big $y$ is: $m \leq p$ . That bound is the whole trick.

Step 4. Pump up, $i = 2$ : length becomes $p^{2} + m$ . Why? Adds exactly $m$ symbols, $1 \leq m \leq p$ .

Step 5. The next square after $p^{2}$ is $(p + 1)^{2} = p^{2} + 2 p + 1$ . The gap is $2 p + 1 > p \geq m$ . Hence $p^{2} < p^{2} + m < p^{2} + 2 p + 1 = (p + 1)^{2} .$ A length strictly between two consecutive squares is not a square. So $a^{p^{2} + m} \in / L$ , contradicting condition 3.

Verify: $p = 3, m = 3$ (largest allowed): $9 + 3 = 12$ , and $9 < 12 < 16$ ✓, $12$ is not a perfect square ✓. $■$

Example 4 — Cell D: three blocks with a relation

Worked example

$L = {a^{i} b^{j} c^{k} : k = i + j}$ is not regular Forecast: if we grow the $a$ -block but keep the $c$ -block fixed, does $k = i + j$ survive? Guess.

Step 1. Assume regular ⇒ $p$ . Why this step? Standard proof-by-contradiction opening: suppose $L$ regular so the lemma supplies a pumping length $p$ we can turn against it.

Step 2. Choose $w = a^{p} b^{p} c^{2 p}$ . Check: $i = p, j = p, k = 2 p = i + j$ ✓, so $w \in L$ , $∣ w ∣ = 4 p \geq p$ . Why? Put the $a$ -block first so the leash pins $y$ to the $a$ 's; then pumping changes $i$ but leaves $k$ fixed.

Step 3. Adversary: $w = x y z$ , $∣ x y ∣ \leq p$ (condition 2). First $p$ symbols are all $a$ , so $y = a^{m}$ , $m \geq 1$ (condition 1). Why? The leash.

Step 4. Pump up, $i = 2$ : $a^{p + m} b^{p} c^{2 p}$ . Now $i^{'} = p + m, j^{'} = p, k^{'} = 2 p$ . Why? Extra $a$ 's raise $i + j$ to $p + m + p = 2 p + m$ , but $k$ stays $2 p$ .

Step 5. Need $k^{'} = i^{'} + j^{'}$ : $2 p = 2 p + m$ ⇒ $m = 0$ , contradicting $m \geq 1$ . So the pumped string $\in / L$ , contradicting condition 3.

Verify: $p = 2, m = 1$ : $a^{3} b^{2} c^{4}$ . Test $k = i + j$ : $4 = ? 3 + 2 = 5$ , false ✓ (correctly rejected). $■$

Example 5 — Cell E: degenerate & boundary care

Worked example Does

${a^{n} b^{n}}$ contain the empty string, and does that break the proof? Forecast: the string $ε$ (length $0$ ) is in $L$ with $n = 0$ . Can the adversary force us to pump $ε$ ? Guess.

Step 1. The lemma only constrains strings with $∣ w ∣ \geq p$ . We are free to choose $w$ ; we chose $w = a^{p} b^{p}$ with $∣ w ∣ = 2 p \geq p \geq 1$ . So $w \neq = ε$ . Why this matters? Short strings (like $ε$ , $ab$ ) may pump fine — the lemma allows some strings to be pumpable. Non-regularity needs only one un-pumpable long string, and we control which one.

Step 2. Smallest legal $p$ is $1$ . If an adversary claims $p = 1$ : our $w = a^{1} b^{1} = ab$ , $∣ w ∣ = 2 \geq 1$ . First $1$ symbol is $a$ , so $y = a$ , $m = 1$ . Pump $i = 2$ : $aab$ , which has $2$ $a$ 's and $1$ $b$ ⇒ $\in / L$ . Why check $p = 1$ ? We must beat every $p \geq 1$ , including the smallest. The argument survives.

Step 3. Degenerate $y$ ? Condition 1 ( $∣ y ∣ \geq 1$ ) forbids $y = ε$ , so the adversary can never hand us an empty loop. The contradiction always uses $m \geq 1$ . Why this step? We close the last edge case — an empty loop would produce $x y^{i} z = w$ for all $i$ and break the attack, but condition 1 rules it out.

Verify: $p = 1$ case: $aab$ has $a$ -count $2$ , $b$ -count $1$ , $2 \neq = 1$ ✓ rejected. Boundary is safe. $■$

Example 6 — Cell F: non-regular yet PASSES the lemma (do NOT conclude regular)

Worked example

$L = {a^{i} b^{j} c^{k} : i, j, k \geq 0, and (i = 1 \Rightarrow j = k)}$ passes the pumping lemma but is not regular Forecast: we will show every long string can be pumped and stay in $L$ — so the lemma raises no alarm. Does that let us call $L$ regular? Guess — this is the trap.

The forbidden situation in $L$ is exactly: $a$ -count equal to $1$ while $j \neq = k$ . Every other string is in $L$ , because the implication " $i = 1 \Rightarrow j = k$ " is automatically true whenever $i \neq = 1$ (a false hypothesis makes an implication true). Keep that single bad case in mind.

Step 1. We claim $L$ satisfies the pumping lemma with pumping length $p = 2$ . To pass the lemma we must show: for every $w \in L$ with $∣ w ∣ \geq 2$ , there is a split $w = x y z$ with $∣ y ∣ \geq 1$ , $∣ x y ∣ \leq 2$ , such that $x y^{i} z \in L$ for all $i \geq 0$ . We exhibit one good split per case. Why this step? Passing the lemma is itself an $\exists$ -statement about a split; we must actually produce a working split for every witness $w$ , not just assert it.

Step 2. Every $w \in L$ has the form $a^{i} b^{j} c^{k}$ . Take $w$ with $∣ w ∣ \geq 2$ . We choose the split by looking at the first symbol, so we always place $y$ inside whichever block starts the string; this way the three adversarial regions ( $a$ -, $b$ -, $c$ -block) are all covered. Why this step? This is the crux the reviewer wants: we must handle each block a loop could sit in, and the first-symbol rule tells us exactly which block $y$ lands in.

Step 3 (Case $i \geq 2$ ). The string starts with at least two $a$ 's. Choose $x = ε$ and $y = a$ (so $∣ y ∣ = 1$ , $∣ x y ∣ = 1 \leq 2$ ). Pumping gives $a^{i - 1 + i_{p}} b^{j} c^{k}$ , where $i_{p} \geq 0$ is the pumping index (number of copies of $y$ ). Its $a$ -count is $i - 1 + i_{p}$ , which ranges over $i - 1, i, i + 1, \dots$ as $i_{p} = 0, 1, 2, \dots$ . Since $i \geq 2$ , the smallest value is $i - 1 \geq 1$ , and the value equals $1$ only when $i = 2$ and $i_{p} = 0$ . Why this step? We must locate the one dangerous pumped string (the one whose $a$ -count could hit $1$ ).

Step 3b (removing the danger). If $i = 2$ , instead choose $x = ε, y = aa$ (still $∣ x y ∣ = 2 \leq 2$ ). Now the $a$ -count is $i - 2 + 2 i_{p} = 2 i_{p}$ , taking values $0, 2, 4, \dots$ — it never equals $1$ . For $i \geq 3$ , keep $y = a$ : the $a$ -count $i - 1 + i_{p} \geq 2$ for all $i_{p} \geq 0$ , so again it never equals $1$ . Why this step? The single criterion is "keep the $a$ -count away from $1$ ." Doubling the loop ( $y = aa$ ) when $i = 2$ shifts counts onto even numbers, dodging $1$ ; for $i \geq 3$ the count already starts at $\geq 2$ , so a single- $a$ loop is fine. Whenever the $a$ -count is $\neq = 1$ , the clause " $i = 1 \Rightarrow j = k$ " is vacuously true, so $x y^{i_{p}} z \in L$ .

Step 4 (Case $i = 1$ ). Then $w = a b^{j} c^{k}$ with $j = k$ (else $w \in / L$ ). Choose $x = ε, y = a$ ( $∣ x y ∣ = 1 \leq 2$ ). Pumping gives $a^{i_{p}} b^{j} c^{k}$ . For $i_{p} \geq 2$ the $a$ -count is $\geq 2 \neq = 1$ (clause vacuous, in $L$ ); for $i_{p} = 1$ we recover $w$ (in $L$ since $j = k$ ); for $i_{p} = 0$ we get $b^{j} c^{k}$ with $a$ -count $0 \neq = 1$ (clause vacuous, in $L$ ). So all $i_{p} \geq 0$ stay in $L$ . Why this step? This handles the delicate $i = 1$ witnesses; pumping the lone $a$ only ever moves the count to $0$ or $\geq 2$ , both of which switch the constraint off, or back to $1$ where $j = k$ already holds.

Step 5 (Case $i = 0$ ). Then $w = b^{j} c^{k}$ (no $a$ 's). The first symbol is $b$ (or $c$ if $j = 0$ ). Choose $y$ = that first symbol, $∣ x y ∣ = 1 \leq 2$ . Pumping changes only the $b$ -count (or $c$ -count) and keeps the $a$ -count at $0$ ; since $0 \neq = 1$ the clause is vacuous, so every $x y^{i_{p}} z \in L$ . Why this step? This is the $b$ -block / $c$ -block adversarial region; pumping there never creates an $a$ , so the special constraint stays switched off in all pumps.

Conclusion of passing. In every case ( $i \geq 2$ , $i = 1$ , $i = 0$ ) we produced a split whose pumps all remain in $L$ . Hence $L$ passes the pumping lemma — it gives us no contradiction.

Step 6 (but $L$ is not regular). Intersect $L$ with the regular language $a b^{*} c^{*}$ (one $a$ , then $b$ 's, then $c$ 's). This forces $i = 1$ , so the surviving strings are exactly ${a b^{j} c^{k} : j = k} = {a b^{n} c^{n} : n \geq 0}$ — an equal-count language, non-regular by the Example 1 argument. Since regular languages are closed under intersection, if $L$ were regular this intersection would be regular too — contradiction. So $L$ is not regular. Why this step? When pumping cannot fail, we switch tools: intersect with a regular set to isolate a known non-regular core, then use closure to transfer the contradiction back to $L$ .

Verify (logic checks): with $i = 0, j = 2, k = 5$ the clause " $i = 1 \Rightarrow j = k$ " has a false hypothesis, so it is true ⇒ $b^{2} c^{5} \in L$ ✓. With $i = 1, j = 2, k = 2$ the hypothesis is true and $j = k$ holds ⇒ $abb cc \in L$ ✓. With $i = 1, j = 2, k = 3$ the hypothesis is true but $j \neq = k$ ⇒ $abb ccc \in / L$ ✓ (this is the only kind of excluded string). $■$

Example 7 — Cell G: real-world word problem (balanced brackets)

Worked example The "matched parentheses" language

$L = {(^{n})^{n} : n \geq 0}$ is not regular — so a regex alone can't validate nesting. Forecast: a text editor wants to check that every ( has a matching ) with correct nesting depth. Can a plain regex (= a DFA) do it? Guess.

Step 1. Model: symbol ( $= a$ , symbol ) $= b$ . Then $L = {a^{n} b^{n}}$ — identical to Example 1. Assume regular ⇒ $p$ . Why this step? We recast brackets as letters so the equal-count machinery applies, then open the contradiction proof by assuming $L$ regular to obtain a pumping length $p$ we can exploit.

Step 2. Choose $w = (^{p})^{p}$ , length $2 p \geq p$ . Why? Front-load the opens; the leash (condition 2) pins $y$ to opens.

Step 3. $∣ x y ∣ \leq p$ (condition 2) ⇒ $y = (^{m}$ , $m \geq 1$ (condition 1). Pump down, $i = 0$ : $(^{p - m})^{p}$ . Why $i = 0$ ? Removing opens leaves more closes than opens — unbalanced.

Step 4. $(^{p - m})^{p}$ has $p - m$ opens and $p$ closes; $p - m \neq = p$ , so it is not balanced ⇒ $\in / L$ , contradicting condition 3.

Verify: $p = 3, m = 1$ : (( ))) = $(^{2})^{3}$ has $2$ opens, $3$ closes ⇒ unbalanced ✓. Consequence: you need a stack — a pushdown automaton — hence the Pumping Lemma for Context-Free Languages governs bracket matching, not the regular one. $■$

Example 8 — Cell H: exam twist via closure

Worked example Show

$L = {w \in {a, b}^{*} : #_{a} (w) \neq = #_{b} (w)}$ (unequal $a$ and $b$ counts) is not regular. Forecast: attacking " $\neq =$ " directly is awkward — pumping might keep the counts unequal. What language is easier to attack? Guess.

Step 1. Suppose $L$ is regular. Regular languages are closed under complement, so the complement $\overline{L} = {w : #_{a} (w) = #_{b} (w)}$ would also be regular. Why this step? We open by assuming $L$ regular (the contradiction hypothesis), then note closure under complement transfers regularity to $\overline{L}$ , which is a cleaner " $=$ " target than the messy " $\neq =$ " of $L$ .

Step 2. Now attack $\overline{L}$ . Assume it's regular ⇒ $p$ . Choose $w = a^{p} b^{p} \in \overline{L}$ (equal counts), $∣ w ∣ = 2 p \geq p$ . Why? Standard equal-count front-loading so the leash traps $y$ in the $a$ -block.

Step 3. $∣ x y ∣ \leq p$ (condition 2) ⇒ $y = a^{m}$ , $m \geq 1$ (condition 1). Pump up, $i = 2$ : $a^{p + m} b^{p}$ , counts $p + m \neq = p$ ⇒ $\in / \overline{L}$ , contradicting condition 3. Why? Breaking equality is exactly what leaves $\overline{L}$ .

Step 4. So $\overline{L}$ is not regular. But we showed " $L$ regular ⇒ $\overline{L}$ regular." Contrapositive: $\overline{L}$ not regular ⇒ $L$ not regular. Why this step? The closure fact runs both ways via its contrapositive, letting the contradiction about $\overline{L}$ rebound onto $L$ .

Verify: $p = 2, m = 1$ : $a^{3} b^{2}$ , counts $3 \neq = 2$ ✓ leaves $\overline{L}$ ; and $a^{3} b^{2} \in L$ (unequal) ✓ — consistent with $L$ being the complement. $■$

Recap of the mechanisms

The diagram below (readable in words) shows the shared spine of every attack: you pick $w$ depending on $p$ → the constraint $∣ x y ∣ \leq p$ pins $y$ → then one of four traps fires (equal-count pumps up at $i = 2$ ; palindrome pumps down at $i = 0$ ; sparse-length uses the gap argument; multi-block breaks the relation) → each yields $x y^{i} z \in / L$ → contradiction, so $L$ is not regular. A separate branch shows the Cell-F escape hatch: when pumping does not fail, you must instead use closure or Myhill–Nerode.

Active Recall

Recall In Example 3, why does

$∣ y ∣ \leq p$ matter rather than where $y$ sits? The string is all $a$ 's, so we cannot pin the location of $y$ ; but the leash bounds its size $m \leq p$ , and the gap between consecutive squares at $p^{2}$ is $2 p + 1 > p \geq m$ , so the pumped length can't reach the next square.

Recall Example 6 passes the pumping lemma. What did we conclude and why?

Nothing about regularity from the lemma (passing is not sufficient). We proved non-regularity separately using intersection with the regular set $a b^{*} c^{*}$ to isolate ${a b^{n} c^{n}}$ , then closure under intersection.

Recall Example 8's trick in one line.

Complement turns " $\neq =$ " into " $=$ "; attack the equal-count complement with pumping, then use closure under complement to transfer non-regularity back.

Recall Why is

$w = ε$ never a problem for our proofs? Because we always choose $w$ ourselves with $∣ w ∣ \geq p \geq 1$ , so our witness is never the empty string; and condition 1 ( $∣ y ∣ \geq 1$ ) forbids an empty loop, so the adversary can't hand us $ε$ as the pumped piece either.