Course contentsShow
← Computer Science
Lesson 1807 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Using the Pumping Lemma to Prove Non-Regularity

Apply pumping lemma by contradiction to show languages like {0^n 1^n} are not regular.

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

  1. Assume the language L is regular
  2. Apply the Pumping Lemma: there exists a pumping length p
  3. Choose a clever string s in L with length ≥ p
  4. Consider all possible ways to split s = xyz (where |xy| ≤ p and |y| > 0)
  5. Show that pumping (xy²z or xy⁰z) produces a string not in L
  6. 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.