Thread: Verify me answer please

So the question: Any regular language is context-free

So here is my proof by construction :

Let M=(Q,Σ,δ,q_0,F) be some DFA that accepts a regular language L. We construct a grammar G=(V,Σ,R,S) such that L(G)= L(M) as follows:

V={ | q ∈ Q }
S= ;where is the start symbol of M

R = ∪ where
→ ϵ iff δ(q,a) = f,where f∈F}
R={ →a iff δ(q,a)= r }

The above construction works because if the DFA goes from a state to a state for an input x∈Σ then the CFG does something similar. That is, the CFG generates x and the goes onto the next variable that is, it generates thus effectively, going to the next variable. We also add a rule the handle accepting states, that is if goes to the state where ∈F, then our CFG just terminates outputting epsilon. So we see that our CFG generates the input read from the DFA M, thusL(G)= L(M).



Is the construction correct? Is the above explanation sufficient to show that the construction is correct? Please check it for technical loop holes. Thanks for helping me again. Seems like your the only one that knows their stuff

Your construction is correct. I have only one remark.

Originally Posted by Matter_Math

R = ∪ where
→ ϵ iff δ(q,a) = f,where f∈F}
R={ →a iff δ(q,a)= r }

The rule X_q → ϵ does not generate any terminal symbol while the transition from q to f reads the symbol a. You should have either X_q → a or X_f → ϵ where f is an accepting state. The second variant is better because it accounts for the case when there is an empty word in the language. And, of course, the second part of R should be labeled R_2 above.

Whether this explanation is sufficient depends on the requirements of your course. To be strict, one has to have an argument by induction on the length of the word. For this, one has to generalize the statement "A word is accepted by the automaton iff it is generated by the grammar" to describe the intermediate situation, when only a part of the word has been read and generated. It's a good exercise to formulate such general induction statement; after that, the base case and the step are pretty obvious.

Note that the grammar you constructed is called a right regular grammar.

Thanks for the help. The professor is pretty strict. I will try to do induction to its length. Thanks again. I'll post back soon.

Hey I'm stuck. Can you help me. Not sure how to start after thinking about it a little bit.

The induction statement P(n) is: "For every word w of length n in , the automaton is in state q after reading w iff the grammar generates w ". Then from "for all n, P(n)" one can derive "A word w in is accepted by the automaton iff it is generated by the grammar".