= Solution
Let a <deterministic finite automaton> recognizing the <regular language> have states $Q$, start state $q_0$, accepting states $F$, and transition <function> $\delta$. Construct a <context-free grammar> with one nonterminal $A_q$ for every state, start symbol $A_{q_0}$, and productions
$$
A_q\to aA_{\delta(q,a)}\quad(q\in Q,\ a\in\Sigma),
\qquad A_q\to\varepsilon\quad(q\in F).
$$
Induction on the length of a word shows that $A_q$ derives $wA_r$ exactly when the automaton reaches $r$ from $q$ after reading $w$. The terminal production can then end the derivation precisely at an accepting state. Thus the grammar generates exactly the recognized language, proving \b[every <regular language> is a <context-free language>]. This is actually a <right-linear grammar>, a special case of a <context-free grammar>.
Back to article page
