Some Preservation Properties of Normal Form Grammars
David B. Benson · SIAM Journal on Computing · 1977
The normal form grammars, such as those developed by Chomsky and Greibach, preserve certain properties of the original grammar. Ordinarily attention is only directed to weak equivalence, that is, that the original grammar and its normal form version both generate the same language. By paying greater attention to the functions carrying a grammar to its normal form, considerably stronger preservation properties can be proved. We demonstrate that several normal forms preserve ambiguities. More surprisingly, a variant of Chomsky’s normal form, called canonical two form, forms an adjunction in connection with the original grammar. This fact shows that canonical two form preserves a large number of the structural properties of the original grammar. In particular, we show that the canonical two form is $LR(k)$ if the original grammar is $LR(k)$, strengthening a result of Gray and Harrison. Preservation of structural properties such as ambiguity is important in semantic considerations, and the methods given for the determination of property preservation seem to be of general applicability.