Pumping Lemma for Regular Languages

Pumping Lemma for Regular Languages

The pumping lemma is a tool for proving that a language is NOT regular. It describes a property that all regular languages must satisfy. If a language fails this property, it cannot be regular. Think of it as a "test" — if your language can't pass, it's not regular.

The Lemma

For every regular language L, there exists a pumping length p such that every string s in L with |s| >= p can be split into three parts s = xyz, where:

Conditions:
  1. |xy| <= p      (the pumped part is near the start)
  2. |y| > 0         (the pumped part is non-empty)
  3. For all i >= 0: xy^iz ∈ L  (pumping y any number of
                                  times stays in L)

Intuition:
  If L is regular, the DFA has p states. Any string longer
  than p must repeat a state. The loop (y) can be repeated
  any number of times without leaving the language.

How to Use It (to Disprove Regularity)

To prove L is NOT regular using the pumping lemma:

Step 1: Assume L IS regular (for contradiction)
Step 2: Let p be the pumping length
Step 3: Choose a string s ∈ L with |s| >= p
        (pick s carefully to create a contradiction)
Step 4: For every possible split s = xyz satisfying
        conditions 1 and 2, find an i >= 0 such that
        xy^iz ∉ L
Step 5: Contradiction! L is not regular.

Example: {0^n 1^n | n >= 0} is NOT regular

Let's prove that the language L = {0^n 1^n | n >= 0} (equal number of 0s and 1s) is not regular.

Assume L is regular. Let p be the pumping length.
Choose s = 0^p 1^p (p zeros followed by p ones).
  |s| = 2p >= p ✓

For any split s = xyz with |xy| <= p and |y| > 0:
  The string x consists of only 0s
  The string y consists of only 0s (since |xy| <= p)
  The string z consists of remaining 0s and all 1s

Now pump: xy^2z has more 0s than the original s,
but the same number of 1s.
  # of 0s > p, # of 1s = p
  So xy^2z has more 0s than 1s
  Therefore xy^2z ∉ L

Contradiction! L = {0^n 1^n} is NOT regular.

Important Notes

The pumping lemma gives a necessary condition for regularity, not a sufficient one. If a language satisfies the pumping lemma, it doesn't automatically mean it's regular. However, if it fails, it's definitely not regular. For proving regularity, you need to construct a DFA, NFA, or regex.

The choice of string s is critical. A bad choice won't produce a contradiction. You need to pick s such that no matter how it's split, pumping creates a string outside the language.