Using the Pumping Lemma to Prove Non-Regularity
What You'll Learn
You'll learn how to apply the Pumping Lemma by contradiction to formally prove that certain languages—like {0^n 1^n}—cannot be recognized by any DFA or regular expression.
The Core Technique: Proof by Contradiction
The Pumping Lemma gives us conditions that every regular language must satisfy. To prove a language is non-regular, we assume the opposite (that it is regular), apply the Pumping Lemma, and derive a contradiction.
The Contradiction Strategy
- Assume the language L is regular
- Apply the Pumping Lemma: there exists a pumping length p
- Choose a clever string s in L with length ≥ p
- Consider all possible ways to split s = xyz (where |xy| ≤ p and |y| > 0)
- Show that pumping (xy²z or xy⁰z) produces a string not in L
- Conclude contradiction—L cannot be regular
Example: {0^n 1^n} is Not Regular
Let's prove the classic language of equal 0s followed by equal 1s is non-regular.
Assume {0^n 1^n} is regular with pumping length p.
Choose s = 0^p 1^p (clearly in the language, length 2p ≥ p).
Split: By the lemma, s = xyz where |xy| ≤ p and |y| > 0. Since |xy| ≤ p, both x and y consist only of 0s.
Pump: Consider xy²z = x(yy)z. This adds extra 0s but keeps the same number of 1s. So xy²z has more 0s than 1s and is not in {0^n 1^n}.
Contradiction! The Pumping Lemma fails, so {0^n 1^n} cannot be regular.
Why This Works
The key is choosing a string where any valid split forces the "pump" to unbalance some crucial property the language requires—like equal counts or nested structure.
Key Takeaway: The Pumping Lemma proves non-regularity by assuming regularity, forcing a split, pumping strategically, and showing the result breaks the language's defining property—yielding a contradiction.