3

上下文无关语言和常规语言的交集始终是上下文无关的，但上下文无关语言在集合交集下不封闭。如果所有常规语言都是上下文无关的（相反的情况并非总是如此），谁能解释为什么这两个定理都是正确的？

4

1 回答 1

7

为了证明上下文无关语言在交集下不是封闭的，我们提供了一个反例。

考虑 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 和PDA；毕竟只有一台机器需要一个堆栈——在尝试使用两个 PDA 的笛卡尔积机器时并非如此，因为在某些情况下需要两个堆栈，而两个堆栈 PDA 相当于图灵机）。

于 2011-08-11T15:51:35.223 回答