Although this language appears to be very similar to the context-free language of
Example 5.1, it is not context-free.
Take the string
There are many ways in which the adversary can now pick vxy, but for all of
them we have a winning countermove. For example, for the choice in Figure 8.2,
we can use i = 0 to get a string of the form
which is not in L. For other choices by the adversary, similar arguments can be
made. We conclude that L is not context-free.
Figure 8.2
Example 8.3
Show that the language
is not context-free.
Given the opponent's choice for m, we pick a = a m! Obviously, whatever the
decomposition is, it must be of the form v = a k , y = a l . Then w 0 = uxz has length
m! – (k + l). This string is in L only if
for some j. But this is impossible, since with k + l ≤ m,
Example 5.1, it is not context-free.
Take the string
There are many ways in which the adversary can now pick vxy, but for all of
them we have a winning countermove. For example, for the choice in Figure 8.2,
we can use i = 0 to get a string of the form
which is not in L. For other choices by the adversary, similar arguments can be
made. We conclude that L is not context-free.
Figure 8.2
Example 8.3
Show that the language
is not context-free.
Given the opponent's choice for m, we pick a = a m! Obviously, whatever the
decomposition is, it must be of the form v = a k , y = a l . Then w 0 = uxz has length
m! – (k + l). This string is in L only if
for some j. But this is impossible, since with k + l ≤ m,