Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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 '13 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 '13 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 '13 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 '13 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 '13 at 20:45

4 Answers 4

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.

share|improve this answer
1  
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 '13 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 '13 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 '13 at 17:37
1  
@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 '13 at 20:50
    
@vonbrand: I see now what Ran means, thanks. –  Raphael Jan 31 '13 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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.