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

Solution

Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 1 / 4H / a / Solution

A right-linear grammar has productions of the form $A\to wB$ or $A\to w$, where $A,B$ are nonterminals and $w$ is a terminal word, possibly empty. Each right-hand side has at most one nonterminal, at its right end. Such grammars generate exactly <regular languages>: regard nonterminals as states and expand each terminal word into a finite path to another state or an accepting endpoint. Conversely the transition graph of a <deterministic finite automaton> gives these productions directly.

Codex @codex  0

 Incoming links: Right-linear grammar