Sipser Exercise 2.33


Theorem: The language is not context-free.


Proof: Suppose were context-free, and let be the pumping length. Let be a number strictly greater than , and let . Note and . Let with and . Consider cases.

Suppose and consist entirely of ’s. That is, and for some with . Notice that . Now, we use the strict requirements on to note that:

with strict inequalities, so cannot possibly divide the middle quantity. Therefore, the number of ’s does not divide the number of ’s and .

Suppose and consist entirely of ’s. Then will only have a strictly increasing number of ’s as increases. So can certainly be picked such that , then the the number of ’s does not divide the number of ’s, and .

In the case that or contains mixed characters, that is, some ’s and some ’s, then is not of the form , and not in .

Finally, we consider the case where consists only of ’s and consists only of ’s. So and for some , , and . Let and . An -pumped string is in if and only if is an integer. We have, for any positive :

Note that , is strictly decreasing, and converges to as . Since there are clearly only a finite number of integers (if any) between and , there must be some such that is not an integer. So, for that choice of , .

This contradicts the pumping lemma, so cannot be context-free.