regex - 使用抽水引理证明 L ={ ww^R : w ∈ Σ*} 不是正则的

Question

如果我让 stringw成为a^mb^m，那么我们知道这y将仅由a's 组成，因为规则|xy| <= m。

如果我设置i=0，那么左侧的 'sww^R会a比右侧的少。因此，它证明了这种语言是不规则的。

但是，我的教科书（林茨的《形式语言和自动机简介》第 118 页）说，如果我选择w = a^2m并让y = aa，那么我会失败。

但怎么会呢？

在我看来，无论x, y,z是什么，第一个会比第二个a^2m拥有更少a或更多的 's 。ia^2m

Answer 1

原因是你在m上有一个偶数标量。由于L中的字符串只是一个字符串的反向附加到自身，偶数个a将始终在L中。

对于任何m >= 1，您都有aa[aa...]。因此，当您的对手选择y = aa时，他们会强迫您将L中的字符串注入w(i)。无论多少次，如果有的话，它最终会被抽出：(aa)^k : k = pump，它是L中的一个字符串

我认为只使用. 拥有两个字母符号通常更容易获胜。正如这本书继续说的那样，你不能认为击败对手应该很容易。任何尝试都会自动失效。