为常规语言泵送引理证明

Question

在这个问题中，你必须决定是否可以使用字符串来证明语言不规则，而不是用泵引理证明语言不规则。

我看到这个问题的答案是“不，这个字符串不能用于完成证明”字符串 a^p+1 b^p 不能使用，因为他们将语言分成 x y^i z ，其中 x = epsilon y = a 和 z = a^p b^p 所以无论 i 值是什么，我们选择的字符串仍然是语言。但这不只是一个例子吗？仍然可能有另一种方法来分割字符串，从而能够证明该语言不是规则的。 假设常规语言和泵送长度 p 我的思考过程是让 x = a ^ alpha, y = a ^ beta * i, z = a ^ (p + 1 - alpha - beta) b^p 阿尔法 + 贝塔 <= p and beta >= 1

对于这种语言，我们需要前缀 so 中 a 的数量 > b 的数量

α + β * i + p + 1 - α - β >= p

beta * i + 1 - beta >= 0 如果我们让 i = 0 并且 beta > 1 我们就会产生矛盾。那么为什么我们不能使用它呢？

Answer 1

让我们看看一种非常简单的语言

(ab)*

。

w = abab

是这种语言的，我可以将它分成三个字符串

x=a

，

y=b

，

z=ab

，并且显然

xyyyz

不是这种语言。泵引理并不是说将 w 分成三个字符串的

每一种

方式都可以“泵送”，只是必须至少有一种。

因此，他们证明了至少有一种方法可以将

w = a^(p+1)b^p

拆分为

x

、

y

和

z

来满足泵送引理。故事结局。这个例子不行。事实上，还有其他

x

、

y

、

z

不满足泵送引理并不重要。情况总是如此。