pumping lemma length restrictions clarification

Question

I know that this kind of question has been asked before, but I still see different kind of answers getting multiple upvotes, but I am not sure if they are all correct. That’s why I wanted to ask it again. I will put some answers that I have read and their difference in this question.

So my question: For a language $L$ and a string $w\in L$, the pumping lemma is defined as follows: If $|w| \geq m$, then $w$ can be written as $xyz$, satisfying the following conditions:

1. $|y|\geq 1$
2. $|xy|\leq m$
3. $ \forall i\geq 0: xy^iz\in L$

For the second condition, I think that all the answers give the same intuition, namely: The string $x$ is the part that stretches from the beginning of the input to the first occurrence of the double state, and the string $y$ stretches until the second occurrence (so y also causes the second occurence of a state). By considering the first loop, we can guarantee that $|xy| \leq m$. Since, in the “worst case”, after reading $m$ characters, we have seen $m+1$ states. So if I have a DFA M with 100 states, the loop can be in the first 3 states, but I can guarantee that if a word with length 100 or more is in L(M) then it will cause a loop since 101 or more states will be seen. If I’m not mistaken, this part is completely correct?

For the first condition, I have read multiple answers:

1. It is clearly necessary if you want to say something interesting, since otherwise you would pump an empty string.
2. Because you have a DFA, every transition must contain a symbol, and you can’t have any lambda-transitions, that’s why.

Could someone clearify which one here is the correct explanation?

Answer 1

First, for the sake of preciseness, note that the Lemma says that for every regular language $L$, there exists a constant $m\ge 1$, such that for every word $w\in L$... [what you wrote]. That is, the statement of the lemma is not "after" you have a language and a word.

As for your questions, basically everything you wrote is correct. To be slightly more specific:

The second condition indeed follows from the fact that we can bound the length of the run before a loop occurs. This follows from the pigeonhole principle. Interestingly, by the way, this condition can be changed to require that we can find a loop from whichever index we start from (as long as there are enough letters remaining). But this is beside the point.

For the first condition: indeed, if we had started with an NFA with $\lambda$ transitions (a.k.a. $\epsilon$ transitions in some textbooks), then we could not immediately assume $|y|\ge 1$ using the same proof. However, we could modify the proof by only looking at states visited after actual letters are read from the word, in an accepting run.

When you ask "which one is correct?" -- we need to start with a DFA (or a $\lambda$-free NFA) in order to obtain that $|y|\ge 1$, and we want $|y|\ge 1$ otherwise the lemma is useless. So both, kind of.