Pumping Lemma & Closure Properties of Regular Languages

The Pumping Lemma is a necessary (NOT sufficient!) property satisfied by all regular languages. It is used exclusively as a proof technique by contradiction to prove that a language is NOT regular.

Formal Statement:

If L is a regular language, then there exists a constant integer pumping length p ≥ 1 (the number of states in the minimal DFA) such that every string s \in L with |s| ≥ p can be partitioned into three substrings, s = xyz, satisfying all three conditions simultaneously:

1. |y| > 0 (the pumped substring y is non-empty).

2. |xy| ≤ p (the pumped substring y occurs within the first p symbols of s).

3. For all integers i ≥ 0: x y^i z \in L (the string can be pumped down with i=0 or pumped up with i ≥ 2).

The Adversarial Proof Game:

1. Assume L is regular \implies there exists a pumping length p.

2. Choose a clever test string s \in L expressed in terms of p such that |s| ≥ p (e.g., s = 0^p 1^p).

3. By condition 2 (|xy| ≤ p), y must consist solely of the initial prefix characters (e.g., y = 0^k with k ≥ 1).

4. Pump y with i = 0 (pump down) or i = 2 (pump up). The resulting string x y^2 z has unequal counts, violating language membership \implies Contradiction! Hence L is not regular.