THE PUMPING LEMMA long enough, and a regular language must repeat
A finite automaton has finitely many states, so on any input longer than its state count it must revisit a state — and the loop between the two visits can be repeated (pumped) any number of times with the string still accepted. Turn it around and it is a weapon: if a language has a string that cannot be pumped, no finite automaton recognises it. This is how you prove a language is not regular.
THE TECHNIQUE pump the loop; a non-regular language breaks
Is aⁿbⁿ (equal a’s then b’s) regular? Take aabb, split it xyz with y inside the a-block, and pump: xy²z = aaabb — now 3 a’s, 2 b’s, no longer in the language. The pump broke it, so aⁿbⁿ is not regular. Watch the counts diverge: live demo
HISTORY & CREDIT Rabin-Scott 1959 (regular); Bar-Hillel 1961 (CF)
“The pumping lemma proves a language IS regular.” — no, never. It is a necessary condition, not sufficient: passing it proves nothing (some non-regular languages pump), but failing it proves non-regularity. It is a one-way tool — a disqualifier, not a certificate. cited
1959 · Rabin & Scott — “Finite Automata and Their Decision Problems” (IBM J. Res. Dev.): the regular pumping lemma first appears here, as Lemma 8 (a run longer than the state count repeats a state). 1961 · Bar-Hillel, Perles & Shamir — “On formal properties of simple phrase structure grammars”: the context-free (“Bar-Hillel”) pumping lemma that pumps two substrings, plus an independent rediscovery of the regular case. the mechanism · the pigeonhole principle on states — more input symbols than states forces a repeat, and the repeat is the pump. the CF cousin · the context-free (“Bar-Hillel”) pumping lemma is BHPS 1961’s genuine primary contribution — it pumps two substrings at once, the tool one level up the Chomsky hierarchy.
Note the honesty of it: the lemma is a necessary condition, so it can only ever say “NO, not regular” — never “yes, regular.” A tool that only disqualifies is still decisive, because one un-pumpable string ends the question. Rabin-Scott 1959 (regular) / Bar-Hillel 1961 (CF)
RECOMMEND FOR I-13 the pump breaks the count, computed
Pumping aabb runs on the canonical compiler — the a-count and b-count diverge, so aⁿbⁿ is not regular:
$ i13 run pump.i13 # a^n b^n : pump y='a' inside aabb -> aaabb
aabb : a=2 b=2 balanced (0) -- in the language
aaabb : a=3 b=2 UNbalanced (1) -- pumped once, no longer a^n b^n -> NOT regular
Recommend: the pumping lemma is LIT as a proof, computed — verified that pumping the loop in aabb gives aaabb with a-count 3 ≠ b-count 2, breaking aⁿbⁿ and proving it non-regular, all in native counting. For I-13 it is the honest boundary marker of the regular world (Glushkov/Brzozowski/Hopcroft, 176–178): balanced brackets and aⁿbⁿ need the stack of the pushdown automaton (175), not a DFA — the lemma is the proof of exactly where a finite machine stops and a stack machine must begin. It only ever says “not regular,” which is the whole point.