Problem 1 [30 points] Let A |M is a DFA which does not accept any string containing an odd number of ones). Show that A is decidable. In other words, you need to design a Turing machine of the following type. The Turing machine will accept a DFA as input. It will accept and halt if the DFA does not accept any string containing an odd number of ones; otherwise, it will reject and halt. No need to give too much details of a Turing machine; a very high pseudo-code level description is fine. For example, you may simply say "Turing machine X simulates the DFA Y step by step". Optional hint: You may use the following facts that you already know. It is easy to design a DFA B that accepts an odd number of ones. The intersection Mn B of two DFAs M and B is also a DFA that can be easily constructed We have seen in the class that it is possible to design a Turing machine that can decide if a given DFA accepts an empty language or not