I am reading "Introduction to the Theory of Computation 3rd Edition" by Michael Sipser.
Pumping lemma is the following proposition:
THEOREM 1.70
Pumping lemma If $A$ is a regular language, then there is a number $p$ (the pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be devided into three pieces, $s=xyz$, satisfying the following conditions:
- for each $i\geq 0$, $xy^iz\in A,$
- $|y|>0$, and
- $|xy|\leq p.$
In this book, when the author prove some language is not regular, he always uses Pumping lemma.
For example, the author uses Pumping lemma to prove the following $C$ is not regular.
EXAMPLE 1.74
Let $C=\{w\mid w\text{ has an equal number of }0\text{s and }1\text{s}\}.$ We use the pumping lemma to prove that $C$ is not regular. $\cdots$
The author's proof of EXAMPLE 1.74:
Assume to the contrary that $C$ is regular. Let $p$ be the pumping length given by the pumping lemma. As in Example 1.73, let $s$ be the string $0^p1^p$. With $s$ being a member of $C$ and having length more than $p$, the pumping lemma guarantees that $s$ can be split into three pieces, $s=xyz$, where for any $i\geq 0$ the string $xy^iz$ is in $C$. We would like to show that this outcome is impossible. But wait, it is possible! If we let $x$ and $z$ be the empty string and $y$ be the string $0^p1^p$, then $xy^iz$ always has an equal number of $0$s and $1$s and hence is in $C$. So it seems that $s$ can be pumped.
Here condition 3 in the pumping lemma is useful. It stipulates that when pumping $s$, it must be divided so that $|xy|\leq p$. That restriction on the way that $s$ may be divided makes it easier to show that the string $s=0^p1^p$ we selected cannot be pumped. If $|xy|\leq p$, then $y$ must consist only of $0$s, so $xyyz\notin C.$ Therefore, $s$ cannot be pumped. That gives us the desired contradiction.
Selecting the string $s$ in this example required more care than in Example 1.73. If we had chosen $s=(01)^p$ instead, we would have run into trouble because we need a string that cannot be pumped and that string can be pumped, even taking condition 3 into account. Can you see how to pump it? One way to do so sets $x=\epsilon,y=01,$ and $z=(01)^{p-1}.$ Then $xy^iz\in C$ for every value of $i$. If you fail on your attempt to find a string that cannot be pumped, don't despair. Try another one!
I think we can easily prove that $C$ is not regular even if we don't know what the pumping lemma is.
I think it is important to notice we can use the idea of pigeonhole principle.
His approach seems too prescriptive.
Is the pumping lemma really useful?
Is there a problem which is very difficult if we don't know the statement of the pumping lemma?
I suspect that pumping lemma is a proposition not worth naming.
My idea is the following picture (the same idea as pumping lemma):
Let $M$ be a DFA which recognizes $C$.
Give a sufficiently long string $00000000$ to $M$.
$M$ must contain a submachine like the above picture because the set of the states of $M$ is finite and $00000000$ is sufficiently long and $0000000011111111\in C$.
Then, $0000000000000011111111\in C$ must holds.
But this string has fourteen $0$s and eight $1$s.