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:
- $|y|\geq 1$
- $|xy|\leq m$
- $ \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:
- It is clearly necessary if you want to say something interesting, since otherwise you would pump an empty string.
- 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?