HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theconditionwhatreasonpumpingsecondforlemma

Problem

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:

  • $|y|\geq 1$



  • $|xy|\leq p$



  • $ \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:

  • $|vy|\geq 1$



  • $|vxy|\leq p$



  • $ \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?

Solution

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.

Context

StackExchange Computer Science Q#9269, answer score: 7

Revisions (0)

No revisions yet.