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: Why do we have condition 2 in the lemma (for either case)? I understand that condition 1 essentially says that the "pumpable" (meaning nullable or arbitrarily repeatable) substring has to have some nonzero length, and condition 3 says that the pumpable substring can be repeated arbitrarily many times without deriving an invalid string (with respect to $L$). I'm not sure what the second condition means or why it is important. Is there a simple but meaningful example to illustrate its importance?

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

When proving that a language isn't regular/context free it is quite useful to be able to limit the area containing the pumped string. The classical example is proving $\{a^n b^n \colon a \ge 0\}$ non-regular: If you take $\sigma = a^p b^p$, where $p$ is the lemma's constant, then without condition (2) you have to consider the three pieces into which $\sigma$ can be cut to be formed of $a$, of $b$, or both. Can be done, but is a lot more complicated. In the language given in the question (same number of $a$ and $b$), you can select $\sigma = a^p b^p$, and unless you can force the piece pumped to be just $a$ or $b$ you won't go anywhere, and there condition (2) is vital.

share|improve this answer
    
This case is special. Other cases may be different. In fact, there is a generalization called Ogden's lemma, and situations in which the pumping lemma is not enough but Ogden's lemma is. –  Yuval Filmus Jan 29 '13 at 14:23
    
What do you mean by "The proof tells you how it is proved."? –  BlueBomber Jan 29 '13 at 19:36
1  
@BlueBomber, I understood the question as asking not for a proof, but for the why this condition is important when using the lemma. Badly worded, conceded. Any suggestion for clarifying this? –  vonbrand Jan 29 '13 at 22:44
    
Ah, ok, no problem! Maybe just remove that first sentence altogether. The rest of your reply is very helpful in demonstrating how the second condition is helpful when using the pumping lemma to prove $s \notin L$. Now I'm just trying to understand why that is a necessary consequence of regularity (context-freeness). –  BlueBomber Jan 30 '13 at 18:34
add comment

Consider the language of words over $\{a,b\}$ consisting of words with an equal number of $a$s and $b$s. This language is context-free but not regular. To show that it is not regular using the pumping lemma, you start with the word $a^pb^p$ and pump $y$, which must consist solely of $a$s. Without condition (2), this wouldn't work: you can pump $ab$ (in the middle) and remain inside the language. Moreover, for any word that you start with, you will be able to find one of the substrings $ab,ba$ which you could then pump.

Similar considerations show that condition (2) is needed for proving that the language over $\{a,b,c\}$ consisting of those words having an equal number of $a$s, $b$s and $c$s is not context-free.

share|improve this answer
    
If you pump the $ab$ in the middle, you get $a...aababab...b$, which isn't in the language at all. –  vonbrand Jan 29 '13 at 12:27
1  
Are you sure? The language isn't $\{a^n b^n : n \geq 0\}$. For example, it contains all of $ab,ba,aabb,abab,baba,bbaa$. –  Yuval Filmus Jan 29 '13 at 14:21
1  
you are right. Too little coffee maybe... –  vonbrand Jan 29 '13 at 14:26
    
Thank you for the reply. It does illustrate the importance (really the utility) of the second condition when using the lemma. –  BlueBomber Jan 30 '13 at 18:42
add comment

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.