A variable-based grammar has disjoint finite terminal and variable alphabets , a start variable , and productions in which and contains at least one variable.
A nonterminal is unreachable when no word derivable from the start symbol contains it. Productions whose left sides are unreachable do not affect the generated language.
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 right-linear regular grammar has productions of the forms and , where are variables and is a terminal word.
Every sentential form reachable from the start variable of a right-linear grammar is either a terminal word or , where is the unique variable and occurs at the right end.
If a finite right-linear grammar generates an infinite language, some variable is accessible, looping, and terminable. It is the repeated variable on a sufficiently long accepting derivation.
For context-free grammars and with disjoint nonterminal symbol sets, introduce a fresh nonterminal symbol and putThen , 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
There are currently no matching articles.