Concatenation grammar (source code)

= Concatenation grammar

For <context-free grammars> $G=(V,\Sigma,P,S)$ and $G'=(V',\Sigma,P',S')$ with disjoint <nonterminal symbol> <sets>, introduce a fresh <nonterminal symbol> $S_0$ and put
$$
H=(V\cup V'\cup\{S_0\},\Sigma,P\cup P'\cup\{S_0\to SS'\},S_0).
$$
Then $L(H)=L(G)L(G')$, the <concatenation> of the two <formal languages>. After the first production, every <production rule> acts within one of the two component <parse trees>. Their terminal <words> form one <word> from $L(G)$ followed by one from $L(G')$. Conversely, any pair of component derivations can be performed after $S_0\to SS'$.

The construction does not work for arbitrary <variable-based grammars>. Let $G$ have <production rules> $S\to A$ and $Aa\to b$, and let $G'$ have the single <production rule> $S'\to a$. Here $L(G)$ is empty and $L(G')=\{a\}$, but the combined <formal grammar> derives $S_0\Rightarrow SS'\Rightarrow AS'\Rightarrow Aa\Rightarrow b$. The <production rule> $Aa\to b$ consumes a <terminal symbol> supplied by the other component, crossing the boundary that <context-free grammar> rules preserve.