ONLY ANSWER PART C!!

Programming Turing machines (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., ,q, qa, qr, ) 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 qo,Y1, qa and qr, and take= {0, 1, (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 1*Ow, where w e (0, 1)*, inserts a special symbol # after k characters of w and then erases prefix 1k0. That is, when started on an input of the form 1k0w1wn, your Turing machine should end in configuration qawi wk#wk+1 wn, for example on input 110010101 it should end in q,01#0101. If the input is not of the form 1*Owi...wn for k 0, or w