1. Consider the following method to convert a DFA to a CFG. Let M-(Q, , , s, F) be a DFA. Construct a CFG G with: nonterminals {Aq I q Q), starting nonterminal A production rules {A, cA, | (p, c)-g) u 14, l p F} (a) Using induction on lwl, prove that "(s, w) q in the DFA if and only if As-wA in the CFG. Then prove that L(M)L(G), hence the conversion from DFA to CFG is correct. (b) Draw the DFA that identifies multiples of 3 in binary. Give names to the states, and then show the CFG that you get when converting this DFA using the approach above Note: You may wish to recall the recursive definition of ": def def s S(q, wb)-6(8" (q, w), b) when b is a single character and the recursive definition of -, for all f -AXy, and X is a production rule, then - 1. Consider the following method to convert a DFA to a CFG. Let M-(Q, , , s, F) be a DFA. Construct a CFG G with: nonterminals {Aq I q Q), starting nonterminal A production rules {A, cA, | (p, c)-g) u 14, l p F} (a) Using induction on lwl, prove that "(s, w) q in the DFA if and only if As-wA in the CFG. Then prove that L(M)L(G), hence the conversion from DFA to CFG is correct. (b) Draw the DFA that identifies multiples of 3 in binary. Give names to the states, and then show the CFG that you get when converting this DFA using the approach above Note: You may wish to recall the recursive definition of ": def def s S(q, wb)-6(8" (q, w), b) when b is a single character and the recursive definition of -, for all f -AXy, and X is a production rule, then