 Solution

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

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

S \to AA, A \to a,

and the word

w = aa

. There is only one parse tree: its root uses

S \to AA

and each child uses

A \to a

. There are nevertheless exactly two derivations,

S \Rightarrow AA \Rightarrow a A \Rightarrow aa

and

S \Rightarrow AA \Rightarrow A a \Rightarrow aa,

according as the left or right occurrence of

A

is replaced first. This illustrates that derivations record replacement order while a context-free grammar parse tree does not.

 New to topics? Read the docs here!