Concatenation grammar 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.
Nonproductive nonterminal Created 2026-09-24 Updated 2026-11-05
A nonterminal symbol of a formal grammar is productive if for some word consisting only of terminal symbols; otherwise it is nonproductive. In a context-free grammar, a sentential form containing a nonproductive nonterminal symbol cannot derive a terminal word: the descendants of that occurrence would have to provide a terminal derivation from the nonterminal symbol. Consequently productions involving nonproductive nonterminal symbols can be discarded when simplifying a context-free grammar.
The context-free hypothesis matters. A general variable-based grammar can have a production rule while neither nor alone derives a terminal word. A terminal derivation from a larger context therefore need not demonstrate productivity of each individual nonterminal symbol.
A variable-based grammar is a tuple
where and are disjoint finite sets of terminals and variables, , and each production has with at least one variable in .