 Solution

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

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

The grammars are non-equivalent. In the first grammar, terminal derivations without

A B \to c

give

{a^{r} b^{s} : r, s \geq 1} .

After applying

B \to B b

any number of times while

A

and

B

remain adjacent, the production

A B \to c

also gives

{c b^{t} : t \geq 0} .

Hence, in particular,

ab \in L (G_{0})

and

c \in L (G_{0})

In the second grammar, the fixed terminals

ab

X abY

prevent

X

and

Y

from ever becoming adjacent, so

X Y \to c

can never be used. The remaining productions give exactly

L (G_{1}) = {a^{r} b^{s} : r, s \geq 2} .

Thus $ab, c \in / L (G_{1})$ , proving that the generated languages differ.

 New to topics? Read the docs here!