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={ $\displaystyle X_q$ | q ∈ Q }
S=$\displaystyle X_q0$;where $\displaystyle q_0$is the start symbol of M

R = $\displaystyle R_1$∪$\displaystyle R_2$where
$\displaystyle R_1= X_q$→ ϵ iff δ(q,a) = f,where f∈F}
R={ $\displaystyle X_q$→a $\displaystyle X_r$iff δ(q,a)= r }

The above construction works because if the DFA goes from a state $\displaystyle q_i$to a state $\displaystyle q_j$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 $\displaystyle X_i$generates $\displaystyle xX_j$thus effectively, going to the next variable. We also add a rule the handle accepting states, that is if $\displaystyle q_k$goes to the state $\displaystyle q_l$where $\displaystyle q_l$∈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

2. Your construction is correct. I have only one remark.
Originally Posted by Matter_Math
R = $\displaystyle R_1$∪$\displaystyle R_2$where
$\displaystyle R_1= X_q$→ ϵ iff δ(q,a) = f,where f∈F}
R={ $\displaystyle X_q$→a $\displaystyle X_r$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.

3. 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.

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

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