Weeks 03 and 05–06 · Sipser 1.4 and 2.3
The lemma is a stack of alternating quantifiers, and alternating quantifiers are a two-player game. The adversary moves first and third; you move second and fourth. Win, and the language is not regular — or not context-free.
The adversary claims A is well-behaved, so it hands you a pumping length. You do not choose it — your argument has to survive whatever it names.
Name a string s ∈ A with |s| ≥ p. Write it in terms of
p so the same choice survives a reroll.
It is not random. It enumerates every legal division and searches for one that no i ≤ 8 defeats. So when you win, you have shown that no division works — which is exactly the quantifier the proof needs, and exactly the step students skip.
One language in each list is well-behaved. You will fight it and lose every cut. That is the lesson the one-way direction never lands on a slide: failing to pump proves nothing at all, and the lemma can never certify that a language is regular or context-free.
The input accepts arithmetic in exponents — a^p, a^{2p+1}, 0^{p*p} — so a choice written in terms of p survives a reroll while a literal string dies the moment p changes. Reroll in front of the class before anyone commits.