Pumping Lemma for Regular Languages

If L is regular, there is a constant n such that every w ∈ L with |w| ≥ n can be split as w = xyz where:

1. |xy| ≤ n
2. |y| ≥ 1
3. xyⁱz ∈ L for all i ≥ 0

It's used to prove a language is not regular (by contradiction).

Proof: L = {aᵏbᵏ | k ≥ 0} Is Not Regular

Assume L is regular, with pumping length n.
Choose w = aⁿbⁿ ∈ L, |w| = 2n ≥ n.
Since |xy| ≤ n, x and y contain only a's:  y = aᵖ, p ≥ 1.
Pump i = 2:  xy²z = aⁿ⁺ᵖbⁿ.
Number of a's ≠ number of b's  ⇒  xy²z ∉ L.
Contradiction ⇒ L is NOT regular.

Closure Properties of Regular Languages

Decision Problems (All Decidable for Regular Languages)

Emptiness, finiteness, membership, equivalence of two DFAs and subset testing.