Closed under Prefix 
1. Suppose L is the language of some DTM M=<Q,{0,1},T,d,q0,qa,qr>.
(i 6 points) Construct a DTM or an NDTM to accept Pre(L) = { x : there exists some y such that xy is L}. List down the DTM/NDTM completely in terms of its tuples and explain the idea behind the construction.
For your convenience you can use stationary moves in your TM for Pre(L) (we learned in class that these are equivalent to standard TMs).
(ii, 3 point) Take the DTM for the language A={0^k : k is a power of 2} given in your textbook. Draw the DTM/NDTM for Pre(A) using your idea in (i). You can take a picture of a hand-drawn TM and paste it in your solution. Then, show that your TM accepts 0^5 by listing the sequence of configurations.
(iii, 1 point) Conclude what can we say about the set of decidable language being closed under Pre() and the set of recognizable languages being closed under Pre(). Explain if they are true or false, and why or why not, in 2-3 sentences.