This exercise concerns TM M2, whose description and state diagram appear in Example 3.7. In each of the pa sequence of configurations that M2 enters when started on the indicated input string. a. 0.
b. 00.
c. 000.
d. 000000.
EXAMPLE 3.7
Here we describe a Turing machine (TM) M2 that decides A={02nIn> 0}, the language consisting of all strings of Os whose length is a power of 2.
M2 = On input string w:
1. Sweep left to right across the tape, crossing off every other 0.
2. If in stage 1 the tape contained a single 0, accept.
3. If in stage 1 the tape contained more than a single 0 and the number of Os was odd, reject.
4. Return the head to the left-hand end of the tape.
5. Go to stage I.