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
-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*|^{3}), 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*|^{4}).