1.consider the following method to convert a DFA to a CFG

 

1. Consider the following method to convert a DFA to a CFG .LetM = (Q,Σ,δ,s,F)beaDFA.Construct a CFG G with:(1).nonterminals{Aq|q∈Q},(2).starTngnonterminalAs,(3).producTonrules{Ap →cAq |δ(p,c)=q}∪{Ap →ε|p∈F}(a) Using inducTon on |w|, prove that δ∗(s,w) = q in the DFA ifand only if As⇒=∗wAq in the CFG. ±hen prove that L(M) =L(G), hence the conversion from DFA to CFG is correct.(b) Draw the DFA that idenT es mulTples of 3 in binary. Givenames to the states, and then show the CFG that you get whenconverTng this DFA using the approach above.Note: You may wish to recall the recursive de niTon of δ∗:∗defWhen b is a single characterifα⇒= βXγ,andX →δ isaproducTonrule,thenα⇒= βδγ2.Convert the following CFG to Chomsky norma lform(showsteps for be²er parTa lcredit):S →aSddd |±± → b±dd | RR → cR | ε3.Show that the following languages are context-free:(a) {akbmcn | k,m,n not all equal}(b) {xcy | x,y∈{a,b}∗and rev(x) is a substring of y}In other words: strings that contain a single c character, wherethe part of the string occurring before c appears reversedsomewhere a³er the c. Example: aaabbcabababbbaaabba is inthe language.

Attachments:

• 1494296876-homework6.docx