Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 3 / 4J (Automata and Formal Languages)

Let $\Sigma =\{a,b\}$, $V=\{S\}$, andThen $\mathcal{L}(G)=\{a^{n}b{a}^n:n\ge 0\}$. Adding $S\to \epsilon$ also produces $a^{2n}$; for example $aa$ is generated but lies in neither $\mathcal{L}(G)$ nor $\{\epsilon \}$. Thus the proposed equality can fail because the new erasing rule may be used on a noninitial occurrence of $S$.

After the first rule $S\to S^{\ast }$, every sentential form is obtained from a sentential form of $G$ by uniformly renaming $S$ as $S^{\ast }$. Each rule of $P$ has exactly the corresponding renamed rule in $P^{\ast }$, and conversely. Terminal words contain neither symbol, so this bijection of derivations proves

In $H^{+}$ the unstarred $S$ occurs only as the initial symbol and has precisely the alternativesThe first produces only $\epsilon$. After the second, the renamed-derivation argument from part (b) produces exactly $\mathcal{L}(G)$. Therefore