 Solution

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

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

One parse tree can be recorded unambiguously by the nested expression

S (A (A (a), B (b)), C (B (b), A (A (A (a), B (b)), B (B (b), A (a))))) .

Every internal node uses one of the given productions, and the leaves read from left to right are

a, b, b, a, b, b, a .

Equivalently, the corresponding leftmost grammar derivation is

S \Rightarrow A C \Rightarrow A BC \Rightarrow a BC \Rightarrow ab C \Rightarrow ab B A \Rightarrow abb A \Rightarrow abb A B \Rightarrow abb A BB \Rightarrow abba BB \Rightarrow abbab B \Rightarrow abbab B A \Rightarrow abbabb A \Rightarrow abbabba .

Hence the required word is generated by the grammar.

 New to topics? Read the docs here!