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

Question

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

Answer 1

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

考虑 L = {a^ib^jc^k | i = j} 且 R = {a^ib^jc^k |我= 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 和 FA 来制作笛卡尔积机） PDA；毕竟只有一台机器需要堆栈 - 尝试使用两个 PDA 的笛卡尔积机器时情况并非如此，因为在某些情况下需要两个堆栈，而两个堆栈 PDA 相当于图灵机）。