2. (10 points) Consider the function from {0,1} to {a, b} given by H(0) = b, h(1) = a. We can extend h to operate on strings by defining h(w) = h(wi)h(w2) ... h(wn) where w = wi ... Wn and each w; E {0,1}. For example, h(010) = bab. Extending h to languages over {0,1}, we define h(L) = {h(w) | w E L} for any LC {0,1}*. Devise a general construction that, given a Turing machine M over the alphabet {0,1}, builds a Turing machine M' over the alphabet {a, b} that recognizes h(L(M)). A full proof would have three stages: setup, construction, and proof of correctness. In this exercise you will focus on the setup and construction, and then apply your construction to an example. (a) Setup Consider an arbitrary Turing machine M = (Q, {0, 1}, I, 8, 90, qacc, drej), where {0, 1, -} CT and {qo, qacc, Irej} CQ and qacc # grej. Let L = L(M). Construction Build a new Turing machine whose language is h(L). Specify this Turing machine formally, specifying each component of the 7-tuple formal definition. You must supply this construction. (b) Application Consider the language, L, recognized by this Turing machine: D;O,R 1;, R 0:0, R D;, R 1; , R 0:0,R q_rej Aacd D:D, R 1:0,R Describe L mathematically (e.g. in set builder notation), and briefly justify your description. Then, apply your construction from part (a) to this Turing machine and confirm that the language recognized by the resulting Turing machine is h(L) by describing its computations. Include the state diagram of the resulting machine as exported from JFLAP and your justifications in your homework submission