The questions refer to exercises in Sipser.
Page 84, questions 1.6 (a), (b), (j).
Consider the following problem, called PowerOf2.
Input: A string of a's and b's.
Question: Does the input string have the form
an where n is a power of 2?
For example, the correct answer is yes on inputs a, aa, aaaa, aaaaaaaa, but the correct answer is no oin inputs aaa, abaa, bb and aaaaaa.
Show that there is no finite state machine that solves PowerOf2.
Hint.. Consider an arbitrary finite state machine M. Try running M on strings a, aa, aaaa, aaaaaaaa, ... (strings of a's whose length is a power of 2). Record the state on which M ends on each. Argue that there must be two of those strings ai and aj, with i < j, on which M ends in the same state. (Note that i and j will be powers of 2.) Show that M gets the wrong answer on either a2i or on ai+j by arguing that 2i is a power of 2 but i+j is not.
Your proof from the preceding exercise is constructive. Look at machine M2 in Exercise 1.1 on page 83. Carry out the argument of your proof to find an input on which M2 gives the incorrect answer to the PowerOf2 problem. Hence, M2 does not solve PowerOf2. Be sure to follow the argument in your proof to find the input. Do not just find one in an ad-hoc manner.