set - 2 种上下文无关语言的集合差异是上下文无关的吗？

Question

我在互联网上搜索过，大多数人说只是说上下文无关语言对于联合、连接、反转和 Kleene Star 是关闭的。它们是否也因设置差异而关闭？

Answer 1

上下文无关语言不会在设定差异下关闭。看到这一点的一种方法是注意

1. 上下文无关语言在互补下不封闭，
2. 语言 Σ* 是上下文无关的，并且
3. 对于任何语言 L，L 的补码由 Σ* - L 给出。

因此，如果 CFL 在设定差异下关闭，那么它们将在互补下关闭……除了它们不是。:-)