Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
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.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.