Подмножество языка Context Free является Context Free?

Question

Я застрял в решении этого упражнения и не знаю, с чего начать:

Язык B не зависит от контекста;язык C является подмножеством B: является ли контекст C свободным?Доказать или опровергнуть.

Я пробовал использовать свойства замыкания:

C = B - ((A * - C) ∩ B) [A * - набор всех слов в алфавитеA]

и учитывая, что языки CF не закрыты при дополнении и пересечении, я бы сказал, что C не обязательно должен быть CF.Но я не уверен, что это хорошее доказательство.

Кто-нибудь может помочь?

Answer 1

Вот подсказка.Подмножество обычного языка не обязательно является регулярным: a*b* является регулярным, но a^nb^n является подмножеством a*b* и не является регулярным.Можете ли вы придумать параллель для контекстно-свободных языков?