 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/ii/paper-3/4i/c/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

Two formal grammars over the same terminal alphabet are isomorphic when there is a bijection

ϕ : V_{0} \to V_{1}

between their nonterminals such that

ϕ (S_{0}) = S_{1}

and

α \to β \in P_{0} ⟺ ϕ (α) \to ϕ (β) \in P_{1},

where

ϕ

is extended to words by fixing each terminal and acting symbol by symbol.

 New to topics? Read the docs here!