无法使用 Pumping Lemma 证明这种语言不是上下文无关的

Question

我试图证明语言 { w ϵ {a, b, c}* | n_a(w) < n_b(w) 和 n_a(w) < n_c(w) } 不是使用 Pumping Lemma 的 CFL。符号 "n_a" 代表 "number of 'a'".

对于泵引理，z = u(v^i)x(w^i)y, |vxw| <=米，|大众| >= 1.

我选择使用字符串 z = (a^m)b^(m+1)c^(m+1) 来表明这不是 CFL。

但是，我遇到了以下情况。

假设 'uvx' 表示 'z' 的 (a^m) 部分，'w' 表示 'z' 的 (b^m) 部分的开始，并且 'y'代表剩下的'z'.

现在抽取 i = 2，我们得到 z' = u(v^2)x(w^2)y = a^(m + |v|)b^(m + 1 + |w| )c^(m + 1).

每当|v| ≠ 0，我们看到这不是语言，因为 n_a(z') 不小于 n_c(z')。然而，对于 |v| 的情况= 0，我们得到 z' = a^(m)b^(m + 1 + |w|)c^(m + 1)，这是语言中的 IS。因此，用 i = 2 抽水是行不通的。这是正确的吗？

我尝试了 'i' 的其他值，但我仍然无法证明这种语言不是 CFL。我究竟做错了什么？这种语言实际上是上下文无关的吗？我应该使用完全不同的 'z' 字符串吗？

Answer 1

设 R 为表示以下内容的非终结符：

There are no more a than there are b or c in the final product

换句话说：

For w ϵ G(R), n_a(w) <= n_b(b) and n_a(w) <= n_c(w)

所以这个人的规则是（让 ϵ 为空字符串）：

R => ϵ

R => bR
R => Rb
R => cR
R => Rc

R => abcR
R => abRc
R => aRbc
R => Rabc

R => acbR
R => acRb
R => aRcb
R => Racb

R => bacR
R => baRc
R => bRac
R => Rbac

R => bcaR
R => bcRa
R => bRca
R => Rbca

R => cbaR
R => cbRa
R => cRba
R => Rcba

R => cabR
R => caRb
R => cRab
R => Rcab

这 29 个是所有可能的转换，保证从 R 派生的任何单词都不会超过 as 而不会超过 bs 并且不会超过 as比 cs.

但问题不是关于G(R)，而是明确说明n_a(w) <= n_b(b)和n_a(w) <= n_c(w)。所以，我还有 3 个非终端：

S,起点
B，直接或间接派生自S，并保证比a至少多b（考虑如何"isborn"）
C，直接或间接派生自S，并保证比a至少多c（考虑如何"isborn"）

我的策略如下：

Those non-terminals will all be similar to R, but they won't have any empty transformation; also, from S I'll have a transformation that will generate bB, or Bb, or cC, or Cc; from B, it is guaranteed to have at least one b more than a, then it will have a transformation to cR or Rc; and for C, transformation to bR or Rb

所以，这将是我的完整语法，从 S:

开始

S => bB
S => Bb
S => cC
S => Cc

S => bS
S => Sb
S => cS
S => Sc

S => abcS
S => abSc
S => aSbc
S => Sabc

S => acbS
S => acSb
S => aScb
S => Sacb

S => bacS
S => baSc
S => bSac
S => Sbac

S => bcaS
S => bcSa
S => bSca
S => Sbca

S => cbaS
S => cbSa
S => cSba
S => Scba

S => cabS
S => caSb
S => cSab
S => Scab

B => cS
B => Sc

B => bB
B => Bb
B => cB
B => Bc

B => abcB
B => abBc
B => aBbc
B => Babc

B => acbB
B => acBb
B => aBcb
B => Bacb

B => bacB
B => baBc
B => bBac
B => Bbac

B => bcaB
B => bcBa
B => bBca
B => Bbca

B => cbaB
B => cbBa
B => cBba
B => Bcba

B => cabB
B => caBb
B => cBab
B => Bcab

C => bR
C => Rb

C => bC
C => Cb
C => cC
C => Cc

C => abcC
C => abCc
C => aCbc
C => Cabc

C => acbC
C => acCb
C => aCcb
C => Cacb

C => bacC
C => baCc
C => bCac
C => Cbac

C => bcaC
C => bcCa
C => bCca
C => Cbca

C => cbaC
C => cbCa
C => cCba
C => Ccba

C => cabC
C => caCb
C => cCab
C => Ccab


R => ϵ

R => bR
R => Rb
R => cR
R => Rc

R => abcR
R => abRc
R => aRbc
R => Rabc

R => acbR
R => acRb
R => aRcb
R => Racb

R => bacR
R => baRc
R => bRac
R => Rbac

R => bcaR
R => bcRa
R => bRca
R => Rbca

R => cbaR
R => cbRa
R => cRba
R => Rcba

R => cabR
R => caRb
R => cRab
R => Rcab

无法使用 Pumping Lemma 证明这种语言不是上下文无关的

Unable to prove this language is not context-free using Pumping Lemma

pumping-lemma