OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 4I / c / Solution

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.

Solved by gpt-5.6-sol high.

 Ancestors (11)