上下文无关语言的一个问题

[troyl]

刚刚看到：
语言 L₁ = {aⁿbⁿcⁱ: n,i ≥ 0}
语言 L₂ = {aⁱbⁿcⁿ: n,i ≥ 0}.
L₁ 和 L₂ 都是上下文无关语言。
但是它们的交集 L = L₁ ∩ L₂ 即 L = {aⁿbⁿcⁿ: n ≥ 0} 却不是上下文无关语言（这个可以用泵引理证明）。

我的问题是，有没有这种可能：
L₁ 和 L₂ 都 *不是* 上下文无关语言，但是它们的交集 L = L₁ ∩ L₂ 却 *可能是* 上下文无关的呢？

希望各位能予解惑。
在此谢过。

[laskuma]

来这问theory的问题估计不会有太多回答吧 愣了一分钟才反应过来。。 原来是context free language.....

[casparchen]

看了楼上的回复突然想到了那个打棒ball的典故

[troyl]

我想到了！
假设

L₁ = {aⁱbʲcᵏ: i < j < k}
L₂ = {aⁿbⁿcⁿ|n ≥ 0}

通过泵引理，我们可以知道，L₁ 和 L₂ 都不是上下文无关语言。
而它们的交集

L = L₁ ∩ L₂ = ∅

这个 L 是上下文无关的，因为我们可以写出它的上下文无关语法：

S → S

证毕（不过我不确定对不对==）

[laskuma]

@casparchen 没办法 我就是一条留学狗 从最基础的东西开始 学的都是英文的 硬跟我说中文可能我都反应不过来

[est]

nice unicode

[Golevka]

我构造出一个例子不知对不对:
L₁: {a bⁿcⁿdⁿ | n >= 1}
L₂: {aⁱbⁿcⁱdⁿ | i, n >= 1},
L₁ ∩ L₂ -> abcd (context free)

[troyl]

@Golevka 你确定 a bⁿcⁿdⁿ 和 aⁱbⁿcⁱdⁿ 都是 non-context-free 的吗？

[Golevka]

@troyl a bⁿcⁿdⁿ应该是non context free, aⁱbⁿcⁱdⁿ不知道.

[Golevka]

@troyl 刚才又翻了下dragon book, aⁱbⁿcⁱdⁿ是non context free无误.

[troyl]

@Golevka Wow! Dragon Book!