DO q0 Let M be the Turing Machine displayed below: Y;Y, R 0:0,R Y;Y,L 0:0, L...

 

Transcribed Image Text:

DO q0 Let M be the Turing Machine displayed below: Y;Y, R 0:0,R Y;Y,L 0:0, L 0;X, R q1 1:Y,L q3 XX.F q2 Y;Y,R Y;Y,R S q4 0:0,R acc (With the usual conventions of missing transitions go to the reject state.) This machine decides the language {0k1k|k 1}. (The number of "steps" in a computation is the number of transitions that the Turing Machine passes before ending on the accept state or the reject state. In other words, the number of "steps" in a computation is equal to the number of configurations minus 1) (a) (6 points) Consider the statement: For all even positive integers n, the input string of length n for which M takes the most steps before halting is on/21n/2. Give an argument about why the above statement is true. (b) (8 points) Suppose that f(n) is the running time of M, i.e., fm (n) = the maximum number of steps M takes before halting over all inputs of size n. Assuming the statement from part (a), Compute: fM (2) fm (4) fm (6) fm (8) (You may use the jflap file that is attached.) (c) (6 points) What is the tightest Big-O class that f(n) belongs to? Justify your answer by talking about how the machine processes inputs. DO q0 Let M be the Turing Machine displayed below: Y;Y, R 0:0,R Y;Y,L 0:0, L 0;X, R q1 1:Y,L q3 XX.F q2 Y;Y,R Y;Y,R S q4 0:0,R acc (With the usual conventions of missing transitions go to the reject state.) This machine decides the language {0k1k|k 1}. (The number of "steps" in a computation is the number of transitions that the Turing Machine passes before ending on the accept state or the reject state. In other words, the number of "steps" in a computation is equal to the number of configurations minus 1) (a) (6 points) Consider the statement: For all even positive integers n, the input string of length n for which M takes the most steps before halting is on/21n/2. Give an argument about why the above statement is true. (b) (8 points) Suppose that f(n) is the running time of M, i.e., fm (n) = the maximum number of steps M takes before halting over all inputs of size n. Assuming the statement from part (a), Compute: fM (2) fm (4) fm (6) fm (8) (You may use the jflap file that is attached.) (c) (6 points) What is the tightest Big-O class that f(n) belongs to? Justify your answer by talking about how the machine processes inputs.