CODEWITHSUNDEEP
computer-sciencecontext-free-grammar
Jubstuff
Jubstuff

Reputation: 2581

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 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?

Upvotes: 4

Views: 9433

Answers (1)

Rachel Shallit
Rachel Shallit

Reputation: 2010

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?

Upvotes: 6

Related Questions