用上下文自由语言抽取引理

Question

我有一种语言,{a^i b^j c^k | i,j,k>=0 & i>j & j>k} 我开始假设有一些m是为我挑选的,这样就是一个字符串

   z = a^m b^(m-1) c^(m-2)

然后,将字符串分成(z =) uvwxy,这样vx是不是空的,#(vwx)<=m 然后,当我来挑一个" i"我感到困惑.说我选择i=1然后我有: uv^1wx^1y而且我不完全确定从哪里开始因为对我来说看起来我可以选择一种语言中的vwx.

有什么建议？

Answer 1

我首先选择稍好的z = a ^(m + 2)b ^(m + 1)c ^(m),其中m是泵送长度.该字符串显然在语言中,其长度大于或等于m.因此,假设语言是CFL,则泵浦引理适用于它.现在,因为你知道| vwx | <= m和那| vx | > 0,你也知道vwx必须包括(1)只有一个,(2)一些和一些b,(3)只有b,(4)一些b和一些c,或(5)只有c.

单独处理每个案例.我会为你做前两个案例.

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

情况2:这意味着对于某些s,t,vx是^(s)b ^(t),使得s + t> 0.假设,再次,你取i = 0.那么z'的形式为a ^ (M + 2-S)b ^(M + 1-t)的C 1-4(米).如果t为正,则违反b的数量严格大于c的数量的条件.如果t为零,则s必须为正,在这种情况下,我们退化为情况1.因此,z'不在语言中,并且这种情况无法抽取.

对于处理其他情况,请记住,您可以为每个情况选择不同的抽水指数.

编辑:(从过去关于这个问题的讨论,我决定展示其他三个案例.)

情况3:这意味着对于某些s> 0,vx是b ^(s).取i = 0.然后z'的形式为a ^(m + 2)b ^(m + 1-s)c ^(米).由于s是正的,这违反了b的数量严格大于c的数量的条件.所以z'不在语言中,这种情况不能用.(你也可以把我等于除了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:这意味着对于某些s> 0,vx是c ^(s).取i = 2.然后z'的形式为a ^(m + 2)b ^(m + 1)c ^(m + S).由于s是正的,因此违反了b的数量严格大于c的数量的条件.所以z'不在语言中,这种情况不能用.

由于所有五种情况都无法泵送,因此泵送引理告诉我们这种语言不是无上下文的.