Need help on theory of computation, appreciate for clear explanation:

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 E Q} > starting nonterminal As, production rules A, cAq I (p, c)-qJU {Ap E l p E 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 ofS* def when b is a single character and the recursive definition of-> --> , for all if -> Xy, 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 E Q} > starting nonterminal As, production rules A, cAq I (p, c)-qJU {Ap E l p E 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 ofS* def when b is a single character and the recursive definition of-> --> , for all if -> Xy, and X is a production rule, then