為什麼先準備一套數學工具
在上一個階段，你已經見過這整門學科的原料：字母表 Σ（Sigma，就是一個有限的符號集合）、由它組成的字串，以及作為字串集合的語言。注意，這些詞幾乎每一個裡面都藏著「集合」二字。集合不過是一堆彼此相異、沒有特定順序的東西的聚集——例如字母集合 {a, b}，或某字母表上所有字串的集合。在我們能建造辨識語言的機器之前，得先能自在地處理這些機器其實正是由它們構成的集合、關係與函數。
把這篇導覽想成出發健行前打包背包。這些概念單獨來看都不難，但稍後你會運行一台確定型有限自動機，它的整個定義就是一個從（狀態、符號）配對映到狀態的 函數；你會用一個 等價關係證明兩個字串「在機器看來毫無分別」；而且你會用一個耀眼的論證發現：有些語言根本沒有任何機器能辨識。這每一個時刻，都正好依靠下面這些工具。
集合、其運算，與笛卡兒積
我們用幾個日常的運算來組合集合。聯集 A ∪ B 蒐集兩集合中任一者裡的所有東西；交集 A ∩ B 只留下同時屬於兩者的；差集 A − B 留下屬於 A 但不屬於 B 的；而補集則是（在某個約定的全集裡）所有不屬於 A 的東西。這些並非抽象的裝飾：稍後「正規語言對聯集與補集封閉」這件事，正是讓你能用兩台機器拼出一台機器的關鍵，所以現在就把這些運算練到熟，日後直接受用。
還有兩個集合概念會不斷出現。A 的冪集是 A 所有子集所構成的集合；若 A 有 n 個元素，其冪集就有 2^n 個元素——記住這個數，因為它正是「把一台 n 狀態的非確定型自動機轉成確定型時，可能產生多達 2^n 個狀態」的原因。另一個是笛卡兒積 A × B：所有 (a, b) 有序對所成的集合，其中 a 取自 A、b 取自 B。一條像 delta(q, a) = p 的轉移，其實只是替取自 狀態集 × Σ 的配對 (q, a) 讀出一個值，所以笛卡兒積正是你日後寫下的每一條轉移的天然歸宿。
關係：那個你不能略過的等價關係
集合 A 上的關係，不過是 A × A 的某個選定子集——一份「哪些配對算是有關聯」的清單。數字上「x 小於 y」，或「字串 x 是字串 y 的前綴」，都是日常的例子。多數關係沒有特別結構，但有一種特別的——等價關係——值得整整一篇導覽，因為它捕捉了「在某方面相同」的想法。當一個關係 ~ 同時是自反的（每個 x ~ x）、對稱的（若 x ~ y 則 y ~ x）、且遞移的（若 x ~ y 且 y ~ z 則 x ~ z）時，它就是一個等價關係。
魔法在這裡。A 上的任何等價關係，都會自動把 A 切成互不重疊的小堆，稱為等價類——每一堆恰好裝著彼此等價的元素，而所有堆合起來無重疊地蓋滿整個 A。這種乾淨的切分稱為劃分。想像把一堆襪子「按顏色」分類：每隻襪子恰好落入一個顏色堆，沒有襪子同時在兩堆，也沒有空堆。顏色堆就是等價類；「同色」就是那個等價關係。
為何如此看重？因為關於正規語言最深刻的定理——你再爬幾階就會遇到的 Myhill–Nerode 定理——正是這樣運作的：當沒有任何後續能把兩個字串區分開時，就宣告它們等價，然後數出所得的類別。每一個類別就成為「最小可能機器」的一個狀態。等價類字面意義上就是一個狀態的種子，所以你現在花在這個概念上的時間，日後會以數倍奉還。
函數、圖與樹
一個從 A 到 B 的函數 f，替 A 中每個輸入指派 B 中恰好一個輸出——沒有輸入被晾著，也沒有輸入拿到兩個答案。確定型自動機的轉移函數正是如此：餵給它一個（狀態、符號）配對，它就交還恰好一個下一狀態，delta(q, a) = p。這個「恰好一個」正是確定型的全部意涵。三個形容詞能讓圖像更銳利：若不同輸入永不碰撞到同一輸出，函數就是單射的（一對一）；若每個可能的輸出都真的被命中，就是滿射的（蓋滿）；若兩者皆是，就是雙射的，意思是輸入與輸出完美配對。我們很快會大力倚賴雙射，因為雙射正是判定兩集合「同樣大小」的黃金標準。
你日後要畫的圖示，多半是圖與樹。圖是一組以邊相連的節點；自動機的狀態圖正是一個圖，其節點為狀態、其帶標籤的箭頭為轉移。樹是一種特別的圖，只有單一根節點且沒有環，因此每個節點回到根都恰有一條路徑。剖析樹——展示文法如何生成字串的圖——正是這個精確意義下的樹，而非確定型機器那種分岔的計算也是，其中每條分支都是一次「猜測」。認得這兩種形狀，會讓日後的圖示感覺熟悉而非陌生。
States = {even, odd} (count of a's so far, mod 2)
start = even, accept = {even}
delta | a | b
------+-------+------
even | odd | even
odd | even | odd
run on "abba": even --a--> odd --b--> odd --b--> odd --a--> even ACCEPT可數與不可數——以及為何有些語言遙不可及
現在來談那個讓整門學科成為可能的想法。若兩集合之間存在一個雙射——一種兩邊都不剩餘的完美配對——它們就有相同的大小。若一個集合能與計數數 1, 2, 3, … 配對，使每個元素終究都拿到一個號碼，它就是可數的。引人注目的是：任何字母表上所有字串的集合都是可數的——把它們由短到長排列、同長者按字母序排，每個字串都會出現在某個有限位置。所有程式（或所有自動機）的集合也基於同樣理由可數——每一個都不過是一串有限的符號。
但到底有多少語言呢？一個語言是字串的集合——是「所有字串」這個可數集合的子集——所以「所有語言」的全體，就是一個可數集合的冪集。Georg Cantor 用他著名的對角線論證證明這個冪集是不可數的：嚴格大於計數數，因此沒有任何清單能裝下它們全部。重點來了，把你已握有的兩個事實對齊：機器只有可數那麼多，語言卻有不可數那麼多。較小的集合無法與嚴格較大的集合一一配對，所以大多數語言根本沒有機器。有些語言就是沒有任何電腦能辨識——不是因為我們不夠聰明，而是字面上已經沒有任何東西可以分派給它們了。
- 為了導出矛盾，假設你能把 Σ 上所有語言列成 L1, L2, L3, …，並同時把字串本身列成 s1, s2, s3, …
- 用一條在對角線上與清單作對的規則，造出一個全新語言 D：當且僅當 si 不屬於 Li 時，把字串 si 放進 D。
- 如今 D 不可能等於清單上任何一個 Lk——它是被刻意造成「在單一字串 sk 上與 Lk 不同」的（sk 的成員資格被翻轉了）。
- 於是 D 是一個被清單漏掉的真實語言：清單原來並不完整，而且沒有任何清單能完整。語言是不可數的，因此超出可數那麼多的機器所能觸及的範圍。
要小心這論證說了什麼、又沒說什麼。它並未指名某個具體的不可辨識語言，也不意味電腦很弱——它純粹是一個關於大小的計數事實。同樣這套對角線手法，若瞄準的是機器而非任意清單，正是日後證明停機問題不可判定的關鍵。現在把這個小動作學透，意味著那個著名結論屆時會比較不像魔術、比較像老朋友。