Pumping lemma: equal 0s and 1s

Pumping lemma

If L is regular, there is p ≥ 1 such that every w ∈ L with |w| ≥ p can be split w = xyz where |xy| ≤ p, |y| ≥ 1 and xyⁱz ∈ L for all i ≥ 0.

Proof that L = {w ∈ {0,1}* : #0(w) = #1(w)} is not regular

Assume L is regular with pumping length p.

1. Choose w = 0ᵖ1ᵖ. It has p zeros and p ones, so w ∈ L, and |w| = 2p ≥ p.
2. Since |xy| ≤ p, the substring xy lies in the block of 0's. So y = 0ᵏ with 1 ≤ k ≤ p.
3. Take i = 2: xy²z = 0^(p+k)1ᵖ.
4. It has p + k zeros but only p ones, and k ≥ 1, so the counts are unequal. Therefore xy²z ∉ L.

This contradicts the pumping lemma, so L is not regular. ∎

Alternative proof (closure). If L were regular, then L ∩ 01 would be regular (regular languages are closed under intersection). But L ∩ 01 = {0ⁿ1ⁿ : n ≥ 0}, which is known to be non-regular. Contradiction.