computer-science - Context Free 语言的一个子集是 Context Free？

Question

我一直在解决这个练习，我不知道从哪里开始:

语言 B 是上下文无关的；语言 C 是 B 的子集:C 是否是上下文无关的？证明或反驳。

我试过使用闭包属性:

C = B - ( (A* - C) ∩ B ) [A* 是字母 A 上所有单词的集合]

考虑到 CF 语言在互补和交叉下不是封闭的，我会说 C 不会被迫成为 CF。但我不确定这是一个很好的证明。

任何人都可以帮忙吗？

Answer 1

这是一个提示。正则语言的子集不一定是正则:a*b*是常规的，但是 a^nb^n是 a*b* 的子集并且不定期。你能想到上下文无关语言的并行吗？