It should be noted here that the above does not imply that a was used
recursively only once. The * of ⇒
* could cover many uses of A, as well as other
recursive variables.
There has to be some “last” recursive step. Consider the longest strings
that can be derived for v, w and x without the use of recursion. Then there is a
number ‘m’ such that | vwx | < m.
Since the grammar does not contain any λ-productions or unit
productions, every derivation step either introduces a terminal or increases the
length of the sentential form. Since A vAx
⇒
*
, it follows that | | .
vx > 0
Finally, since uvAxy occurs in the derivation, and A vAx
⇒
*
and A w
⇒
*
are
both possible, it follows that uv wx y
i
i also belongs to L.
This completes the proof of all parts of Lemma.
3.3.4 Usage of Pumping Lemma
The Pumping Lemma can be used to show that certain languages are not
context free.
Let us show that the language
L a b c i
i i i
=
>
{
|
}
0
is not context-free.
Proof: Suppose L is a context-free language.
If string X L
∈ , where | |
X m
> , it follows that X = uvwxy, where |
|
vwx m
≤ .
Choose a value i that is greater than m. Then, wherever vwx occurs in the
string a b c
i i i , it cannot contain more than two distinct letters it can be all a’s,
all b’s, all c’s, or it can be a’s and b’s, or it can be b’s and c’s.
Therefore the string vx cannot contain more than two distinct letters; but
by the “Pumping Lemma” it cannot be empty, either, so it must contain at least
one letter.
Now we are ready to “pump”.
Since uvwxy is in L, uv wx y
2
2 must also be in L. Since v and x can’t both be
empty,
|
| |
|,
uv wx y
uvwxy
2
2
>
so we have added letters.
Both since vx does not contain all three distinct letters, we cannot have
added the same number of each letter.
Therefore, uv
2 wx
2 y cannot be in L.
Thus we have arrived at a “contradiction”.
Pushdown Automata
173