ASSINGMENT 2 ATOC

Assignment #2 Due 10:00am February 3, 2017 (Friday)

1. This problem refers to the example DTM posted right under the item “Turing Machine” on the class Web site. For each of the 3 input strings abc , aabc , and abcc , show the computation that accepts or rejects the string.

2. Show a DTM that accepts the following language with ∑={#,a,b} as the input alphabet. The symbol # is used to mark the left end of the tape.

{# ai bj | i,j > 0 and i is a factor of j},

You should first accurately describe in words the algorithm that your DTM carries out and then show a state diagram for the DTM.

3. Show a DTM that, when given #b as input, where b is a bit

string representing an unsigned binary number >= 1 with no leading 0’s, halts with #b-1 on the tape as output, where b-1 is a bit string representing the value of b-1 as an unsigned binary number with no more than one leading 0. You should first accurately describe in words the algorithm that your DTM carries out and then show a state diagram for the DTM.

4. Consider the following NTM. For each of the two strings aab

and baa as input to the NTM, show a computation tree and circle each accept configuration and underline each reject configuration.