We develop a direct method for placing a given context-free grammar into Greibach normal form with only polynomical 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 if would be more effcient to apply the algorithm to a context-free grammar in canconical 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.
展开▼
机译：我们开发了一种直接的方法，将给定的无内部语法放入Greibach正常形式，只有其尺寸的多元增加;即，我们不使用像正式电源系列这样的代数概念。从CFG G以Chomsky正常形式开始，我们将使用标准方法来从有限的自动机构构建等同的无线语法，反之亦然，以便在Greibach正常形式中转化为相当于CFG G'。 G'的大小将是O（| g |〜3），其中g |是G的大小。此外，我们表明，如果将算法应用于无与伦比的两种形式的无关语法，则获得不受联系的语法，在其中，达到连锁规则，产品符合Greibach正常的语法表单属性，然后使用链规范的标准方法消除该语法的转换为Greibach正常形式。构造的语法的尺寸是O（| g |〜4）代替O（| g |〜6），我们将获得，如果我们将g转化为胆碱正常形式，然后进入Greibach正常形式。
展开▼
