ASSINGMENT 2 ATOC, 2

1. This problem refers to this example DTM below

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 as input to the NTM, show a computation tree and circle each accept configuration and underline each reject configuration.