8
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.