1. (10 points) Consider the Turing Machine where is defined as: | ((q, s)) q4,1, llll (q, s) -((q, s)) (91,a)(1,a, R)(93,a)(94,a, L)(a5, a)(1,X, R) (91,b)(2, X, R(93,b)(lrej,-, R) (95,b)(grej,-, R) (g1, X) (q1,X, R)(93, X)(3, X, L)(95, X) (grej,-, R) and 6( (gacc, s)) = (qacc-L) and ((grej, s)) = (grej-L) for each s e(a, b, X,-} a) Draw the state diagram of this Turing machine. For clarity, in your diagram you may leave out all outgoing transitions from qacc and qrej and all incoming transitions to qrej (Hint: q1, q2, q3, q4,95s form a pentagon so draw that first.) b) Trace through the computation of this machine on input aabb by listing each configuration of the machine in turn. c) Will this machine always halt? Why or why not