我试图证明语言 { w ϵ {a, b, c}* | n_a(w) < n_b(w) 和 n_a(w) < n_c(w) } 不是使用 Pumping Lemma 的 CFL。符号“n_a”表示“‘a’的数量”。
对于抽取引理,z = u(v^i)x(w^i)y, |vxw| <= 米, |vw| >= 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),这在语言中是。因此,用 i = 2 抽水是行不通的。这个对吗?
我尝试使用其他值“i”,但我仍然无法证明这种语言不是 CFL。我究竟做错了什么?这种语言实际上是上下文无关的吗?我应该使用完全不同的“z”字符串吗?