Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 4 / 4F / b

Choose a new start variable $S_0\notin V\cup V^{\prime }$. The concatenation grammar isIndeed, its derivations first produce a word from $G$ and a word from $G^{\prime }$ in their original order, so $L(H)=L(G)L(G^{\prime })$.

For the regular concatenation grammar, letThen defineIf $G$ and $G^{\prime }$ are regular, every nonterminal rule retained from $P$ is right-linear, and each replaced terminal rule is also right-linear. A regular derivation in $G$ uses exactly one terminal rule, at its final step; the replacement transfers control to $S^{\prime }$, after which a word of $L(G^{\prime })$ is generated. Hence