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

WHY this lemma exists

A DFA has a fixed, finite set of states. Memory = current state only. So a DFA cannot count without bound — it cannot remember "I have seen exactly $n$ a's" for arbitrarily large $n$ , because that would need infinitely many states. The pumping lemma is the formal weapon that turns "can't count" into a contradiction proof.

The Pumping Lemma (statement)

The lemma is a necessary condition, not sufficient. Passing it does NOT prove regular; failing it proves non-regular.

Deriving it from first principles (the proof)

Setup. $L$ regular ⇒ there is a DFA $M=(Q,\Sigma,\delta,q_0,F)$ accepting $L$ . Let $p = |Q| \quad(\text{number of states}).$

Take any $w \in L$ with $|w| = n \ge p$ . Write $w = a_1 a_2 \dots a_n$ .

Trace the run. Define the sequence of states visited: $r_0 = q_0,\qquad r_k = \delta(r_{k-1}, a_k)\ \ (k=1,\dots,n).$ Since $w\in L$ , $r_n \in F$ .

Pigeonhole. Look at the first $p+1$ states $r_0, r_1, \dots, r_p$ . That's $p+1$ states but only $p$ distinct states exist. So two of them are equal: there exist indices $0 \le j < k \le p \quad\text{with}\quad r_j = r_k.$

Split the string around the repeated state: $x = a_1\dots a_j,\qquad y = a_{j+1}\dots a_k,\qquad z = a_{k+1}\dots a_n.$

Check the three conditions:

$|y| = k - j \ge 1$ because $j < k$ . ✓ (condition 1)
$|xy| = k \le p$ because $k \le p$ . ✓ (condition 2)

Why pumping works (condition 3). Reading $x$ takes $q_0 \to r_j$ . Reading $y$ takes $r_j \to r_k = r_j$ — a self-loop on state $r_j$ . So reading $y$ again leaves us back at $r_j$ : $q_0 \xrightarrow{x} r_j \xrightarrow{y} r_j \xrightarrow{y} r_j \dots \xrightarrow{y} r_j \xrightarrow{z} r_n \in F.$ Thus for every $i\ge 0$ , reading $xy^iz$ ends in $r_n\in F$ , so $xy^iz \in L$ . $\blacksquare$

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

HOW to USE it (the proof-by-contradiction recipe)

