Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456

Solution for Exercise 1.17(c) in Sipser's Book

Assume, towards a contradiction, that the language A₃ is regular. Then, by the pumping lemma, it has a pumping length p. Consider the string

s = a^{2^p}.

Since, 2^p is larger than p for each p>=0, the pumping lemma says that s can be written as xyz for some strings x, y, z with length(xy)<=p and length(y)>0. We claim that the string xyyz is not in the language A₃, contradicting the statement of the pumping lemma and therefore our assumption that A₃ were regular.

To see that xyyz is not in the language A₃, observe that the shortest string in A₃ that is longer than s is of length 2^p+1. The difference in length between s and this string is therefore 2^p. On the other hand, we have that

length(xyyz) - length(s) = p < 2^p.

It follows that the length of xyyz is not a power of 2, and therefore xyyz is not in the language A₃, as claimed.