證明非正規性（proving non-regularity）

證明某語言「是」正規的，精神上很容易——拿出一台有限自動機或一個正規表示式即可。證明某語言「不是」正規的卻較難，因為你無法試遍無窮多台自動機並看著它們全部失敗。取而代之，你要從「每個正規語言都必須具備」的某個性質出發，並指出你的語言缺乏它。直覺始終一致：正規語言只能記住有限多的資訊，因此任何需要「無界地計數或配對」的語言都不可能是正規的。

有三件標準武器，全都利用「有限記憶」這個弱點。幫浦引理論證夠長的字串必含一個可幫浦的迴圈，再證明你的語言在幫浦下被破壞。封閉性論證把你的語言與已知是正規的零件（用交集、同態、反轉）組合，製造出與某已知非正規語言的矛盾。Myhill-Nerode 定理則拿出「無窮多個兩兩可區分」的字串——兩兩都必須被分開記住——而這是任何有限狀態機都辦不到的。Myhill-Nerode 是最完整的工具：它「恰好」在語言非正規時成功，而幫浦引理偶爾會偵測不到非正規性。

經典的非正規語言群像都帶著「無界記憶」的味道：a^n b^n（必須讓 a 與 b 的個數相符）、ww（必須記住整個前半段才能和後半段比較）、回文（必須記住整個字串才能檢查倒著讀一不一樣）、a^{n^2}（必須追蹤一個完全平方數）、以及成對的括號。每一個都失敗，因為沒有固定大小的記憶能對任意大的輸入維持那個限制。