確定一種語言是否無上下文

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）。