context-free-grammar - 上下文无关语言的闭包特性和与常规语言的交集

Question

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

Answer 1

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

考虑 L = {a^i b^j c^k | i = j} 和 R = {a^i b^j c^k |我 = k}。这两组的交集是 S = {a^i b^j c^k | i = j = k}，即 a^n b^n c^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 相当于图灵机)。