 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ii/paper-3/4h/c/solution

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

Introduce nonterminals for the terminals and one for the pair

bb

A \to a, B \to b, C \to c, U \to BB .

Because the original start symbol occurs on a right-hand side, take a fresh start symbol

S_{0}

. After eliminating the unit production

S \to T

, one grammar in Chomsky normal form is

S_{0} S U A \to S U ∣ A S ∣ CC, \to S U ∣ A S ∣ CC, \to BB, \to a, B \to b, C \to c .

The original grammar generates exactly

{a^{i} cc b^{2 j} : i, j \geq 0} .

The displayed grammar generates the same set:

A S

adds an

a

on the left,

S U

adds one

bb

pair on the right, and

CC

terminates the derivation with

cc

. Since the original grammar does not generate

ϵ

L (G) = L (G_{Chom}) .

 New to topics? Read the docs here!