这是一个创建于 4062 天前的主题，其中的信息可能已经有所发展或是发生改变。
刚刚看到：
语言 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₂ 却 *可能是* 上下文无关的呢？
希望各位能予解惑。
在此谢过。
语言 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₂ 却 *可能是* 上下文无关的呢？
希望各位能予解惑。
在此谢过。
 |
1
laskuma 2013-10-10 07:23:28 +08:00 via iPhone
来这问theory的问题估计不会有太多回答吧 愣了一分钟才反应过来。。 原来是context free language.....
|
 |
2
casparchen 2013-10-10 07:37:25 +08:00 via iPad
看了楼上的回复突然想到了那个打棒ball的典故
|
 |
3
troyl OP 我想到了！
假设 L₁ = {aⁱbʲcᵏ: i < j < k} L₂ = {aⁿbⁿcⁿ|n ≥ 0} 通过泵引理，我们可以知道，L₁ 和 L₂ 都不是上下文无关语言。 而它们的交集 L = L₁ ∩ L₂ = ∅ 这个 L 是上下文无关的，因为我们可以写出它的上下文无关语法： S → S 证毕（不过我不确定对不对==） |
|
4
laskuma 2013-10-10 08:41:51 +08:00
@casparchen 没办法 我就是一条留学狗 从最基础的东西开始 学的都是英文的 硬跟我说中文可能我都反应不过来
|
 |
5
est 2013-10-10 09:10:56 +08:00
nice unicode
|
 |
6
Golevka 2013-10-10 09:22:09 +08:00
我构造出一个例子不知对不对:
L₁: {a bⁿcⁿdⁿ | n >= 1} L₂: {aⁱbⁿcⁱdⁿ | i, n >= 1}, L₁ ∩ L₂ -> abcd (context free) |
Select Language