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 | q Q},

Starting nonterminal As,

production rules {Ap cAq | (p, c) = q} U {Ap | p F}

a) Using induction on |w|, 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.

I'm a little confused on how to go about this. This was provided for help:

Note:

You may wish to recall the recursive definition of *:

*(q,) = q

*(q, wb) = (*(q, w) ,b) When b is a single character

and the recursive definition of * :

* , for all

if * X, and X is a production rule, then *