regex - 证明 L ={ ww^R : w ∈ Σ*} is not regular by using Pumping Lemma

Question

如果我让字符串 w是a^mb^m然后我们知道 y将仅包含 a是因为规则 |xy| <= m .

如果我设置 i=0 , 然后 ww^R a 会更少在左边比在右边。从而证明这种语言不是正则的。

但是，我的教科书(形式语言和自动机简介 第 118 页，林茨着)说如果我要选择 w = a^2m让y = aa ，那我就失败了。

但怎么会这样呢？

在我看来，无论如何x , y , z是，第一个a^2m a 会更少的或更多取决于什么 i比第二个a^2m .

Answer 1

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

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

我认为只使用 a 是一个糟糕的选择。拥有两个字母符号通常更容易获胜。正如这本书继续说的那样，你不能假设打败你的对手应该很容易；任何尝试都自动无效。