THE PUMPING LEMMA FOR REGULAR LANGUAGES: IF L is a regular language, THEN there exists a constant p ≥ 1 (the PUMPING LENGTH) such that EVERY string w ∈ L with |w| ≥ p can be written as w = x y z satisfying ALL THREE conditions: (1) |y| ≥ 1 y is NOT empty (2) |xy| ≤ p x and y occur within the first p symbols (3) x yⁱ z ∈ L for ALL i ≥ 0 ── WHY IT IS TRUE — THE PIGEONHOLE ARGUMENT ──────────────── Let the minimal DFA for L have p states. Take any w ∈ L with |w| ≥ p. Reading w visits |w| + 1 states, and the first p+1 of those are drawn from only p distinct states — SO BY THE PIGEONHOLE PRINCIPLE SOME STATE IS VISITED TWICE within the first p symbols. Let x be the prefix read before the first visit, y the portion read between the two visits (so y ≠ ε, giving condition 1, and both visits are within the first p symbols, giving condition 2), and z the remainder. READING y TAKES THE MACHINE FROM A STATE BACK TO ITSELF — IT IS A LOOP. So the loop can be traversed any number of times, including zero, and the machine still ends where it did. Hence x yⁱ z is accepted for every i ≥ 0, which is condition 3. THAT IS THE WHOLE PROOF, AND IT IS WORTH REMEMBERING AS AN ARGUMENT RATHER THAN A FORMULA: a finite machine reading a long enough string must repeat a state, and a repeated state is a loop that can be pumped. ── HOW IT IS USED — PROOF BY CONTRADICTION ───────────────── THE LEMMA SAYS "REGULAR ⟹ PUMPABLE". Its contrapositive is "NOT PUMPABLE ⟹ NOT REGULAR", and that is how it is applied. THE PROOF IS A GAME AGAINST AN ADVERSARY, and framing it that way prevents the standard errors: 1. THE ADVERSARY chooses p. You know nothing about it, so your argument must work for EVERY p. 2. YOU choose w ∈ L with |w| ≥ p. THIS IS YOUR ONLY FREE CHOICE AND THE WHOLE PROOF DEPENDS ON MAKING IT WELL. 3. THE ADVERSARY splits w = xyz however they like, subject to |y| ≥ 1 and |xy| ≤ p. You must handle EVERY legal split. 4. YOU choose i and show x yⁱ z ∉ L. THE TWO ERRORS THAT INVALIDATE A PROOF: · CHOOSING THE SPLIT YOURSELF. Writing "let y = a" is wrong — the adversary chooses y, so you must argue about all possible y. THE GOOD NEWS IS THAT CONDITION (2) USUALLY CONSTRAINS THE ADVERSARY SO SEVERELY THAT ALL SPLITS LOOK THE SAME, which is exactly what a well-chosen w achieves. · CHOOSING w BADLY. A string that can be pumped proves nothing, even if the language is genuinely non-regular. ── THE STANDARD WORKED PROOF ─────────────────────────────── CLAIM: L = { aⁿbⁿ : n ≥ 0 } is NOT regular. PROOF. Suppose L is regular. Let p be the pumping length. CHOOSE w = aᵖ bᵖ. Then w ∈ L and |w| = 2p ≥ p, so the lemma applies. By condition (2), |xy| ≤ p. SINCE THE FIRST p SYMBOLS OF w ARE ALL a's, BOTH x AND y CONSIST ENTIRELY OF a's. So y = aᵏ for some k ≥ 1, by condition (1). TAKE i = 2. Then x y² z = a^(p+k) bᵖ This has p + k a's and p b's, and k ≥ 1, so the counts DIFFER. Therefore x y² z ∉ L, contradicting condition (3). Hence L is not regular. ∎ CONCRETELY, with p = 3 and k = 1: w = aaabbb, and pumping gives aaaabbb — four a's and three b's, which is not in L. i = 0 works equally well, giving aabbb. NOTICE WHAT MADE THE CHOICE OF w GOOD: putting all the a's first meant condition (2) FORCED y into the a-block, eliminating every other case. A LAZIER CHOICE SUCH AS w = (ab)ᵖ WOULD HAVE LEFT THE ADVERSARY FREE TO PUT y ANYWHERE and the proof would have been far messier. ── MORE NON-REGULAR LANGUAGES AND THE w TO CHOOSE ────────── { aⁿbⁿ } w = aᵖbᵖ { ww : w ∈ Σ* } w = aᵖbaᵖb { aⁿbᵐ : n > m } w = a^(p+1)bᵖ palindromes over {a,b} w = aᵖbaᵖ { aⁿ : n is prime } w = a^q for a prime q > p { aⁿ : n is a perfect square } w = a^(p²) { aⁿbᵐcⁿ⁺ᵐ } w = aᵖbᵖc²ᵖ balanced parentheses w = (ᵖ)ᵖ FOR { aⁿ : n PRIME } the argument needs one extra step: after pumping, the length becomes q + (i−1)k, and CHOOSING i = q + 1 GIVES LENGTH q + qk = q(1 + k), which is composite since both factors exceed 1. A NEAT TRICK WORTH REMEMBERING.

