把封閉性當作證明工具(closure as a proof tool)
封閉性不只用來搭建辨識器——它也是一種間接「證明」某語言「不是」正規的方法,完全不必動用幫浦引理。訣竅是一種邏輯柔道:先假設你懷疑的語言是正規的,再用「保持正規性」的運算(交集、補集、同態、反轉、差集)把它和「已知是正規」的材料組合起來。如果這個合法的組合落到一個你「早已知道不是正規」的語言上,你就得到矛盾——於是那個懷疑對象一開始就不是正規的。
食譜如下。為了反證,假設 L 是正規語言。挑一個你能輕易寫下的正規語言 R。由於正規語言對交集封閉,L ∩ R 也會是正規的。現在選 R,使得 L ∩ R 等於某個著名的非正規語言——最常用的是 a^n b^n。但 a^n b^n 不是正規語言,所以 L ∩ R 不可能是正規的,這與封閉性的結論相衝突。我們唯一做的假設是「L 是正規的」,所以這個假設為假。
這種手法常比幫浦引理更乾淨,因為它把困難的部分外包給一個你已信任其地位的、典範的非正規語言。它也能推廣:對同態、反同態與反轉的封閉性各提供不同切入角,所以某個抵擋得住某種封閉性論證的語言,可能敗在另一種之下。代價是你必須「知道」某個基礎的非正規語言,並找到對的正規搭檔來組合。
主張:在 {a,b} 上 a 與 b 個數相等的字串所成的語言 L 不是正規的。假設它是。把它與正規語言 a* b*(先全部是 a、再全部是 b)取交集。結果恰好是 { a^n b^n : n ≥ 0 },而這不是正規的——矛盾。所以 L 不是正規的。
把懷疑對象和一個正規語言組合,逼出一個已知的非正規語言。
這只能證明「非」正規性,永遠不能證明正規性——對某運算封閉,無法保證某個給定語言是正規的。而且矛盾的牢固程度只取決於你的基礎事實(例如 a^n b^n 非正規),那本身又須用幫浦引理或 Myhill-Nerode 來證明。