Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1996 Copyright 1996 University of Bonn, Department of Computer Science, 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 context-free 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 context-free 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 context-free grammar in canonical two form, obtaining a context-free 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V