arbitrarily long. This gives additional freedom to the adversary, making
arguments involving Theorem 8.1 a little more complicated.
Example 8.1
Show that the language
is not context-free.
Once the adversary has chosen m, we pick the string a m b m c m , which is in L.
The adversary now has several choices. If he chooses vxy to contain only a's,
then the pumped string will obviously not be in L. If he chooses a decomposition
so that v and y are composed of an equal number of a's and b's, then the pumped
string a m b m c m with k ≠ m can be generated, and again we have generated a string
not in L. In fact, the only way the adversary could stop us from winning is to
pick vxy so that vy has the same number of a’s, b’s, and c’s. But this is not
possible because of restriction (8.2). Therefore, L is not context-free.
If we try the same argument on the language L = {a n b n } we fail, as we must,
since the language is context-free. If we pick any string in L, such as w = a m b m
the adversary can pick v = a k and y = b k . Now, no matter what i we choose, the
resulting pumped string w i is in L. Remember, though, that this does not prove
that L is context-free; all we can say is that we have been unable to get any
conclusion from the pumping lemma. That L is context-free must come from
some other argument, such as the construction of a context-free grammar.
The argument also justifies a claim made in Example 7.11 and allows us to
close a gap in that example. The language
is not context-free. The string a m b m c m is in , but the pumped result is not.
Example 8.2
Consider the language
arguments involving Theorem 8.1 a little more complicated.
Example 8.1
Show that the language
is not context-free.
Once the adversary has chosen m, we pick the string a m b m c m , which is in L.
The adversary now has several choices. If he chooses vxy to contain only a's,
then the pumped string will obviously not be in L. If he chooses a decomposition
so that v and y are composed of an equal number of a's and b's, then the pumped
string a m b m c m with k ≠ m can be generated, and again we have generated a string
not in L. In fact, the only way the adversary could stop us from winning is to
pick vxy so that vy has the same number of a’s, b’s, and c’s. But this is not
possible because of restriction (8.2). Therefore, L is not context-free.
If we try the same argument on the language L = {a n b n } we fail, as we must,
since the language is context-free. If we pick any string in L, such as w = a m b m
the adversary can pick v = a k and y = b k . Now, no matter what i we choose, the
resulting pumped string w i is in L. Remember, though, that this does not prove
that L is context-free; all we can say is that we have been unable to get any
conclusion from the pumping lemma. That L is context-free must come from
some other argument, such as the construction of a context-free grammar.
The argument also justifies a claim made in Example 7.11 and allows us to
close a gap in that example. The language
is not context-free. The string a m b m c m is in , but the pumped result is not.
Example 8.2
Consider the language