Where do the length restrictions of the pumping lemma come from?

Question

For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows:

Regular version: If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following conditions:

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

Context-free version: If $|s| \geq p$, then $s$ can be written as $uvxyz$, satisfying the following conditions:

1. $|vy|\geq 1$
2. $|vxy|\leq p$
3. $ \forall i\geq 0: uv^ixy^iz\in L$

My question is this: Can someone give a concise and clear explanation of how regularity (context-freeness) imply the first and second conditions above? The pumping length is determined by (finite) properties (finite number of states or finite properties of production rules, respectively), the third properties guarantee that a state (production rule) can be skipped or repeated arbitrarily many times, but where do the first and second conditions originate? How are they justified?

Answer 1

The first condition, i.e. $|y| \geq 1$, is clearly necessary if you want to say something interesting: for $y = \varepsilon$, $xy^iz \in L$ trivially and always holds.

The second condition, i.e. $|xy| \leq p$, is "arbitrary": the lemma still says something interesting if you drop it, and it is still true because the statement becomes weaker.

But remember what we want to use the pumping lemmas for: we want to find a (sufficiently long) word such that all valid decompositions into $x,y,z$ fail to pump. Therefore, it is useful to allow as few such decompositions as possible. Lucky as we are, the proof of the pumping lemma readily yields a strong restriction, namely that there has to be a pumpable decomposition with $|xy| \leq p$ with constant $p$.

Now we have to refute only finitely many prefixes $xy$ (with possibly infinitely many different continuations, of course). If you look at example applications, you will see that they make heavy use of this restriction.

Answer 2

As you move through the states of an automaton, you'll eventually hit a cycle. The cycle is $y$. There is no point in pumping an empty word, hence condition 1. $xy$ is the number of symbols you had to read to find the first cycle. This can't possibly be more than the number of states, hence condition 2. Almost by definition, a cycle can be repeated any number of times, hence condition 3.

The context free variant is very similar. The first condition is we're only looking for useful cycles. The second condition says that a cycle can be found because you'll run out of non-terminals. The third condition says that once you have a cycle you can pump it. Note that to see a cycle in the context free case, you should draw a parse tree.

Answer 3

I'll only offer some pointers on the pumping lemma for regular languages; the reasoning is similar enough for the other. Think of $x$ as the part of $s$ generated by everything before starting the first loop for the first time; $y$ as everything generated while in that certain loop for the first loop; and $z$ as everything generated after looping the first time.

1. Since $|s| \geq p$, and $p$ is the number of states in the minimal finite automaton (e.g.) accepting the language, then the automaton must have looped (since at most $p-1$ transitions would have been possible, otherwise). Therefore, $y$ is non-empty; we are stating the fact that since we have a string of a certain length, the automaton accepting it must have looped at some point, so $|y|>1$ is justified.

2. Since $y$ is the first time you go through the first loop, and $x$ is everything before that, you have not visited any state in the automaton more than once. Since there are $|p|$ states in the automaton, and you haven't visited all of them, you have $|xy| < p$.

These aren't so much hypotheses requiring support; they're statements of fact based on how the pumping lemma was dreamed up in terms of finite automata.