regular-language - 这是使用泵引理的正确方法吗？

Question

我一直在 YouTube 上观看 Coderisland 的关于有限状态机、DFA 和 NFA 的讲座，在一次讨论中，他谈到了如何使用泵引理来展示一种语言如何不规则。我不太知道如何应用引理，并且想了解我是否做得正确。如果我有类似的东西:

w = {aⁿb^k, n =/= k}

我可以这样说吗:

h = {aⁿb^{n + r}, r > 0} 是 w 的子集，因此，如果我通过引理表明 h 不规则，则 w 一定不规则，因为 h 是 h 的子集>w.

我的展示方式如下:

1. h = xyz
2. |xy| <=n
3. x = a^n-r
4. y = a^r
5. z = b^{n + r}
6. xyz = a^n-ra^rb^{n + r}
7. xy²z = a^n-ra^2rb^{n + r} = a^{n + r}b^{n + r}

因此 h 不能是正则，因为 a^{n + r}b^{n + r} 的形式不是 {aⁿb^{n + r}, r > 0}，并且由于 h 不是正则 w 也一定不是正则，因为 h 是 w 的元素。

我应用得正确吗？我了解如何将其应用于像 {aⁿbⁿ} 这样的简单语言，因为我可以将引理直接应用于这种语言，但我能想到的唯一方法对于我的语言来说，就是创建一个属于我的语言的子集，并将引理应用于该子集。

如果我没有正确应用它，有没有办法使用另一个引理，或者可能使用闭包属性来表明我的语言不是常规的(或常规的)？

这是一个非常棒的主题，即使我不完全理解泵引理，我也很高兴能进一步探索它!

Answer 1

你的证明中有两个错误。

首先，您的这段话有错误的是:

if I show by the lemma that h is not regular, that w must not be regular since h is a subset of w.

因为考虑语言L = {aⁿb^m | n,m 自然数} h 是 L 的子集，但显然 L 是正则的，因为它可以用正则表达式 a*b* 表示。

但是您已经非常接近解决方案，实际上您不需要考虑 h。相反，您应该选择 w 中的一个字符串，这样无论您如何对其应用泵引理，您总是会得到一个不在 w 中的字符串.

现在这是你在抽水引理步骤 3 中的第二个错误。在泵引理中，我们要证明“该语言存在一个元素，因此无论您如何将泵引理应用于该字符串，您总是会得到一个在该语言之外的字符串”。

在你的证明中，你故意选择 x = a^n-r，而没有解释为什么一定是这样。例如，实际上可能存在 x = a^n-2 的情况。在这种情况下，幸运的是，您仍然有相同的结论，即它不满足泵引理(因此它不是正则的)，因为通过考虑 xy^r+1z，您肯定会拥有比 b 更多的 a .

---

证明问题的一种正确方法是直接对其应用泵引理(还有其他方法，例如使用补集，或将其与正则语言相交并证明交集不规则)，但为了解释泵引理，我将向您展示如何将泵引理应用于这种语言。

因此，问题表明我们有 w = {aⁿb^k, n=/=k} 并且我们要证明它不是正则。

1. 现在考虑字符串 s = aⁿb^n!+n (即，n 个 a 后跟 n 个阶乘加上 n 个 b )。通过抽引理，如果 w 是正则的，则应该存在 xyz 使得 s = xyz，并且 |xy|<=n。

2. 由于 |xy|<=n 并且我们在 s 的开头有一个ⁿ，因此 x 和 y 必须只包含 a。设 y = a^m。我们知道 1<=m<=n。

3. 现在我们得到 a 和 b 的数量之差为 (n!+n)-n = n!。该数字可以被 1 到 n(含)范围内的任何数字整除。所以我们有 n!/m 是一个整数。设 q = n!/m。

4. 考虑字符串 xy^q+1z，我们得到 a 的数量为 (n-m)+(q+1)*m = n-m+qm+m = n +qm = n+n!，与 b 的数量相同。因此 xy^q+1z 不属于 w 语言，因为 a 的数量与 b 的数量相同。因此，语言w不满足泵引理。

5. 因此 w 不是正则。

---

要解决评论中的问题，请使用补语进行证明。

1. 假设w是正则的。那么补码w'也应该是正则的。

2. 但是补码 w' = {aⁿbⁿ, n 自然数} 不规则(你证明了已经，对吧？)。

3. 因此 w 不是正则。