# What's the reason for the second condition of the pumping lemma(s)?

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?

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.

• 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. Jan 29, 2013 at 14:23
• What do you mean by "The proof tells you how it is proved."? Jan 29, 2013 at 19:36
• @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? Jan 29, 2013 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). Jan 30, 2013 at 18:34
• @BlueBomber, there is where the proofs come in... Feb 15, 2020 at 16:31

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.

• If you pump the $ab$ in the middle, you get $a...aababab...b$, which isn't in the language at all. Jan 29, 2013 at 12:27
• 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$. Jan 29, 2013 at 14:21
• you are right. Too little coffee maybe... Jan 29, 2013 at 14:26
• Thank you for the reply. It does illustrate the importance (really the utility) of the second condition when using the lemma. Jan 30, 2013 at 18:42