Turing Machine Question 1.

(a) Let L = {x E {0, 1)' | x ends with 1). First describe in English, and then give a full description of a deterministic Turing machine M-Q. .g-ga, gr, deciding L. Your English descrip- tion should explain what your Turing machine is doing, and your full description should include a table for . Use only states go,J1,Ja and qr, and take -{0, 1, J. (b) List a sequence of configurations describing the computation of your Turing machine from the previous subquestion on the string 010. Now do the same for the string 11. Finally, what sequence of configurations would your Turing machine go through on blank input? (c) Describe in English a Turing machine that, on an input of the form 1k0u, where w E {0,1}*, inserts a special symbol # after k characters of u, and then erases prefix 1k0. That is, when started on an input of the form 1k0w1-..uh, your Turing machine should end in configuration gaw! wk#wk+1 wn, for example on input 110010101 it should end in q,01#0101. If the input is not of the form 1kOw... wn for k , or wl