抽吸引理，條件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

回答

相關問題