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 As, (a) Using induction on Iwi, prove that "(s, w) q in the DFA if and only if As wAq 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 when b is a single character and the recursive definition of - , for all if , 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 As, (a) Using induction on Iwi, prove that "(s, w) q in the DFA if and only if As wAq 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 when b is a single character and the recursive definition of - , for all if , and X is a production rule, then