正規語言的性質、幫浦引理與最小化

幫浦引理並不充分(the pumping lemma is not sufficient)

這是關於幫浦引理「最重要的誠實警語」。它是正規性的「必要」條件——每個正規語言都滿足它——但「不是」「充分」條件。白話說:「每個正規語言都能幫浦」為真,但「每個能幫浦的語言都是正規的」則「為假」。確實存在某些「非」正規語言,卻仍然滿足整個幫浦條件,所以「通過幫浦測試」不能證明任何正面的事。

差距從何而來?幫浦引理只捕捉到有限記憶的「一個」後果——夠長的字串上存在可重複的迴圈。一個狡猾的語言可以遞給你一個「輕易就能幫浦」的結構(使迴圈條件總能被滿足),同時仍暗藏一個有限記憶無法維持的限制。標準反例是 L = { a^i b^j c^k : 若 i = 1 則 j = k }(在 {a,b,c} 上),連同所有 i 不為 1 的字串。每個長字串都能幫浦(當 i 不為 1 時在 a 區段幫浦;當 i = 1 時,可用的切法並不威脅到 j = k 的限制)——然而 L 不是正規的,Myhill-Nerode 會揭示這點。

實務上的結論是一條嚴格的使用規則:只有幫浦引理的「失敗」才能證明事情,而它證明的是非正規性。如果你試了幫浦引理,語言卻頑固地一直能幫浦,那你對「它是否正規」一無所獲——你必須改用 Myhill-Nerode,它「既必要又充分」,因此永不給出假的「通過」。同樣的單向警告也適用於上下文無關語言的幫浦引理。

L = { a^i b^j c^k : i, j, k ≥ 0 且(i ≠ 1 或 j = k)} 滿足幫浦引理(總有某個合法切法可幫浦)卻不是正規的。所以「L 能幫浦」什麼也沒告訴我們——只有 Myhill-Nerode 才能定案。

一個仍通過幫浦測試的非正規語言——逆命題不成立。

絕不要寫「該語言滿足幫浦引理,因此它是正規的」——這是邏輯錯誤。只有逆否命題(它無法幫浦,因此非正規)才有效。

又称
necessary but not sufficientthe converse fails必要但不充分逆命題不成立