抽吸引理，条件1

让B为语言{0 ^{n n} | N> = 0}，即0和1必须具有相同的长度抽吸引理，条件1

令S B中是字符串0 ^{p p}

假设B是定期所以s必须是整除为s = xyz其中xy ⁱ zi> = 0仍然处于B（抽水引理的三个条件的条件1）中。

考虑的情况下的xy ^我 z，其中I = 2，从而xyyz：用全0
xyyz具有更多的0和1泵ÿ所以它不能在B.因此，B不是正则的。

我有一个很难理解，如果y是xyyz全部为0，那么0的＃>的1S

为什么不能＃| XYY | = | z |那么它会有相同的0和1的数字？

来源

2012-10-19 antz

这可能发生在理论CS中。 –

“泵y随全0”并不十分清楚，但如何工作了一个例子如下：

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是规律的，我们知道 - 为我的任何值 - 由xy ⁱ z组成的字符串也应该在B！让我们尝试xyyz，就像你所建议的那样。

......嗯。你看到问题了吗？我们必须保持y不变，但这样做意味着我们只是创建了一个比s多一个0的字符串，但没有额外的一个字符来支持它！我们只是表明y不能是0.那么，该死。

现在考虑：是否有任何价值的y这不会成立？给y添加0只会使问题变得更糟！

这是非常非正式的证明演练，但希望它有助于理解它为什么有效。

来源

2012-10-19 01:35:00

因此，举个例子，假设x ='0'和y ='0'，那么在xyyz，xyy ='000'为什么不能z是'111'（这意味着它们是相同的）？变量x，y，z不必长度为1. – antz

正确。但是你只显示了我的一个值。如果对于i> = 0的所有值使用xy^iz语言，则只选择x，y和z'适合'该语言。 –

抽吸引理，条件1

回答

相关问题