# What is the Pumping Lemma a lemma to?

This is something I couldn't find - but I always found it interesting that the pumping lemma is just a lemma (especially since it has the same name for regular languages, context free languages, etc...)

What is it a lemma to?

## 1 Answer

In the foundational paper of Rabin and Scott, Finite automata and their decision problems, the pumping lemma appears as a lemma (Lemma 8) to the following result (Theorem 9):

The language accepted by an $n$-state DFA is infinite if and only if it accepts some word whose length lies between $n$ and $2n$.

The pumping lemma implies the $\Longrightarrow$ direction.

It also "gives another proof" that the language $\{0^n 1 0^n : n \geq 0\}$ isn't regular (the original proof in the paper uses Myhill-Nerode theory).