Pumping Lemma Game

The lemma is taught as a formula, but it is a two-player game with alternating quantifiers — ∃n, ∀w, ∃xyz, ∀i. You play the ∀ moves, the engine plays the ∃ moves, and it plays to win: it checks every decomposition and plays the one that is hardest to beat.

Prove a language is not regular

You attack. Beat the engine's best decomposition and the proof writes itself.

proveeasyEqual zeros then onesL = { 0ⁿ1ⁿ : n ≥ 0 }provemediumNo more zeros than onesL = { 0ⁿ1ᵐ : n ≤ m }provemediumBalanced parenthesesL = { w ∈ {(,)}* : w is balanced }provehardA word doubledL = { ww : w ∈ {0,1}* }provehardPrime-length strings of zerosL = { 0ⁱ : i is prime }provemediumEqual a-b-c blocksL = { aⁿbⁿcⁿ : n ≥ 0 }

Defend a regular language

Reverse mode: you claim n and split; the engine attacks. Surviving teaches why the lemma cannot prove regularity.

decideeasyEnds in 01 (regular!)L = { w ∈ {0,1}* : w ends in 01 }decideeasyAn even number of 0s (regular!)L = { w ∈ {0,1}* : the number of 0s in w is even }

The CFL variant

w = uvxyz with |vxy| ≤ n — v and y pump together. These languages are not even context-free.

provehardA word doubledL = { ww : w ∈ {0,1}* }provehardPrime-length strings of zerosL = { 0ⁱ : i is prime }provemediumEqual a-b-c blocksL = { aⁿbⁿcⁿ : n ≥ 0 }