Pumping lemma for regular languages

In the theory of formal languages, the pumping lemma for regular languages is a lemma that describes an essential property of all regular languages. Informally, it says that all sufficiently long strings in a regular language may be pumped—that is, have a middle section of the string repeated an arbitrary number of times—to produce a new string that is also part of the language. The pumping lemma is useful for proving that a specific language is not a regular language, by showing that the language does not have the property.

Specifically, the pumping lemma says that for any regular language ${\displaystyle L}$, there exists a constant ${\displaystyle p}$ such that any string ${\displaystyle w}$ in ${\displaystyle L}$ with length at least ${\displaystyle p}$ can be split into three substrings ${\displaystyle x}$, ${\displaystyle y}$ and ${\displaystyle z}$ (${\displaystyle w=xyz}$, with ${\displaystyle y}$ being non-empty), such that the strings ${\displaystyle xz,xyz,xyyz,xyyyz,...}$ are also in ${\displaystyle L}$. The process of repeating ${\displaystyle y}$ zero or more times is known as "pumping". Moreover, the pumping lemma guarantees that the length of ${\displaystyle xy}$ will be at most ${\displaystyle p}$, thus giving a "small" substring ${\displaystyle xy}$ that has the desired property.

Languages with a finite number of strings vacuously satisfy the pumping lemma by having ${\displaystyle p}$ equal to the maximum string length in ${\displaystyle L}$ plus one. By doing so, no strings at all in ${\displaystyle L}$ have length at least ${\displaystyle p}$.

The pumping lemma was first proven by Michael Rabin and Dana Scott in 1959, and rediscovered shortly after by Yehoshua Bar-Hillel, Micha A. Perles, and Eli Shamir in 1961, as a simplification of their pumping lemma for context-free languages.