Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
复制标题
DOI：
10.1007/978-3-030-40608-0_24
复制
发表时间：
2020-01-07
期刊：
影响因子：
--
通讯作者：
Yamakami T
中科院分区：
文献类型：
--
作者：
Yamakami T
我们研究了确定性上下文无关语言的有限交集和并集的计算复杂性。早些时候，Wotschke（1978）基于Liu和Weiner（1973）的层次分离证明了对于任何正整数d，确定性上下文无关语言的交集一般比d确定性上下文无关语言的交集更强大。刘和韦纳的论点，但是，工程只对有界语言的特定形式，因此Wotschke的结果不能扩展到反驳任何其他语言被写在一个交叉的形式d确定性上下文无关的语言。为了处理各种语言的非成员关系，我们绕过了他们的证明论点，而是设计了一个新的，实用的技术工具：确定性上下文无关语言的有限联合的泵引理。由于确定性上下文无关语言家族在互补下是封闭的，因此这个泵引理使我们能够显示由甚至无界语言的有限交集组成的语言的非成员关系。我们还提到了与Hibbard有限自动机的关系。
We study the computational complexity of finite intersections and unions of deterministic context-free languages. Earlier, Wotschke (1978) demonstrated that intersections of deterministic context-free languages are in general more powerful than intersections of d deterministic context-free languages for any positive integer d based on the hierarchy separation of Liu and Weiner (1973). The argument of Liu and Weiner, however, works only on bounded languages of particular forms, and therefore Wotschke’s result cannot be extended to disprove any other language to be written in the form of an intersection of d deterministic context-free languages. To deal with the non-membership of a wide range of languages, we circumvent their proof argument and instead devise a new, practical technical tool: a pumping lemma for finite unions of deterministic context-free languages. Since the family of deterministic context-free languages is closed under complementation, this pumping lemma enables us to show a non-membership relation of languages made up with finite intersections of even non-bounded languages as well. We also refer to a relationship to Hibbard’s limited automata.