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

This topic created in 4640 days ago, the information mentioned may be changed or developed.

刚刚看到：
语言 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₂ 却 *可能是* 上下文无关的呢？

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

上下文

语言

无关

10 replies • 1970-01-01 08:00:00 +08:00

laskuma

Oct 10, 2013 via iPhone

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

casparchen

Oct 10, 2013 via iPad

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

troyl

Oct 10, 2013

我想到了！
假设

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

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

L = L₁ ∩ L₂ = ∅

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

S → S

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

laskuma

Oct 10, 2013

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

est

Oct 10, 2013

nice unicode

Golevka

Oct 10, 2013

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

troyl

Oct 10, 2013

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

Golevka

Oct 10, 2013

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

Golevka

Oct 10, 2013

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

troyl

Oct 10, 2013 via iPhone

@Golevka Wow! Dragon Book!