On Greibach normal form construction (Q5966461)

We present an algorithm which, given an arbitrary \(\epsilon\)-free and chain-free context-free grammar, produces an equivalent context-free grammar in Greibach normal form (GNF). This algorithm is a generalization of an algorithm recently presented by Ehrenfeucht and Rozenberg. Using this algorithm, the well-known GNF construction of Rosenkrantz can be obtained. Furthermore it is possible to rewrite a given context-free grammar by a GNF grammar which has at most twice as much nonterminals as the original grammar. This result is shown to be optimal (with respect to the number of nonterminals).