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.

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 {Ap cAq | (p, c)-qJU {Ap l p F} (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 wb) - when b is a single character and the recursive definition of , for all fr xr, and X-i is a production rule, then