It is an adversary game. The lemma gives you $p$ (you don't choose it); you must beat every possible $p$ and every split.

Memory aid for who-chooses-what: ∃p, ∀w, ∃split, ∀i — but for the proof of non-regularity we flip it: we pick $w$ , the adversary picks the split, we pick $i$ .

Worked Examples

Worked example Example 1 —

$L = \{a^n b^n : n \ge 0\}$ is not regular

Assume regular, get $p$ .
Choose $w = a^p b^p$ . Why this $w$ ? It is in $L$ , has length $2p \ge p$ , and concentrates $a$ 's in the first $p$ symbols so condition 2 controls $y$ .
By condition 2, $|xy|\le p$ , and the first $p$ symbols are all $a$ 's. Why does this matter? It forces $x$ and $y$ to consist only of a's. So $y = a^m$ with $m = |y| \ge 1$ .
Pump with $i=2$ : $xy^2z = a^{p+m} b^{p}$ . Why $i=2$ ? It adds extra $a$ 's without touching $b$ 's, breaking the equal-count.
Since $m\ge1$ , $p+m \ne p$ , so $a^{p+m}b^p \notin L$ . Contradiction with condition 3. ⇒ $L$ not regular. ✓

Worked example Example 3 —

$L = \{a^{n^2} : n \ge 0\}$ (perfect-square lengths) is not regular

Assume regular ⇒ $p$ .
Choose $w = a^{p^2}$ . Why? Length is a perfect square $\ge p$ .
Split $w=xyz$ , $1 \le |y| = m \le |xy| \le p$ .
Pump $i=2$ : length becomes $p^2 + m$ . Why does $|y|\le p$ help? Because the gap between consecutive squares at $p^2$ is $(p+1)^2 - p^2 = 2p+1 > p \ge m$ . So $p^2 < p^2+m < p^2 + 2p+1 = (p+1)^2$ .
$p^2+m$ lies strictly between two consecutive perfect squares ⇒ not a perfect square ⇒ $a^{p^2+m}\notin L$ . Contradiction. ⇒ not regular. ✓

Common Mistakes (Steel-manned)

Active Recall

Recall What three conditions must the split

$w=xyz$ satisfy? $|y|\ge1$ ; $|xy|\le p$ ; and $xy^iz\in L$ for all $i\ge0$ .

Recall Which combinatorial principle drives the proof, and what plays the role of "pigeons" and "holes"?

Pigeonhole. Pigeons = the $p+1$ states $r_0\dots r_p$ visited; holes = the $p$ states of the DFA. Two pigeons share a hole ⇒ a repeated state ⇒ a loop $y$ .

Recall Why must your chosen

$w$ depend on $p$ ? Because $p$ is given by the adversary and unknown; $w$ must satisfy $|w|\ge p$ for any $p$ .

Recall Does passing the pumping lemma prove a language is regular?

No. It is necessary, not sufficient. Use Myhill–Nerode or build a DFA to prove regularity.

Recall For

$a^nb^n$ , why does $|xy|\le p$ matter? It forces $y$ to lie entirely in the a-block, so pumping changes the number of a's only, breaking $i=j$ .

Recall Explain it to a 12-year-old.

Imagine a toy train with only a few colored stations and a very long track of letters. If the track is longer than the number of stations, the train must visit some station twice. Whatever loop of track it drove between those two same-color stations, it could drive that loop again and again (or skip it) and still finish at the same place. So if a language is "made by such a train," repeating that middle loop must always still be allowed. If you find a word where repeating the loop gives something not in the language, then no such train (machine) exists — the language is too clever for finite memory.

Flashcards

State the pumping lemma for regular languages.

L

regular,

\exists p\ge1

s.t. every

w\in L,\ |w|\ge p

splits

w=xyz

with

|y|\ge1

|xy|\le p

, and

xy^iz\in L

for all

i\ge0

What is the pumping length

p

in the proof?

The number of states of a DFA accepting

L

(

p=|Q|

Which principle proves the lemma?

Pigeonhole:

p+1

visited states but only

p

states ⇒ a state repeats ⇒ a loop.

What does condition

|xy|\le p

buy you in proofs?

It localizes

y

to the first

p

symbols, letting you force

y

into a specific block.

Which string proves

a^nb^n

non-regular?

w=a^pb^p

, then pump

i=2

to get unequal a's and b's.

Which string proves

\{a^{n^2}\}

non-regular and why?

w=a^{p^2}

; pumping by

m\le p

lands strictly between consecutive squares since the gap is

2p+1>p

Pump up vs pump down — which

i

values?

Up:

i\ge2

; down:

i=0

(i.e.

xz

). Both allowed by condition 3.

Does passing the pumping lemma imply regularity?

No — it's necessary, not sufficient.

Who chooses the split

x,y,z

— you or the adversary?

The adversary (lemma says "there exists"); you must beat all legal splits.

Better tool to prove regularity (not just non)?

Build a DFA/NFA/regex, or use the Myhill–Nerode theorem.

Connections

Finite Automata (DFA NFA) — the source of the finite-state / pigeonhole argument.
Myhill–Nerode Theorem — exact characterization of regularity; proves regularity and non-regularity.
Pigeonhole Principle — combinatorial engine of the proof.
Regular Expressions — equivalent definition of regular languages.
Pumping Lemma for Context-Free Languages — the $uvxyz$ analogue with two loops.
Closure Properties of Regular Languages — sometimes easier than pumping (intersect with a regular set first).

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, pumping lemma ka core idea bahut simple hai. Har regular language ke peeche ek DFA hota hai jiske paas sirf finite number of states hote hain — maan lo $p$ states. Ab agar koi string isse lambi hai ( $|w| \ge p$ ), to machine ko string padhte waqt koi ek state do baar visit karni hi padegi — yeh pigeonhole principle hai (zyada pigeons, kam holes). Jo portion us repeated state ke beech padha gaya, woh ek loop ban jaata hai, jise hum $y$ kehte hain. Loop ka matlab — usko 0 baar, 1 baar, 2 baar, jitni baar chaaho chala sakte ho aur machine same accepting state pe khatam hogi. Isiliye $xy^iz$ bhi language mein hona chahiye, har $i \ge 0$ ke liye.

Yeh lemma hum non-regularity prove karne ke liye use karte hain, ulta tareeke se. Maan lo language regular hai, to $p$ exist karega. Phir tum ek clever string $w$ choose karte ho jo $p$ pe depend kare, jaise $a^pb^p$ . Ab adversary (lemma) split $xyz$ deta hai, par condition $|xy|\le p$ ke wajah se $y$ sirf shuru ke a's mein phasta hai. Phir tum $i=2$ ya $i=0$ choose karke count tod dete ho — a's badh jaate hain par b's same, to $a^{n}b^{n}$ wali equality break ho jaati hai. Contradiction! Matlab language regular thi hi nahi.

Do important traps yaad rakhna. Pehla: split tum nahi chunte, adversary chunta hai — isliye saare possible splits handle karne padte hain (par $|xy|\le p$ tumhari madad karta hai). Doosra: agar koi language pumping lemma pass kar leti hai, iska matlab regular nahi hota — yeh sirf one-way tool hai. Regular prove karna ho to DFA banao ya Myhill–Nerode use karo. Mnemonic "PUMP" yaad rakho: Pigeonhole, Unknown $p$ , Middle $y$ non-empty, Pick $i$ .

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

WHY this lemma exists

The Pumping Lemma (statement)

Deriving it from first principles (the proof)

HOW to USE it (the proof-by-contradiction recipe)

Worked Examples

Common Mistakes (Steel-manned)

Active Recall

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Theory of Computation

Connections