1

我正在写一些关于 Ppumping Lemma 的东西。我知道语言 L = { a^nb^n| n ≥ 0 } 是上下文无关的。但我不明白这种语言如何满足抽引引理的条件(对于无上下文语言)?

如果我们选择字符串 s = a^pb^p, |s| > p , |vxy| < p 和 |vy| > 0。

当我们泵送它(泵升或降压)或者我缺少某些东西时,它似乎会超出语言范围。

任何解释都会有所帮助。

编辑:我将抽引引理应用于 a^nb^n 并且它无法在所有情况下都保持在语言中。那么,为什么它是无上下文的?

我只是想看看这种语言是否满足抽水引理的条件。但是当我抽水时它似乎失败了 s = uv^2xy^2z

4

2 回答 2

3

请记住,您必须允许任何满足条件的 v,x,y 选择。特别是,您可以随时选择

u=a^{n-1}, v=a, x=empty, y=b, z=b^{n-1}. 

然后 vxy 根据需要变短,但抽水只会给你

uv^kxy^kz = a^{n-1} a^k empty b^k b^{n-1} = a^{n+k-1} b^{n+k-1}, 

这仍然是语言。

于 2013-10-15T00:33:06.417 回答
0

对于那些想要外行解释的人(重申格里杰什在评论中写的内容)..

抽引引理是必要的,但还不够。

这是什么意思?

L1 = (a^n)(b^n)(c^n)

对于 L1,我们无法找到 u,v,x,y,z,这样我们就可以向上/向下抽气,而字符串仍然在 L1 中。由于 L1 不满足抽水引理,它没有通过“必要”部分,我们可以肯定地说 L1 不是上下文无关的。

但,

L2 = (a^n)(b^n)

对于 L2,有一些方法可以选择 u,v,x,y,z,这样我们就可以向上/向下抽气,并且字符串仍然在 L2 中(如果我们选择 u,v,x,y,z,它也会失败以其他一些聪明的方式)。但是由于 Pumping Lemma 是不够的,我们不能说这里的 L2 是否是上下文无关的。

TLDR:抽引理只能肯定地说“不”,不能肯定地说“是”。

于 2016-05-05T17:59:00.790 回答