3. This problem is concerned with the string encodings of DFAs. Fix the alphabet = {0, 1}; then one way to encode the DFA (Q, , 8, qo, F) is by the string 10(0,0))((0, 1)) ... ((q|Q|, 1))0(F), where we encode (qi, ) =q; by 12, and the set F by its characteristic vector: the i-th bit of (F) is 1 if q; E F and 0 otherwise. (thus 10 000 encodes the DFA with one state, go, with 8(90, 0) = 8(90, 1) = qo, and F = {}, while 10001 encodes the DFA with the same transition function and F = {0}.) Once we fix an encoding, we consider the language DDFA = {(M) | M is a DFA that rejects (M)}. So for example, 10000 DDFA, while 10001 DDFA. (a) Show that DDFA is decidable: e.g. describe a TM to decide, given the string (M), whether the DFA M will reject (M). (you do NOT need to give the state diagram for this TM.) (b) Prove that DDFA is not regular.