- Problem 5 20 Points Turing Machines Consider The Single Tape Deterministic Turing Machine With Input Alphabet E2 1 (66.59 KiB) Viewed 38 times
- Problem 5 20 Points Turing Machines Consider The Single Tape Deterministic Turing Machine With Input Alphabet E2 2 (41.53 KiB) Viewed 38 times
Problem 5 : [20 Points] [Turing Machines) Consider the single tape deterministic Turing machine with input alphabet E2 = {#,a} and tape alphabet T2 = {0, 1, a, #, U} whose transition diagram is given in Figure 5 below. As always, we assume that accepting state qe has no outgoing transitions and any transitions from symbols not shown in the states (other than qr) goes to the reject state grej, which is not shown in the picture. a +1,L # + #.L 42 94 # + #.R a + a,R a + a,R F # + #.R # + #.L # + #.R 90 91 93 a + 0,L Figure 1: Turing machine for Problem 5. 1. Give the sequence of configurations of the Turing machine when it is run on the input #a# [3 points) 2. Give the sequence of configurations of the Turing machine when it is run on the input #aa# [4 points)
3. Is there an input on which the Turing machine does not halt? If yes, give the string on which the Turing machine does not halt, if no, explain why. [3 points) 4. If the input is #a”#, what will the machine have on its tape when it halts? [5 points) 5. Write a regular expression defining the collection of all strings that could appear on the tape after the Turing machine halts. [3 points] 6. Given a string of length n, what is the maximum number of steps the Turing machine take to accept the string. [2 points)