Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 4I (Automata & Formal Languages)

For the formal grammar $G=(\Sigma ,V,P,S)$,Thus $L(G)$ contains exactly the finite terminal words reachable from the start symbol by a finite grammar derivation.

Two formal grammars over the same terminal alphabet are equivalent when they generate the same language:

Two formal grammars over the same terminal alphabet are isomorphic when there is a bijection $\varphi :V_0\to V_1$ between their nonterminals such that $\varphi (S_0)=S_1$ andwhere $\varphi$ is extended to words by fixing each terminal and acting symbol by symbol.

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.