一句話解釋泵引理如何找矛盾:調整y重複的次數,選擇泵入或泵出,使得w變得不屬於RL,發生矛盾,證明原本suppose L=RL是錯的,我們必須接受L不是Regular。
白話文解釋證明步驟:
先找一個字串w其長度需大於等於L的狀態數N,
同時此字串w的內容要精心設計,必須將w字串的子字串xy的長度鎖在N之中,最好是讓xy鎖在相同的字符裡,這樣才方便讓y重複k次,導致矛盾產生(通常題目的L: 字符ab的長度有相關,設法讓y重複k次,使得ab長度關係被打破)
最後調整y重複的次數,選擇泵入或泵出,使得w變得不屬於RL,發生矛盾,證明原本suppose L=RL是錯的,我們必須接受L不是Regular。