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

The grammars are isomorphic. The bijectionmaps every production of $P_0$ to the corresponding production of $P_1$. They are therefore equivalent. Notice that $B$ in the first grammar and $C$ in the second are unreachable; the isomorphism also preserves this irrelevant component.

The grammars are non-equivalent. In the first grammar, terminal derivations without $AB\to c$ giveAfter applying $B\to Bb$ any number of times while $A$ and $B$ remain adjacent, the production $AB\to c$ also givesHence, in particular, $ab\in L(G_0)$ and $c\in L(G_0)$.

In the second grammar, the fixed terminals $ab$ in $XabY$ prevent $X$ and $Y$ from ever becoming adjacent, so $XY\to c$ can never be used. The remaining productions give exactlyThus $ab,c\notin L(G_1)$, proving that the generated languages differ.

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.