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.
Retain every production of whose right-hand side contains a variable, replace every production with by , include , and use as start variable. If and are right-linear, the resulting grammar is right-linear and generates .
The regular construction relies on a regular derivation having exactly one terminal rule, at its end. In a general variable-based grammar several variables may each use terminal productions, so replacing every such production can introduce several copies of the second start variable.
Even if both input grammars are regular, the added production has two variables on its right-hand side and therefore need not be a regular production.

Articles by others on the same topic (0)

There are currently no matching articles.