Pumping lemma: aⁿb²ⁿ not regular

Pumping lemma for regular languages

If L is a regular language, there is a constant p ≥ 1 (the pumping length) such that every string w ∈ L with |w| ≥ p can be written as w = xyz with

1. |xy| ≤ p,
2. |y| ≥ 1 (y ≠ ε),
3. xyⁱz ∈ L for every i ≥ 0.

(p can be taken as the number of states of a DFA for L.)

Proof that L = {aⁿb²ⁿ : n ≥ 1} is not regular

Use proof by contradiction. Assume L is regular, and let p be its pumping length.

1. Choose w = aᵖb²ᵖ. Then w ∈ L (n = p) and |w| = 3p ≥ p.
2. Let w = xyz with |xy| ≤ p and |y| ≥ 1. Since the first p symbols of w are all a, both x and y consist only of a's. So y = aᵏ for some k with 1 ≤ k ≤ p.
3. Pump with i = 2: the string xy²z = a^(p+k) b^(2p).
4. For this to be in L, the number of b's must be twice the number of a's: 2p = 2(p + k), which gives k = 0. But k ≥ 1, so xy²z ∉ L.

This contradicts condition 3 of the lemma. Hence the assumption was false, and L = {aⁿb²ⁿ} is not regular. ∎

(Pumping with i = 0 also works: a^(p−k)b^(2p) has too many b's.)