 Solution

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

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

The compressed initial production gives the leftmost derivation

S \Rightarrow A B A \Rightarrow A BB A \Rightarrow a BB A \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 .

It has

12

steps, whereas part (b) gives

2 \cdot 7 - 1 = 13

for every derivation in Chomsky normal form. The Weak Chomsky normal form ternary rule has compressed exactly one pair of binary productions, so the derivation is strictly shorter as required.

 New to topics? Read the docs here!