7
$\begingroup$

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?

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.