代码之家 › 专栏 › 技术社区 › Neal

CFLs的泵引理

pumping-lemma context-free-grammar computer-science

3

Neal · 技术社区 · 17 年前

我的问题是:

设L={a,b}中的{x*| x有相等数量的a和b}

我知道这是一种上下文无关的语言,因为我可以为它创建语法(e是epsilon):

S -> aX | bY | e

X -> bS | aXX

Y -> aS | bYY

您还可以通过使用与常规语言相交的上下文无关语言是上下文无关的这一事实来证明它是上下文无关的。

由于它是一种上下文无关语言,根据CFL的泵送引理,任何超过泵送长度p的字符串都应该能够被泵送。但是,如果我选择字符串s=a^p b^p a^p b^p,则无法抽取该字符串,因此该语言不应与上下文无关。

我哪里做错了?

2 回复 | 直到 7 年前

1

4

sepp2k 17 年前

确定绳子可以抽。允许 u = a^p b^(p-1), v = b, x = e, y = a, z=a^(p-1) b^p uvxyz = s 不管怎样,我 u v^i x y^i z

2

1

Jim Lewis 17 年前

让u=a^p,v=b^(p-1),x=ba,y=a^(p-1),z=b^p,这样字符串s=uvxyz。

那么任何形式为u v^i x y^i z的字符串都在语言中,因此满足CFL泵引理的条件。

编辑: sepp2k正确地指出,我选择的vxy违反了| vxy |<=p、语言的泵送长度。他的解v=b,x=e,y=a是正确的。对于这种语言,任何长度为2或更大的字符串都将泵送--“ab”或“ba”必须出现在某个地方,因此vy=ab或vy=ba将始终有效。