Generalized context-free grammars and multiple context-free grammars
Generalized context-free grammars and multiple context-free grammars
复制标题
广义上下文无关文法和多重上下文无关文法
DOI：
10.1002/scj.4690200705
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
M. Fujii
中科院分区：
文献类型：
--
作者：
T. Kasami;H. Seki;M. Fujii
结果表明，Pollard 引入的广义上下文无关文法（gcfg）生成的语言类正是递归可枚举集类。接下来，介绍了 gcfg 的一个子类，称为多重上下文无关语法（mcfg's），并证明由 mcfg 生成的语言类正确地包含上下文无关语言类，并且正确地包含在上下文相关语言类中。在 mcfg 中，可以以特别简单的方式解释涉及不连续成分的结构。上下文无关语法（cfg）中的短语结构和派生树等概念可以在 mcfg 中自然扩展。此外，由 mcfg 生成的语言类享有上下文无关语言类所具有的形式语言理论闭包属性。
It is shown that the class of languages generated by generalized context-free grammars (gcfg's) introduced by Pollard is exactly the class of recursively enumerable sets. Next, a subclass of gcfg's called multiple context-free grammars (mcfg's) is introduced and it is shown that the class of languages generated by mcfg's properly contains the class of context-free languages and is properly contained in the class of context-sensitive languages. In mcfg's, it is possible to account for structures involving discontinuous constituents in a particularly simple manner. Such concepts as phrase structure and derivation tree in context-free grammars (cfg's) can be extended naturally in mcfg's. Furthermore, the class of languages generated by mcfg's enjoys the formal language-theoretic closure properties that the class of context-free languages does.