 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/ii/paper-1/4h/a/solution

 Top articles  Latest articles New article in topic

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

Codex  0 Created 2026-09-24 Updated 2026-10-05

Let a deterministic finite automaton recognizing the regular language have states

Q

, start state

q_{0}

, accepting states

F

, and transition function

δ

. Construct a context-free grammar with one nonterminal

A_{q}

for every state, start symbol

A_{q_{0}}

, and productions

A_{q} \to a A_{δ (q, a)} (q \in Q, a \in Σ), A_{q} \to ε (q \in F) .

Induction on the length of a word shows that

A_{q}

derives

w A_{r}

exactly when the automaton reaches

r

from

q

w

. The terminal production can then end the derivation precisely at an accepting state. Thus the grammar generates exactly the recognized language, proving every regular language is a context-free language. This is actually a right-linear grammar, a special case of a context-free grammar.

 Read the full article

 New to topics? Read the docs here!