patternMinor
What's the reason for the second condition of the pumping lemma(s)?
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:
Context-free version:
If $|s| \geq p$, then $s$ can be written as $uvxyz$, satisfying the following conditions:
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?
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.
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.