Context Derivation Sets and Context-Free Normal Forms

A set of transformations is presented that will convert an arbitrary context-tree grammar to six of the normal forms for which the right hand side of any production has at most two occurrences of nonterminal symbols. These transformations form the basis of a meta-normal form algorithm for context-free grammars. The algorithm takes as input an arbitrary context-free grammar and a target normal form, expressed as an extended two-symbol grammar form, and converts the grammar to that normal form. The number of nonterminals and productions in the output grammars of each of the base transformations is minimal.