The Pumping Lemma for Regular Languages

Formal Definition

If a language L is regular, then there exists some integer p ≥ 1 (the pumping length) such that every string s in L of length at least p (|s| ≥ p) can be written as s = xyz, satisfying the following conditions:

  • 1. |y| > 0   (The substring y cannot be empty)
  • 2. |xy| ≤ p   (The loop must occur within the first p characters)
  • 3. For all i ≥ 0, xyⁱz ∈ L   (Pumping y any number of times keeps the string in L)

Proof by Contradiction

The Pumping Lemma is primarily used to prove that a language is not regular. To do this, we use a proof by contradiction, commonly structured as a "game" against an adversary:

  1. Assume the language L is regular.
  2. Therefore, there must exist some pumping length p.
  3. We choose a specific string s ∈ L where |s| ≥ p. (This represents a difficult case for the adversary).
  4. The adversary partitions the string into s = xyz such that conditions 1 and 2 hold.
  5. We find at least one pump count i (often i=0 or i=2) where the resulting string xyⁱz ∉ L.
  6. Because condition 3 was broken for every valid partition the adversary could possibly make, our initial assumption was false. The language is not regular.

Invalidity of the Lemma Converse

While the pumping lemma states that all regular languages satisfy the conditions described above, the converse of this statement is not true: a language that satisfies these conditions may still be non-regular. In other words, both the original and the general version of the pumping lemma give a necessary but not sufficient condition for a language to be regular.