Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 4 4I ii Solution Created 2026-09-24 Updated 2026-09-25
We prove the claim by induction on the length of the grammar derivation from . At length zero the sentential form is , which has the required form.
Suppose the current sentential form is . Because is terminal, the only symbol to which a production can apply is . A production producesagain a terminal word followed by one variable. A production produces the terminal word . Once a completely terminal word is reached, no further production can apply. The induction proves the sentential form of a right-linear regular grammar: every reachable is either or .