0

证明 a^nb^n, n >= 0, 是非常规的。使用字符串 a^pb^p。

我见过的每个示例都声称 y 可以包含 a、b 或两者。但是我看不出 y 怎么能包含除 a 之外的任何东西，因为如果 y 包含任何 b，那么 xy 的长度必须大于 p，这使得它无效。

相反，例如：

www, w 是 {a, b}*，使用的字符串是 a^pba^pba^p b。在我看到的证明中，它声称 y 不能包含除 a 之外的任何东西，原因我在上面说。为什么这不一样？

还抛出另一个问题：

描述以下“证明”中的错误，即 0* 1* 不是常规语言。（必须存在错误，因为 0* 1* 是常规的。）证明是矛盾的。假设 0* 1* 是规则的。令 p 为 0* 1* 的泵送长度，由泵送引理给出。选择s为字符串OP P。你知道s是0*1*的成员，但是a^pb^p不能抽。这样你就有矛盾了。所以 0* 1* 是不规则的。

我找不到这个证明有什么问题。我只知道 0*1* 是正则语言，因为我可以构造一个 DFA。

4

1 回答 1

0

抽水引理指出，对于常规语言L：

对于所有大于p的字符串s存在一个细分s=xyz使得：

  1. 对于所有i，xy i z在L中；
  2. |y|>0 ; 和
  3. |xy|<p .

现在声称y只能包含a或b的说法源于第一项。因为如果它同时包含a和b，并且i=2，这将导致aa...abb...baa...b等形式的字符串。这就是语句想要说的.

第三部分确实很明显y只能包含a。也就是说，教科书上说的是从第一项得出的结论。

最后，如果将 1.、2. 和 3. 结合起来，就会产生矛盾，因为我们知道y必须至少包含一个字符 (2.)，所以字符串只能包含一个's。假设y包含k a。如果我们用i=2 “泵送”这个，结果是我们生成了一个字符串：

s'=xy 2 z=a p+k b p

然而，我们知道s' 不是 L 的一部分，它应该是 1.，所以我们达到了不一致。

因此，您只能通过结合这三个项目来进行证明工作。仅知道y仅由a组成是不够的：这不会导致矛盾。这是因为没有可用的细分同时满足所有三个约束。

关于你的第二个问题。在这种情况下，L看起来不同。您不能重用a^nb^n的证明， 因为如果字符串包含更多a 's ， L会非常高兴。换句话说，你找不到矛盾。换句话说，证明的最后一项失败了。只要y只包含一种类型的字符——不管它的长度如何——它就可以满足所有三个约束。

于 2015-02-23T11:22:15.877 回答