# How can both |y| = 0 and y⁰ = ε hold in the Pumping lemma?

There is something in the pumping lemma that I do not quite understand, namely if $s$ is at least of length $p$, then we could split it to $xyz$ such that the following conditions are met:

1. For each $i \geq 0$, $x(y^i)z \in A$
2. $|y| > 0$
3. $|xy| \leq p$

But if $i = 0$ then $|y|$ cannot be strictly greater than $0$. Isn't condition 1 contradicting condition 2? Isn't $y^0 = \varepsilon$?

-
Note that the Pumping lemma is not a definition -- that's why it's called a lemma! –  Raphael Feb 4 '14 at 10:00

Sure, $y^0$ is $\epsilon$, but that does not make $|y|=0$.
Consider $y=\mathit{foo}$. Here, $|y|=|\mathit{foo}|=3$, yet $(\mathit{foo})^0=\epsilon$.
No contradiction – $y$ is unchanged.

-

The pumping lemma is effectively finding a loop in your DFA for you. You can think of the string $xy^iz$ as saying:

1. follow $x$ from the initial vertex,
2. now you are at the start of the loop, follow $y$ to go around the loop and return to the same spot.
3. now follow $z$ to an accept state.

Now, the condition [2] in your question says that the loop in point 2. of my explanation has to actually exist (i.e. have non-zero length). Condition [1] in your question says that since this is a loop you don't necessarily have to follow it (since it returns to the same spot) and can just follow $x$ to the start of the loop, follow the loop zero times (i.e. $y^0 = \epsilon$) and continue to follow $z$ to the accept state.

-

The above answers sums it up pretty good, but I wanted to add something from my understanding of this topic.

For the pumping lemma to apply you must have a substring $y$ within your string $s$ that can be pumped, but that requires that $y$ is effectively some string other than the empty string, or else you couldn't be able to pump it in the first place.

Recall that $y$ represents a loop inside the finite deterministic automaton that accepts the language, so if for your initial string $s$ you have $|y| = 0$ then there is no loop at all, which is not the same as avoiding the loop and going straight to the accept state (when $i=0$).

Maybe the order the conditions are given is misleading, because you first gotta check for conditions 2 and 3 in order to pump $y$, i.e. check condition 1.

-