THEORY OF COMPUTATION // PROTOCOL 001

isn't just
a formula.

Powered by Finite States*

THE PUMPING LEMMA A beginner-friendly deep-dive into why some languages break machines.
SCROLL
DEFINITION

The Core Dilemma

A Finite State Automaton (FSA) has no memory. It only knows its current state. Feed it a string longer than its state count and, by the Pigeonhole Principle, it must revisit a state — creating a repeatable loop.

The Pumping Lemma weaponises that loop. If every string in a language can be "pumped" (its loop repeated endlessly) and still stay in the language, it might be regular. If we find even one string where pumping breaks it — the language is NOT regular.

p
Pumping Length — the threshold above which every string must contain a loop.
|y| > 0
The pumpable segment y can never be empty.
|xy| ≤ p
The loop must appear within the first p characters.
S = XYZ· XYnZ· |y| > 0· |xy| ≤ p· n ≥ 0· NOT REGULAR· S = XYZ· XYnZ· |y| > 0· |xy| ≤ p· n ≥ 0· NOT REGULAR·
S = XYZ

Deconstructing
the string

01
X — The Prefix
The part before the loop. The FSA processes x as it advances through initial states toward the repeated cycle.
S = XYZ
02
Y — The Loop
The pumpable segment. Because the automaton returns to the same state, this portion can repeat 0, 1, 2... infinite times.
S = XYnZ
03
Z — The Suffix
Everything after the loop. It carries the balance of the string. Pump y, and z stays fixed — breaking the pattern.
S = XYZ
FORMAL PROOF

The
Enemy Game

A proof by contradiction. You vs. a hypothetical FSM that claims it can recognise a non-regular language.

①
ENEMY speaks

Assumes the language is regular. Provides you with a pumping length p.

②
YOU respond

Carefully choose a string s ∈ L with |s| ≥ p. Classic choice: aᵖbᵖ.

③
ENEMY speaks

Partitions s = xyz adhering strictly to |y|>0 and |xy|≤p. The y must fall in the aᵖ region.

④
YOU win

Pump to n = 2. The result aᵖ⁺ᵏbᵖ has more a's than b's. It's NOT in the language. Contradiction. Q.E.D.

EXAMPLES

Who breaks
the machine?

L₁ = { aⁿbⁿ | n≥0 }
NOT REGULAR
Pumping 'a' causes a>b imbalance. No FSM can count arbitrarily.
L₂ = { aⁿb²ⁿ | n≥0 }
NOT REGULAR
Changing the count of a breaks the 1:2 ratio irreparably.
L₃ = { (ab)ⁿ | n≥0 }
REGULAR
The repeating unit "ab" is itself the pumpable y. No imbalance is created.
L₄ = { aⁿ | n is prime }
NOT REGULAR
Pumping changes the count to a non-prime. Primes can't be finite-state-counted.

PUMPING LEMMA SIMULATOR

See it
destabilise.

ENTER RL SIMULATOR

Interact with a live string-pumping visualisation of L = { PⁿDⁿ }

S = UVXYZ· UVnXYnZ· |vy| > 0· |vxy| ≤ p· n ≥ 0· NOT CONTEXT-FREE· S = UVXYZ· UVnXYnZ· |vy| > 0· |vxy| ≤ p· n ≥ 0· NOT CONTEXT-FREE·
CONTEXT-FREE LANGUAGES

Beyond
regular.

Context-Free Languages (CFLs) are more powerful than regular languages — they can be recognised by Pushdown Automata (PDAs) which have a stack for memory. But even PDAs have limits.

The CFL Pumping Lemma splits every sufficiently long string into five parts: s = uvxyz. Both v and y can be pumped simultaneously. If pumping breaks the language, it cannot be context-free.

5
Parts — the string is split into u, v, x, y, z instead of the RL's three-way split.
|vy| > 0
At least one of the pumpable segments must be non-empty.
|vxy| ≤ p
The pumpable region and its center are bounded by the pumping length.
COMPARISON

Regular vs
Context-Free

REGULAR LANGUAGES

Pumping Lemma (RL)

Splits a string into 3 parts (x, y, z). Only the single loop segment y is pumped. Used to prove a language is not regular.

s = xyz → xynz
CONTEXT-FREE LANGUAGES

Pumping Lemma (CFL)

Splits a string into 5 parts (u, v, x, y, z). Two segments v and y are pumped simultaneously. Used to prove a language is not context-free.

s = uvxyz → uvnxynz
S = UVXYZ

The Five-Part
Decomposition

u
PREFIX
The initial segment before any pumpable region. Stays fixed during pumping.
v
PUMP 1
The first pumpable segment — pumped in sync with y. Derived from the parse tree's repeated variable.
x
CENTER
The "core" between the two pumps. Generated by the deepest occurrence of the repeated variable.
y
PUMP 2
The second pumpable segment. Pumped simultaneously with v — their counts always match.
z
SUFFIX
Everything after the pumps. Remains fixed. Pumping v and y into the string distorts the overall balance.
FORMAL CONDITIONS

The Three
Constraints

①
|vxy| ≤ p
The total length of the pumpable region plus its center cannot exceed the pumping length p. This constrains where the parse tree's repeated variable appears.
②
|vy| > 0
At least one of v or y must be non-empty. The pump cannot be trivial — there must be actual content to repeat.
③
uvixyiz ∈ L, ∀i ≥ 0
For ALL pump counts i, the resulting string must remain in the language. If any pump count produces a string outside L, the language is not context-free.
CFL PROOF

The Parse Tree
Adversary Game

The CFL pumping lemma proof mirrors the RL version but with a twist — two segments are pumped simultaneously, reflecting the left/right branches of a parse tree.

①
ADVERSARY speaks

Assumes the language is context-free. Provides pumping length p (tied to the grammar's variable count).

②
YOU respond

Choose a string s ∈ L with |s| ≥ p. Classic: aᵖbᵖcᵖ (three-way balance).

③
ADVERSARY speaks

Partitions s = uvxyz with |vxy| ≤ p and |vy| > 0. Since |vxy| ≤ p, v and y can touch at most 2 of the 3 symbol blocks.

④
YOU win

Pump i = 2. Since v and y can't span all three symbols, pumping increases only 1 or 2 counts — the three-way balance is destroyed. Not in L. Contradiction. Q.E.D.

EXAMPLES

Who breaks
the PDA?

L₁ = { aⁿbⁿcⁿ | n≥0 }
NOT CF
Pumping can only affect 2 of 3 symbol types. The three-way balance is always broken.
L₂ = { ww | w ∈ {a,b}* }
NOT CF
Pumping destroys the exact-copy structure. The two halves can never match after pumping.
L₃ = { aⁿbⁿ | n≥0 }
CONTEXT-FREE
A PDA with a stack can count a's vs b's. CFG: S → aSb | ε. Passes the pumping lemma.
L₄ = { aⁿbⁿcⁿdⁿ | n≥0 }
NOT CF
Even harder than aⁿbⁿcⁿ. Four-way balance is impossible to maintain under pumping.
L₅ = { an² | n≥0 }
NOT CF
Pumping adds a linear amount to a quadratic-length string, escaping perfect square lengths.

CFL PUMPING LEMMA SIMULATOR

Watch the parse tree
collapse.

ENTER CFL SIMULATOR

Interact with a live CFL pumping visualisation of L = { aⁿbⁿcⁿ }