── THE CRITICAL LOGICAL POINT ────────────────────────────── THE PUMPING LEMMA IS A NECESSARY CONDITION, NOT A SUFFICIENT ONE. REGULAR ⟹ PUMPABLE. PUMPABLE ⟹ REGULAR IS **FALSE**. So the lemma can PROVE a language is NOT regular, and can NEVER PROVE that one IS regular. A student who "verifies the pumping lemma holds" and concludes the language is regular has committed the converse error. A CONCRETE COUNTEREXAMPLE, worth knowing because it is the standard one: L = { aⁱbʲcʲ : i ≥ 1, j ≥ 0 } ∪ { bʲcᵏ : j, k ≥ 0 } THIS LANGUAGE SATISFIES THE PUMPING LEMMA AND IS NOT REGULAR, and the mechanism is worth following because it shows exactly how the lemma can be evaded. TAKE y TO BE A SINGLE LEADING SYMBOL. · If w = aⁱbʲcʲ with i ≥ 1, let y be one a. Pumping UP gives a^(i+1)bʲcʲ, still in the first set since j = j is unaffected. Pumping DOWN to i = 0 gives bʲcʲ — WHICH LANDS IN THE SECOND SET b*c*, and is therefore still in L even though nothing now constrains the counts. · If w ∈ b*c*, pumping the first symbol keeps it in b*c*. SO EVERY STRING IN L CAN BE PUMPED, and the lemma is satisfied. THE SECOND SET IS A TRAPDOOR: it absorbs exactly the strings that pumping would otherwise push out of the language. YET L IS NOT REGULAR, which Myhill-Nerode shows at once: the strings ab, abb, abbb, … are pairwise distinguishable, because abʲ followed by cʲ is in L while abʲ followed by c^(j+1) is not. Infinitely many equivalence classes, hence no DFA. CHECK IT CONCRETELY: abc ∈ L and abcc ∉ L; abbcc ∈ L and abbccc ∉ L. THE RELIABLE ALTERNATIVE IS THE MYHILL-NERODE THEOREM: Exhibit an INFINITE SET of strings that are PAIRWISE DISTINGUISHABLE — for each pair x, y there is a z with exactly one of xz, yz in L. Then L has infinitely many equivalence classes and CANNOT be regular. FOR { aⁿbⁿ }: take { a, aa, aaa, … }. For i ≠ j, the string bⁱ distinguishes aⁱ from aʲ, since aⁱbⁱ ∈ L but aʲbⁱ ∉ L. Infinitely many classes, so not regular. MYHILL-NERODE IS BOTH NECESSARY AND SUFFICIENT, so it can prove regularity as well as non-regularity — which is why it is the stronger tool, even though the pumping lemma is the one usually taught first. ── PRACTICAL GUIDANCE FOR THE EXAM ───────────────────────── THE TEMPLATE, which should be written out in full: 1. "Assume, for contradiction, that L is regular." 2. "Let p be the pumping length given by the lemma." 3. "Consider w = …, which is in L and has |w| ≥ p." 4. "By condition (2), |xy| ≤ p, so y consists only of …" — THIS IS THE STEP THAT EARNS THE MARKS; state explicitly why the constraint pins down y. 5. "Write y = … with k ≥ 1 by condition (1)." 6. "Take i = …. Then xyⁱz = …, which is not in L because …" 7. "This contradicts condition (3), so L is not regular." ∎ CHOOSING w — THE PRACTICAL RULES: · make it long enough that |w| ≥ p is automatic · ARRANGE IT SO THE FIRST p SYMBOLS ARE UNIFORM, so condition (2) forces y into one block · the standard choice is the "extreme" member of the language for the given p CHOOSING i: · i = 2 (pumping up) works in most counting arguments · i = 0 (pumping DOWN) is often cleaner when the language requires a MINIMUM count, since deleting y breaks it immediately · for arithmetic properties such as primality, choose i to force a composite or otherwise disallowed value ── THE PLACE OF THE RESULT ───────────────────────────────── The pumping lemma completes the picture of regular languages begun in this section: · FINITE AUTOMATA say what CAN be recognised. · REGULAR EXPRESSIONS give an equivalent notation. · MINIMIZATION gives a canonical form. · THE PUMPING LEMMA MARKS THE BOUNDARY — it tells us where the class ENDS. AND THE BOUNDARY IS EXACTLY WHERE UNBOUNDED MEMORY BECOMES NECESSARY, which is precisely the capability added by the stack of a pushdown automaton in the next section. THERE IS A CORRESPONDING PUMPING LEMMA FOR CONTEXT-FREE LANGUAGES, with the string split into FIVE parts instead of three, marking that class's boundary in the same way.