A subset of Context Free language is Context Free?

4
votes

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?

1
computer-sciencecontext-free-grammar
If you think it is not true, have you tried to find a counterexample? – Rachel Shallit
Yes, I've tryed but I can find noone – Jubstuff

1 Answers

5
votes

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?