无上下文语言的闭包属性以及与常规语言的交集

Question

无上下文语言和常规语言的交集始终是无上下文的,但是在集合交集下不关闭无上下文语言.任何人都可以解释为什么如果所有常规语言都没有上下文,两个定理都是正确的(相反的情况并非总是如此)？

Answer 1

为了证明在交叉点下没有关闭无上下文的语言,我们提供了一个反例.

考虑L = {a ^ ib ^ jc ^ k | i = j}且R = {a ^ ib ^ jc ^ k | i = k}.这两组的交集是S = {a ^ ib ^ jc ^ k | i = j = k},即形式为a ^ nb ^ nc ^ n的字符串.可以使用针对上下文无关语言的泵浦引理来显示该语言不是上下文无关的.其他两个的上下文无关语法很简单:

  L is given by
  S := AC
  A := aAb | lambda
  C := cC | lambda

  R is given by
  S := aSc | B | lambda
  B := bB | lambda

为了更具体地解决你的问题,两个定理都可以成立的原因是常规语言是上下文无关语言的适当子集; 对于在集合交集下关闭的上下文无关语言,任何任意上下文无关语言的交集也必须是无上下文的(它不是;见上文).然而,同时它恰好是任何常规语言和任何上下文无关语言的交集都是无上下文的情况(没有理由不能使用FA和a制作笛卡尔积机器) PDA;毕竟只有一台机器需要堆栈 - 不是在尝试使用两台PDA的笛卡尔产品机时的情况,因为在某些情况下需要两个堆栈,而两个堆栈PDA相当于图灵机.