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

The Pumping Lemma for Regular Languages

A necessary condition for regularity: sufficiently long strings must contain pumpable substrings.

The Pumping Lemma for Regular Languages

What you'll learn: You'll discover a mathematical tool that proves certain languages cannot be regular by exploiting an inherent structural property of DFAs and NFAs.

The Core Idea

Imagine a DFA with a fixed number of states, say 10. If you feed it a string with 15 characters, the DFA must visit at least one state more than once (by the pigeonhole principle). This creates a loop in the computation path.

The Pumping Lemma formalizes this observation: if a language is regular, then every sufficiently long string in that language contains a repeatable (pumpable) substring. You can repeat that middle part zero, one, two, or any number of times, and the resulting strings must all still be in the language.

The Formal Statement

For any regular language L, there exists a constant p (the "pumping length") such that any string s in L with length ≥ p can be split into three parts:

  • s = xyz

where:

  1. |xy| ≤ p (the loop occurs early)
  2. |y| > 0 (the loop is non-empty)
  3. For all i ≥ 0, the string xy^i z is also in L

Why It Matters

The Pumping Lemma is primarily used as a proof technique by contradiction. To prove a language is not regular, you assume it is regular, apply the Pumping Lemma, then show that no matter how you split a carefully chosen string, pumping breaks the language rules—a contradiction.

For example, the language {0^n 1^n | n ≥ 0} cannot be regular because pumping the 0s or 1s independently destroys the balance.

Key Takeaway: The Pumping Lemma states that sufficiently long strings in regular languages must contain a pumpable (repeatable) substring due to state repetition in finite automata—a property used to prove languages are not regular.