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

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?

-
 I'm commenting since I might not get your question, but it seems to me obvious that if you have a word of length at least $p \geq 1$, you can partition the word into three parts, $xyz$ such that $|y| \geq 1$ and $|xy| \leq p$. Simply let $x$ be empty, $y$ be the first character and $z$ the rest. Did I completely misunderstand your question? – Pål GD Jan 30 at 19:51 @PålGD, I don't find it obvious in the context of the other conditions of the lemma (non-zero length of the pumpable substring, and arbitrary pumpability). I agree, it's obvious that a string of length at least $x$ can be partitioned into to substrings such that the first has length $\leq x$, but the obviousness (to me) doesn't carry over when you retain the other conditions. Maybe I should clarify the original post? – BlueBomber Jan 30 at 19:55 No, seen in light of the third condition, one should be a bit more careful. As you've noticed, the first two conditions say nothing useful. As you also notice, forcing the $y$ to be nonempty (as is indeed what the first condition says), makes us actually in a position to "pump". – Pål GD Jan 30 at 20:04 Is the context-free PL necessary for your question? It does not make a lot of sense to consider some of these conditions in isolation. – Raphael♦ Jan 30 at 20:27 @BlueBomber, in both case without condition (1) the pumping is pointless (can select the empty substring always). For regular languages, (2) is just that in $n$ symbols the DFA for the language has been in $n + 1$ states, and by the pigeonhole principle if the DFA has $n$ states, one must have repeated (and you can go through the cycle $k$ times, pumping the string). – vonbrand Jan 31 at 20:45

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.

-
condition 2 is "arbitrary" in other ways. E.g., an equivalent lemma is given if we replace (2) by $|yz|<p$. There is even a stronger version of the pumping lemma in which the $y$ part can be anywhere (not necessarily in the beginning or end). The common variant ($|xy|<p$, that is, $y$ is next to the beginning) is due convenience. – Ran G. Jan 31 at 5:10
@RanG. How is a version where the position of $y$ is arbitrary stronger? I think I explained how that would be weaker. Or does that version state other things? – Raphael Jan 31 at 9:37
It is stronger since it gives you more flexibility: maybe the part you wish to pump is not in the beginning of the word. Indeed, it still has an equivalent of $|xy|<p$ for not being "weaker" as you say, but without the need to locate it exactly in the beginning. Think of Ogden's lemma as the most generalized form.. – Ran G. Jan 31 at 17:37
@Raphael, for example the version given above isn't enough to prove that $\{a b^n c^n \colon n \ge 0\} \cup a a^+ b^* c^*$ isn't regular (can pump the $a$), but with $y$ lying anywhere it is easy. – vonbrand Jan 31 at 20:50
@vonbrand: I see now what Ran means, thanks. – Raphael Jan 31 at 23:31

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.

-

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.

-