 Solution

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

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

The first grammar generates

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

because

A \to b A b

adds two

b

's and

A \to b

terminates the derivation.

In the second grammar,

Z

is a nonproductive nonterminal: every right-hand side of a

Z

-production still contains a

Z

. Consequently the branch

Y \to ZZ

never yields a terminal word. Every terminal derivation from

Y

instead uses

Y \to bYb

repeatedly and ends with

Y \to b

, so

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

The grammars are therefore equivalent, although they are not isomorphic.

 New to topics? Read the docs here!