
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 1996  Copyright 1996 Universität Bonn, Institut für Informatik, Abt. V  
85151

Greibach Normal Form Transformation, Revisted
Norbert Blum, Robert Koch [Download PostScript] [Download PDF] We develop a direct method for placing a given contextfree grammar into Greibach normal form with only polynomial increase of its size; i.e., we don't use any algebraic concept like formal power series. Starting with a cfg $G$ in Chomsky normal form, we will use standard methods for the construction of an equivalent contextfree grammar from a finite automaton and vice versa for transformation of $G$ into an equivalent cfg $G'$ in Greibach normal form. The size of $G'$ will be $O(G^3)$, where $G$ is the size of $G$. Moreover, we show that it would be more efficient to apply the algorithm to a contextfree grammar in canonical two form, obtaining a contextfree grammar where, up to chain rules, the productions fulfill the Greibach normal form properties, and then to use the standard method for chain rule elimination for the transformation of this grammar into Greibach normal form. The size of the constructed grammar is $O(G^4)$ instead of $O(G^6)$, which we would obtain if we transform $G$ into Chomsky normal form and then into Greibach normal form. 

Last Change:
08/18/99 at 13:00:38
English 
Universität Bonn > Institut für Informatik > Abteilung V 