Greibach Normal Form Transformation, Revisited

We develop a new method for placing a given context-free grammar into Greibach normal form with only polynomial increase of its size. Starting with an arbitrary $\varepsilon$-free context-free grammar G, we transform G into an equivalent context-free grammar H in extended Greibach normal form; i.e., in addition to rules, fulfilling the Greibach normal form properties, the grammar can have chain rules. The size of H will be O(|G|³), where |G| is the size of G. Moreover, in the case that G is chain rule free, H will be already in Greibach normal form. If H is not chain rule free then we use the standard method for chain rule elimination for the transformation of H into Greibach normal form. The size of the constructed grammar is O(|G|⁴).