假设您有一种语言 L，并且您想确定它是否是上下文无关的。与常规语言相交的上下文无关语言是上下文无关的。这足以证明 L 是上下文无关的吗？
意义，
L intersect P = T 其中 P 是常规语言，T 是上下文无关的。这是否意味着 L 是上下文无关的？
问问题
249 次
1 回答
0
不，你的说法不正确。考虑以下反例：
L = {0n1n2n | n > 0}, P = T = Ø. 显然我们有L ∩ P = L ∩ Ø = Ø = T, 并且Ø是常规的和上下文无关的。
请注意，众所周知，L它不是上下文无关的（参见第 12 页上的示例，以获取通过抽取引理的草图证明）。
于 2015-02-24T04:47:04.970 回答