 Solution

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

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

Take

G^{'} = ({a, b}, {S, A, B}, P^{'}, S),

where

P^{'} = {S \to A B A, A \to A B, B \to B A, A \to a, B \to b} .

This grammar is in Weak Chomsky normal form. In the original grammar,

C

occurs only in

S \to A C

and has the sole production

C \to B A

. Thus every use of

S \to A C \to A B A

is replaced in

G^{'}

S \to A B A

, while every later production is unchanged. Conversely, the ternary production can always be expanded into those two original steps. Therefore

G^{'}

is equivalent to

G

 New to topics? Read the docs here!