pumping-lemma - 这种语言是正规的吗？{a^ib^j| i=j mod 19}

Question

我知道这{a^i b^j | i = j }不正常，我可以用抽引理证明；同样，我也可以使用抽引引理来证明这个不规则。但我想我看到了一些类似的问题，说这种语言实际上是有规律的。而且因为我对我在抽取引理方面的知识没有信心，所以我问了这个不好的问题。对不起。

这就是我证明它的方式：让 w be a^p b^(19k+p)，显然这是在语言中。然后，如果我抽一个，做它a^(p+1) b^(19k+p)。它失败。因此，它不是常规的。

我的证明对吗？

Answer 1

看看这个答案。简而言之，您没有正确地抽弦。抽水引理指出你的字符串w可以被划分为w = xyzwhere |xy| ≥ p，并且y不为空。然后，对于所有 i ≥ 0 ，您可以将字符串抽成 xy ⁱ z。

这里的关键是，抽水引理指出存在满足这些属性的字符串的划分w，您无法选择划分，并且您只能将字符串抽为 xy ⁱ z。

但是，这种语言是有规律的，所以不能用泵引理来证明一种语言是否有规律，它只能证明一种语言是否有规律（这是必要条件但不是充分条件）。为了证明一种语言是正则的，你可以构造一个 DFA、NFA 或正则表达式来准确描述你的语言。一种这样的正则表达式是：

(a^19)*(e|ab|aabb|aaabbb|...|a^18b^18)(b^19)*

e空字符串在哪里。

---

我怀疑你的语言是自动机或计算入门课程的一个例子。如果您有兴趣，Myhill-Nerode 定理通常不会在介绍材料中介绍，但在这种情况下提供了一个非常简单的规律性证明：考虑可区分的扩展 b、bb、bbb、...、b^19 和证明相对容易由此而来。