Lecture 7 - The Pumping Lemma and Nonregular Languages
(Skeleton for Fall 2026.)
Why Some Languages Are Not Regular
TODO: finite memory intuition; the 0^n 1^n running example.
The Pumping Lemma
TODO: statement with all quantifiers spelled out (the definition drill applies here with force: students restate the full lemma before every use); the pigeonhole proof.
Pumping Lemma Proofs as a Game
TODO: the adversary game framing (demon picks p, you pick s, demon picks the split, you pick i); worked examples; classic student mistakes (picking the split yourself).