In class and in the textbook (pages 166-167, page 173), we saw a Turing machine deciding the set B = {w#w | w {0, 1}}. In this question, you will modify this machine so that it decides the set

A = {w#wR | w {0,1}} a) Give an implementation-level description of your machine. Follow the style and conventions demon-

strated on page 167.

b) Prove that the machine you gave in part (a) decides A by showing that for any string w {0, 1, #} , if w A, then your machine accepts on input w, and

if w / A, then your machine rejects on input w.

c) Draw the state diagram formalizing the machine you described in part (a). You may use the abbrevia- tions used on page 173 and on this weeks Individual Homework: omit all outgoing transitions for the accept and reject states, and omit all incoming transitions to the reject state.

1. (10 points) In class and in the textbook (pages 166-167, page 173), we saw a Turing machine deciding the set B = {w#w ue {0, 1)'). In this question, you will modify this machine so that it decides the set instead. a) Give an implementation-level description of your machine. Follow the style and conventions demon- strated on page 167. b) Prove that the machine you gave in part (a) decides A by showing that for any string w {0,1,#)', if w if w A, then your machine accepts on input w, and A, then your machine rejects on input w. c) Draw the state diagram formalizing the machine you described in part (a). You may use the abbrevia- tions used on page 173 and on this week's Individual Homework: omit all outgoing transitions for the accept and reject states, and omit all incoming transitions to the reject state