Length of mid part of the string in Pumping Lemma

Question

This statement of the pumping lemma from Wikipedia.

Let $L$ be a regular language. Then there exists an integer $p \ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = x y z$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:

1. $\lvert y \rvert \ge 1$
2. $\lvert x y \rvert \le p$ and
3. for all $i \ge 0$, $x y^i z \in L$.
   $y$ is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in $L$).

What confuses me about the definition of pumping lemma are two requirements: $\lvert y \rvert \ge 1$ and $i \ge 0$, $x y^i z$. The way I read it, that we are required to have $y$ length be equal to one or greater, and at the same time, we can completely skip it, since $i \ge 0$, i.e. effectively $\lvert y \rvert = 0 $. Intuitively, it makes sense that we should be able to skip $y$ and still have string be in $L$.

Answer 1

Any finite state automaton that accepts an infinite number of words will necessarily have a loop in it. One such loop may go from state $q$ to state $q$ consuming word $y$ – that is, $y$ is the word based on the symbols on the transitions going from $q$ back to $q$.

The pumping lemma says, more or less, that you can get to such a state $q$ from the initial state by consuming the word $x$ and that you can get to the final state from state $q$ by consuming the word $z$. In the middle you can go through the loop as many times as you like. Thus making the complete word $xy^iz$, where $i$ is the number of times you chose to go through the loop.

Answer 2

"The way I read it, that we are required to have $y$ length be equal to one or great, and at the same time, we can completely skip it, since $i\geq 0$, i.e. effectively $|y|=0$."

If $y$ had length $0$, then it would be the empty word, and so it would not be useful that we can skip it (or pump it as many times as we like). The condition $|y|\geq 1$ is insuring that there is a nontrivial word that can be pumped.

Does that help?

Answer 3

The condition that $y$ has length at least one is to avoid a triviality. If you allow the length of $y$ to be zero then for any language you can divide each word in the language into $xyz$, such that $xy^iz$ is still in the language; choosing an empty $y$ means $xyz = xy^iz$ for any $i$.

Thus the ability for a language to be "pumped" with this alternate version of the pumping lemma tells us nothing about the language. The only language that couldn't be so "pumped" is the empty language, and even then that's because it simply contains no words.

Observing that $i = 0$ is one of the values of $i$ does not make $|y|$ "effectively" 0. At the point that you're considering all values of $i$ you're talking about some particular $y$; (the one that can be found for the language and word under consideration). Thus taking $i = 0$ produces a different string $w$ by removing $y$, which is completely different from dividing $w$ up into $xyz$ where $y$ is empty.

Answer 4

The lemma states that all strings longer than $p$ can be subdivided into $x y z$ with $\lvert x y \rvert \le p$ and $y \ne \epsilon$ so that for all $i \ge 0$ $x y^i z$ belongs to the language. This means that $0 < \lvert y \rvert \le p$, obviously. If you take a "pumped" string, i.e. $x y^i z$ for $i > 1$, the resulting string is longer than $p$ and thus can be pumped. Again, plain $y$ works just as before, giving $x y^{i + j} z$, for $i + j > 1$, and that you knew.

The lemma states there is some subdivision, it doesn't say there is just one. There may very well be several.