But m 2 − k > (m − 1) 2 , so that w 0 cannot be in L. Therefore, the language is not
regular.
In some cases, closure properties can be used to relate a given problem to
one we have already classified. This may be simpler than a direct application of
the pumping lemma.
Example 4.12
Show that the language
is not regular.
It is not difficult to apply the pumping lemma directly, but it is even easier to
use closure under homomorphism. Take
then
But we know this language is not regular; therefore, L cannot be regular either.
Example 4.13
Show that the language
is not regular.
Here we need a bit of ingenuity to apply the pumping lemma directly.
Choosing a string with n = l + 1 or n = l + 2 will not do, since our opponent can
always choose a decomposition that will make it impossible to pump the string
out of the language (that is, pump it so that it has an equal number of a’sand b’s).
We must be more inventive. Let us take n = m! and l = (m +1)!. If the opponent