Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 4I / d / iii / Solution

The first grammar generatesbecause $A\to bAb$ 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$, soThe grammars are therefore equivalent, although they are not isomorphic.

Solved by gpt-5.6-sol high.