語言 a^n b^n

a^n b^n 是最著名的非正規語言——教科書裡的「礦坑金絲雀」。它是「若干個 a 後面接『相同數目』的 b」所成的字串集合：ε、ab、aabb、aaabbb，依此類推（這裡 ε 是 n ＝ 0 的情形，即空字串）。要接受它，你必須「數」看過幾個 a，再檢查 b 的數目恰好相符。這種「無上界的計數」，正是有限自動機辦不到的。

為什麼它不是正規的，一句話：DFA 的狀態數固定，所以讀完一些 a 後它只能處於有限多個狀態之一；若兩個不同的前綴 a^i 與 a^j（i ≠ j）使它停在「同一個」狀態，機器便再也分不出它們，但 a^i b^i 必須被接受、a^j b^i 必須被拒絕——單憑一個狀態辦不到。幫浦引理把這點包裝得很俐落：幫浦 w ＝ a^p b^p，a 的數目改變而 b 的數目不變，於是離開了該語言。關鍵在於：這是「關於有限記憶」的正規語言事實；a^n b^n「是」上下文無關的——下推自動機（PDA）接受它的方法是每個 a 推入一個記號、每個 b 彈出一個，僅當「輸入結束的那一刻堆疊恰好為空」才接受。

a^n b^n 是非正規性證明的主力：你透過封閉性論證把神祕語言化約到它，而它也是幫浦引理賽局中的標準目標字串。它的近親——a^n b^n c^n（連上下文無關都不是）、ww、回文、成對括號——各自頂到某個機器模型的邊界，但 a^n b^n 標示著「第一道牆」：有限狀態記憶所能應付的極限。