开发者

A subset of Context Free language is Context Free?

I'm stuck at solving this exercise, and I don't know where to begin:

A language B 开发者_StackOverflowis 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?


Here's a hint. A subset of a regular language is not necessarily regular: a*b* is regular, but a^nb^n is a subset of a*b* and is not regular. Can you think of a parallel for context-free languages?

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