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?
精彩评论