patternModerate
What is the Pumping Lemma a lemma to?
Viewed 0 times
thelemmawhatpumping
Problem
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?
What is it a lemma to?
Solution
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).
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).
Context
StackExchange Computer Science Q#70009, answer score: 10
Revisions (0)
No revisions yet.