Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 4 / 4F (Automata & Formal Languages)

A variable-based grammar is a tuplewhere $\Sigma$ and $V$ are disjoint finite sets of terminals and variables, $S\in V$, and each production $\alpha \to \beta$ has $\alpha ,\beta \in (\Sigma \cup V{)}^{\ast }$ with at least one variable in $\alpha$.

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

LetBoth are regular grammars and their variable sets are disjoint. Their ordinary concatenation grammar adds a new ruleThis rule has two variables on its right-hand side, so it is not right-linear. Thus this is an explicit instance in which the concatenation grammar need not be regular.

TakeandThese are variable based and have disjoint variable sets. They satisfyIn $H^{\mathrm{reg}}$, however, both terminal productions of $G$ are replaced:Consequently its only terminal derivation issoThis realizes the failure of the regular concatenation construction for a nonregular grammar: two different terminal productions introduce two copies of $T$.