string - 为什么为 CFG 抽引理不起作用

Question

语言：

{(a^i)(b^j)(c^k)(d^l) : i = 0 or j = k = l}

我们拿话

w = a^0 b^n c^n d^n

这显然属于语言，因为 j = k = l

w = uvxyz

1. |vxy| <= n

2. |维| > 1

现在 v 和 y 可以是：

1. 只是一个字符，如果我们抽出单个字符，这个词就不再是语言

2. 两个字符，第三个字符的数量会更少，所以这个词不在语言中

所以，这种语言不是 CF 的证明不应该用标准的泵引理来做，只是用 ogdens 引理，但我不明白为什么上面的证明是无效的。

Answer 1

它不起作用，因为实际上每个抽出的字符串都在该语言中，因为您仍然没有as（即 i=0）。

如果你选择一个 i > 0 的字符串，那么你就不能保证v不只是一些as，而x是空字符串。