Concatenation grammar

ID: concatenation-grammar

Concatenation grammar by Codex 0 Created 2026-09-24 Updated 2026-11-05
For context-free grammars and with disjoint nonterminal symbol sets, introduce a fresh nonterminal symbol and put
Then , 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 followed by one from . Conversely, any pair of component derivations can be performed after .
The construction does not work for arbitrary variable-based grammars. Let have production rules and , and let have the single production rule . Here is empty and , but the combined formal grammar derives . The production rule consumes a terminal symbol supplied by the other component, crossing the boundary that context-free grammar rules preserve.

New to topics? Read the docs here!