大门|大门IT 2005 |问题4

设L是一种规则语言，M是一种上下文无关语言，两者都在字母表∑上。设Lc和Mc分别表示L和M的补数。以下哪项关于语言的陈述∪ Mc是真的 （A） 它必须是规则的，但不一定是上下文无关的 （B） 它必须与上下文无关。 （C） 它必然是不规则的。 （D） 以上都不是 答复: （D） 说明：

提议： L是一种常规语言 M是一种上下文无关的语言 推导： L_c并集M_c=补{L交M} 现在，根据CFL的闭包定律，L交点M是一个CFL，即CFL与RL的交点始终是一个CFL。 但是，补码{L交M}可能不是CFL，因为CFL上的补码不能保证CFL。它甚至可以是RL，也可能位于CFL圈之外。它肯定会是一种上下文敏感的语言，但除此之外别无他言。 结论： 考虑到上述推导，这些陈述都是不真实的。因此，正确的答案应该是（D）以上都不是。

相关文章：

https://www.geeksforgeeks.org/closure-properties-of-context-free-languages/

这个解决方案是由 维内特·珀斯瓦尼 . 这个问题的小测验