Give as much detail as possible when answering these questions

(a) Let L = {x E {0, )' x ends with 1). First describe in English, and then give a full description of a deterministic Turing machine M = Q, .q-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, q1:ga 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 1*Owi... Wn, your Turing machine should end in configuration qawi wk#wk+1 wn, for example on input 1 100 10 101 it should end in gaol#0101. f the input is not of the form 1k0wi wn for k > 0, or 1w k, your TM should reject (end in rejecting state, any tape content/head position). Hint: add new symbols to