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

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.

Answer 3

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 4

There are variants of the pumping lemma. I will use yours.

Note that you have really 3 length conditions. The missing one is about the minimum total length of the word. I treat it with the second condition.

In a (big) nutshell :

I call subtree any subpart of the parse tree that has at most one non-terminal at the fringe. The pumping lemma uses recursive subtrees where the non terminal in the fringe is the same as the root of the subtree. The whole parse tree is a subtree.

Subtrees as defined here (and recursive subtrees) are the heart of the matter. Their existence is directly related to the context-freeness.

1st condition: it states simply that if there is an unproductive (fringe with no termina symbol) recursive subtree in the parse tree, it can be short-circuited, so that we are always sure the fringe contains a terminal symbol.

A finiteness issue: It will be used twice. If you have a subtree that contains no recursive subtree, then no path in the subtree has twice the same label (subtree root excepted). The subtree is finitely branching with a limited depth (no more than the number of non-terminals).Hence you have a finite set of such subtrees generating only a finite set of strings at their fringe. Being finite in number, there is an upperbound for the length of the fringes. A contrario, if a fringe exceeds the bound, it is a sure indication it contains a recursive subtree.

"missing condition": The "missing condition" that $\mid s\mid \geq p$ ensure that the string is long enough so that there is at least one recursive subtree in the parse tree for pumping.

2nd condition: you can always get for pumping a recursive subtree that neither dominate nor contains another recursive subtree in the parse tree. If it does, just take the other recursive subtree. Since the parse tree is finite, this terminates. You end up with subtrees (for $vy$ and for $x$) that do not contain recursive subtrees, and the finiteness analysis above garantees the existence of an upperbound.

In the regular grammar case you just have subtrees that do not branch very much. It is really identical to the CF case with some strings replaced by $\epsilon$.

In the CF case, it is often convenient for the proof of the lemma, or its variations, to assume that the grammar is CNF (depending also on the lemma variant)

Much of the formal proof is mathematical presentation, not understanding.

This was an interesting exercise.