I. 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 {Ap cAq I (, c)-q) U {Ap l pe F} (a) Using induction on lwl, 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 pxy, and X is a production rule, then I. 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 {Ap cAq I (, c)-q) U {Ap l pe F} (a) Using induction on lwl, 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 pxy, and X is a production rule, then