2

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

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

我是否正确，我可以这样说：

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

我要展示的方式如下：

  1. h = xyz
  2. |xy| <= n
  3. x = n-r
  4. y = a r
  5. z = b n + r
  6. xyz = a n-r a r b n + r
  7. xy 2 z = a n-r a 2r b n + r = a n + r b n + r

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

我是否正确应用了它？我了解如何将它应用于像 {an b n }这样的简单语言，因为我可以将引理直接应用于这种语言，但我能想到的语言的唯一方法是创建一个属于我的语言的子集, 并将引理应用于此。

如果我没有正确应用它，有没有办法表明我的语言不规则（或规则），使用另一个引理，或者可能具有闭包属性？

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

4

1 回答 1

1

你的证明有两个错误。

首先，您的此陈述中的错误是：

如果我通过引理表明h不是正则的，那么w一定不是正则的，因为h是w的子集。

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

但是您非常接近解决方案，实际上您不需要考虑h。您应该改为在w中选择一个字符串，这样无论您如何将 Pumping Lemma 应用于它，您总是会得到一个不在w中的字符串。

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

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

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

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

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

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

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

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

  5. 因此w不是正则的。

要解决您评论中的问题，请使用补码证明。

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

  2. 但是补码w' = {a n b n , n natural number} 是不规则的（你已经证明了，对吧？）。

  3. 因此w不是正则的。

于 2014-01-26T11:41:13.293 回答