Consider the (non-regular) language of all bit strings that contain a 'power of two' number of...

 

Transcribed Image Text:

Consider the (non-regular) language of all bit strings that contain a 'power of two' number of Os, i.e., L= {0,00,0000, 00000000, 000000000000000,...} = {02 | k 0}. A Turing machine that decides L is M = "On input string w: 1. Sweep left-to-right across the tape, crossing off every other 0. 2. If the tape has one 0 left, accept 3. If the tape has more than one 0, and the number of 0's is odd, reject. 4. Return the head to the left end of the tape and goto 1. Essentially every pass cuts the number of 0's by two. At the end we should only have 1 zero remain. If this occurs, then the original number of zeros was a power of 2!. a. Describe how a Turing machine, M5, would accept the string 000000000 (223=8-0s). u|u|0|0|0|0|0|0|0|0|u|u b. Describe how a Turing machine, M5, would reject the string 000000000000 (12 0s). u|u|0|0|0|0|0|0|0|0|0|0|0|0|u|u| c. For an input of length n what is the complexity of this machine? d. Construct a state diagram for Turing machine Ms (It may be helpful to construct a 'reject' state) Consider the (non-regular) language of all bit strings that contain a 'power of two' number of Os, i.e., L= {0,00,0000, 00000000, 000000000000000,...} = {02 | k 0}. A Turing machine that decides L is M = "On input string w: 1. Sweep left-to-right across the tape, crossing off every other 0. 2. If the tape has one 0 left, accept 3. If the tape has more than one 0, and the number of 0's is odd, reject. 4. Return the head to the left end of the tape and goto 1. Essentially every pass cuts the number of 0's by two. At the end we should only have 1 zero remain. If this occurs, then the original number of zeros was a power of 2!. a. Describe how a Turing machine, M5, would accept the string 000000000 (223=8-0s). u|u|0|0|0|0|0|0|0|0|u|u b. Describe how a Turing machine, M5, would reject the string 000000000000 (12 0s). u|u|0|0|0|0|0|0|0|0|0|0|0|0|u|u| c. For an input of length n what is the complexity of this machine? d. Construct a state diagram for Turing machine Ms (It may be helpful to construct a 'reject' state)