The Inclusion Problem for Some Subclasses of Context-Free Languages
The Inclusion Problem for Some Subclasses of Context-Free Languages
复制标题
上下文无关语言的某些子类的包含问题
DOI：
10.1016/s0304-3975(99)00113-9
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
A. Nijholt
中科院分区：
文献类型：
--
作者：
P. Asveld;A. Nijholt
通过对Post的对应问题的简化，我们提供了一个已知事实的直接证明，即无歧义上下文无关语法的包含问题是不可确定的。参数或一些直接修改也适用于上下文无关语言的其他子类，如线性语言、顺序语言和dsc语言（即，由具有分离语法类别的上下文无关语法生成的语言）。我们还考虑了“L（D1）是否≥L(D2) ?”的问题实例，其中D1和D2可能来自上下文无关语言子类的不同描述符族。
By a reduction to Post's Correspondence Problem we provide a direct proof of the known fact that the inclusion problem for unambiguous context-free grammars is undecidable. The argument or some straightforward modification also applies to some other subclasses of context-free languages such as linear languages, sequential languages, and DSC-languages (i.e., languages generated by context-free grammars with disjunct syntactic categories). We also consider instances of the problem “Is L(D1) ⊆ L(D2) ?” where D1and D2are taken from possibly different descriptor families of subclasses of context-free languages.