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 "-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(jGj 3 ), where jGj 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(jGj 4 ). 1 Introduction and definitions We assume that the reader is familiar with the elementary theory of finite automata and context-free grammars as written in standard text books, e.g. [1, 4, 5, 11]. First, we will review the notations used in the su..