Context Free語言的一個子集是Context Free？

我被困在解決這個練習中，我不知道從哪裏開始：Context Free語言的一個子集是Context Free？

語言B是Context Free;一種語言C是B的一個子集：是C Context Free？證明或反駁。

我使用封閉性tryed：

C =乙 - （（A * - C）∩B）[A *是一組上的字母A的所有詞語]

和給定CF語言在互補和交集下沒有關閉我會說C不是被迫成爲CF.但我不確定這是一個很好的證明。

任何人都可以幫忙嗎？

2011-06-16 JustB

如果你認爲這不是真的，你有沒有試圖找到一個反例？ – 2011-06-16 18:21:30

是的，我已經嘗試過，但我找不到任何人 – JustB 2011-06-16 23:42:34

這是一個提示。常規語言的子集不一定是常規的：a*b*是常規的，但a^nb^n是a*b*的子集，並且不規則。你能想到一個並行的上下文無關語言嗎？

2011-06-17 00:28:52

因此，例如：B = {A^n B^m C^n | n，m> 0}; A = {A^n B^m C^n | N = M}。 A是B的一個子集，但它不是CF. – JustB 2011-06-22 23:08:01

@JustB：優秀！ – 2011-06-23 02:41:38

回答