上下文无关语言的子集是上下文无关的吗？
我被困在解决这个练习中，而且我不知道从哪里开始：
A 语言 B 是上下文无关的；语言 C 是 B 的子集：C 是上下文无关的吗？证明或反驳。
我尝试过使用闭包属性：
C = B - ( (A* - C) ∩ B ) [A* 是字母表 A 上所有单词的集合]
并考虑到 CF 语言在补码和交集下不闭合，我会说C没有被迫成为CF。但我不确定这是一个很好的证明。
有人可以帮忙吗？
I'm stuck at solving this exercise, and I don't know where to begin:
A language B is Context Free; a language C is a subset of B: is C Context Free? Prove or disprove.
I've tryed using closure properties:
C = B - ( (A* - C) ∩ B ) [A* is the set of all words on the alphabet A]
and given that CF languages are not closed under complementation and intersection I would say that C is not forced to be CF. But I'm not sure this is a good prove.
Can anyone help?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是一个提示。正则语言的子集不一定是正则的：
a*b*是正则的，但a^nb^n是a*b*< 的子集/code> 并且不规则。你能想到上下文无关语言的相似之处吗？Here's a hint. A subset of a regular language is not necessarily regular:
a*b*is regular, buta^nb^nis a subset ofa*b*and is not regular. Can you think of a parallel for context-free languages?