用上下文无关语言抽取引理

我先选一个稍好的z=a^(m+2)b^(m+1)c^(m),其中m是泵送长度。这个字符串在语言中很明显,它的长度大于或等于m。因此,假设语言是CFL,泵引理适用于它。既然你知道| vwx | lt;=m和| vx | gt;0,你也知道vwx必须由(1)只有a的,(2)一些a和一些b的,(3)只有b的,(4)一些b和一些c的,或者(5)只有c的。

分别处理每一个案件。我帮你做前两个案子。

案例1:这意味着vx是一些s>0的一个^(s),因为引理告诉我们| vx |>0。现在假设你取i=0。然后引理告诉我们z'=uv^(0)wx^(0)y应该仍然属于该语言。但是,z'的形式是a^(m+2-s)b^(m+1)c^(m),并且,由于s>0违反了a的数量必须严格大于b的条件。因此,z'不在语言中,并且这种情况下无法泵出。

案例2:这意味着vx对于某些s,t是a^(s)b^(t),因此s+t>0。假设,同样,你取i=0。那么z'的形式是a^(m+2-s)b^(m+1-t)c^(m)。如果t为正,则违反b的个数严格大于c的个数的条件。如果t为零,s必须为正,在这种情况下,我们退化为情况1。因此z'不在语言中,这个例子无法泵出。

在处理其他情况时,请记住,可以为每个情况选择不同的泵送指数i。

编辑:

案例3:这意味着vx对于某些s>0是b^(s)。取i=0。那么z'的形式是a^(m+2)b^(m+1-s)c^(m)。因为s是正的,这违反了b的个数严格大于c的个数的条件,所以z'不在语言中,这个例子不能泵出。(你也可以把i取为除1以外的任何值,以表明这个案例无法泵出。)

案例4:这意味着对于某些s,t,vx是b^(s)c^(t),因此s+t>0。取i=2。那么z'的形式是a^(m+2)b^(m+1+s)c^(m+t)。如果s不为零,则违反a的个数严格大于b的条件。如果s为零,则t必须为非零,在这种情况下,违反了b的个数严格大于c的条件。所以z'不在语言中,这个例子也不能泵出。

案例5:这意味着vx对于某些s>0是c^(s)。取i=2。那么z'的形式是a^(m+2)b^(m+1)c^(m+s)。因为s是正的,所以违反了b的个数严格大于c的条件。所以z'不在语言中,这个例子不能泵出。

由于这五种情况都无法泵出,泵出引理告诉我们,这种语言不是上下文无关的。

注意 而威廉的回答实际上是正确的。我把这个答案留在这里好让我 指出我的推理路线失败的地方。

子串v,w,x必须有哪些属性才能有机会保持 像“ab”或“bc”,否则它们会立即从输入语言中抽取出来。所以

考虑语言中的字符串aaabbc。

如果我们选择u=”a a”,v=”a”,w=epsilon,x=”b”,y=”bc”;然后 泵v和泵x?( 这是我的错误: 我没有考虑n=0的情况,其中v和x是 实际上从字符串中移除;无论您如何选择uvwxy,证明都将 当uvwxy被泵送到uv时,n=0或n>1情况下均失败 宽x ^n个 y) 是的。

:CFL泵引理可用于证明语言不是上下文无关的, 不 足以证明一种语言 上下文无关。有些语言不是CF,而是 CFL泵引理仍然成立。对于这种情况,您可能需要查看 Ogden's lemma ,有点 更强大的测试,看看是否可以用来表明你的语言不是CF。

泵引理说,如果一种语言是上下文无关的,那么它“泵”。也就是说,如果是上下文无关的,那么:

s=uvxyz,其中u和y项可以在原地重复任意次数(包括零次)。

一个典型的用法是证明一种语言没有泵,以证明它不是上下文无关的。从你的工作看来,这就是你要做的。

Ogden's lemma 相反。