Pumping Lemma for Regular Languages

A property that all regular languages must satisfy. A necessary (not sufficient) condition for regular languages.

Any sufficiently long string in a regular language can be divided into parts that can be repeated (pumped) any number of times and still remain in the language.

Used to prove a language is not regular.

Versions

Version 1

Suppose $L$ is a language recognized by an FA with $p$ states. Any string $w \in L$ with $\lvert w \rvert \ge p$ can be written as $w = xyz$ where the following conditions hold:

• $\lvert xy \rvert \le p$
  The substring $xy$ lies within the first $p$ characters.
• $\lvert y \rvert \gt 0$
  The substring $y$ must not be empty.
• $xy^iz \in L$ for all $i \ge 0$
  The substring $y$ can be repeated 0 or more times and the resulting string must still belong to $L$.

Deals with an FA with $p$ states.

Version 2

For a regular language $L$, there exists a integer constant $p$ (called the pumping length) such that:

Any string $w \in L$ with $\lvert w \rvert \ge p$ can be written as $w = xyz$ where the version 1’s conditions hold.

Deals with a language alone, and defines the pumping length. More common than version 1.