确定一种语言是否无上下文

Question

可以说你有一种语言L，并且你想确定它是否是上下文无关的。与常规语言相交的上下文无关语言是上下文无关的。这足以证明L无上下文吗？

含义，

大号相交P = T其中P是一个正则语言和T是上下文。这是否意味着L无上下文？

Answer 1

不，你的发言是不是是真的。考虑下面的反例：

L = {0n1n2n | n > 0}, P = T = Ø。很明显，我们有L ∩ P = L ∩ Ø = Ø = T，Ø是规则的和上下文无关的。

请注意，众所周知L不是上下文无关的（see example on p.12 for a sketch proof by pumping lemma）。