使用 Pumping Lemma 证明 L ={ ww^R : w ∈ Σ*} 不是正则的
Show that L ={ ww^R : w ∈ Σ*} is not regular by using Pumping Lemma
如果我让字符串 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.
原因是 m 上的标量是偶数。由于 L 中的字符串只是一个字符串的反向附加到自身，偶数个 a 将始终在 中L.
对于任何 m >= 1 你有 aa[aa...]。因此，当您的对手选择 y = aa 时，他们会强制您将 L 中的字符串注入 w(i )。不管多少次，如果有的话，你最终会得到：(aa)^k : k = pumps，这是 L[= 中的一个字符串28=]
我认为只使用a是一个糟糕的选择。拥有两个字母符号通常更容易获胜。正如这本书继续说的那样，你不能假设打败你的对手应该很容易；任何尝试都自动无效。
如果我让字符串 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.
原因是 m 上的标量是偶数。由于 L 中的字符串只是一个字符串的反向附加到自身，偶数个 a 将始终在 中L.
对于任何 m >= 1 你有 aa[aa...]。因此，当您的对手选择 y = aa 时，他们会强制您将 L 中的字符串注入 w(i )。不管多少次，如果有的话，你最终会得到：(aa)^k : k = pumps，这是 L[= 中的一个字符串28=]
我认为只使用a是一个糟糕的选择。拥有两个字母符号通常更容易获胜。正如这本书继续说的那样，你不能假设打败你的对手应该很容易；任何尝试都自动无效。