论文标题
较弱的格里巴赫正常形式的超边替换语法
Weak Greibach Normal Form for Hyperedge Replacement Grammars
论文作者
论文摘要
众所周知，在定义和属性的意义上，HyperDege替换语法类似于无弦上下文语法。因此，我们预计从字符串语法到超法语法的众所周知的Greibach正常形式的概括。这种广义的正常形式在几篇论文中呈现。但是，它们不涵盖大量的超图语言（例如由星形图组成的语言）。在本文中，我们引入了一种弱的Greibach正常形式，其定义对应于字符串语法的词汇化正常形式，并证明可以以这种正常形式的语法生成每种无上下文的超图（具有非上下文异常）。本文提供的证据概括了一个具有更多技术性的字符串语法的相应的证明。
It is known that hyperedge replacement grammars are similar to string context-free grammars in the sense of definitions and properties. Therefore, we expect that there is a generalization of the well-known Greibach normal form from string grammars to hypergraph grammars. Such generalized normal forms are presented in several papers; however, they do not cover a large class of hypergraph languages (e.g. languages consisting of star graphs). In this paper, we introduce a weak Greibach normal form, whose definition corresponds to the lexicalized normal form for string grammars, and prove that every context-free hypergraph language (with nonsubstantial exceptions) can be generated by a grammar in this normal form. The proof presented in this paper generalizes a corresponding one for string grammars with a few more technicalities.
