gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-04 16:48:01 25 4
gpt4 key购买 nike

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

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

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

但怎么会这样呢?

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

最佳答案

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

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

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

关于regex - 证明 L ={ ww^R : w ∈ Σ*} is not regular by using Pumping Lemma,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35676659/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com