2

令 B 为语言 {0 n 1 n | n >= 0} 即 0 和 1 必须具有相同的长度

令 B 中的 s 为字符串 0 p 1 p

假设 B 是正则的,所以 s 必须能被 s = xyz 整除,其中 xy i z i>=0 仍在 B 中(泵引理的三个条件的条件 1)。

考虑 xy i z 的情况,其中 i = 2 所以 xyyz:泵 y 全为 0
xyyz 有更多的 0 和 1,因此它不能在 B 中。因此,B 不是规则的。

我很难理解如果 y 在 xyyz 中全为 0,那么 # of 0s > # of 1s

为什么不能|xyy| = |z| 那么它将具有相同的 0 和 1 数?

4

1 回答 1

2

'Pump y with all 0s' 不是很清楚,但如何解决的一个例子如下:

Pick some value for y: let's say y = '0'.
Pick some value for i: i = 1
Then s = xyz.  We will assume this holds true for the moment.

现在,由于我们假设 B 是正则的,我们知道 - 对于任何 i 值 - 由 xy i z 形成的字符串也应该在 B 中!让我们试试 xyyz,就像你建议的那样。

……哦哦。你看到问题了吗?我们必须保持 y 不变,但这样做意味着我们只是创建了一个字符串,它的 0 比 s 多一个,但没有额外的 1 !我们刚刚证明 y 不能为 0。好吧,该死。

现在考虑:是否存在任何不适用的 y 值?将 0 添加到 y 只会使问题变得更糟!

这是一个非常非正式的证明演练,但希望它有助于理解它为什么起作用。

于 2012-10-19T01:35:00.357 回答