為什麼要追求最小？
到現在為止，你幾乎能為任何正規模式建一台 DFA，而且你手上有整箱工具——乘積構造、補集、子集合建構法——個個都樂於吐出機器。麻煩在於這些機器往往臃腫。兩台 5 狀態 DFA 的乘積有 25 個狀態，即使真正的語言只需要 6 個。兩個人解同一個問題，會遞給你兩張不同的狀態圖。於是一個自然的疑問就纏上來了：在所有識別某個特定語言的 DFA 之中，存不存在一台「最好的」，而且我們找得到它嗎？
答案是一個安靜的小奇蹟。對每一個正規語言，都有且僅有一台最小的 DFA——狀態數盡可能少——而且它是唯一的，差別最多只在於替它的狀態重新命名。同一個語言的兩台正確 DFA，最小化後永遠得到一模一樣的圖。這個東西就是唯一最小 DFA。上一篇導覽已經從理論面承諾過這件事；這一篇要把真正用來計算它的演算法交到你手裡，並解釋為什麼這個結果是被「逼出來」的，而非碰運氣的選擇。
兩個狀態什麼時候才算真的相同？
最小化建立在一個尖銳的問題上：給定一台 DFA 的兩個狀態 p 與 q，把它們分開來放，到底有沒有發揮任何作用？想像你站在狀態 p、相對於站在狀態 q，然後讀完剩下的輸入。如果對「每一個」可能的後續字串，這兩個狀態最終的判決都一致——每一次都同為接受、或同為拒絕——那麼 p 與 q 做的就是一模一樣的工作。機器之後所能觀察到的任何東西，都無法把它們區分開來。這樣的一對狀態就是不可區分的，而一台仍把它們分開放的機器，正在浪費一個狀態。
反面才是我們要用的槓桿。兩個狀態是可區分的，如果存在至少一個後續字串，使兩者的結果不同——一個通往接受，另一個通往拒絕。那個見證字串，就是「p 與 q 確實扮演不同角色、必須分開」的證據。這和上一篇導覽的字串不可區分性是完全相同的概念，只是往上挪了一層：那裡我們用兩個字串的未來去比較它們；這裡我們用兩個狀態的未來去比較它們。橋樑很簡單——一個字串的未來，就是「機器讀完它之後所在那個狀態」的未來。
逐步操作的填表演算法
這裡是經典的食譜，叫做填表法、或標記與傳播演算法。它的想法是：一開始幾乎不對任何東西先入為主，然後讓「可區分性」像墨漬一樣向外暈開。一旦你能證明某一對可區分，就立刻把它標記起來，並持續標記到不再冒出新標記為止。塵埃落定後仍未被標記的，就是真正不可區分的一對，可以安全地合併。
- 先清理乾淨。移除每一個不可達的狀態（沒有任何輸入能把起始狀態驅動到它）——它影響不了語言。確認這台 DFA 是全函數的，若有某條轉移缺漏，就補上一個死亡陷阱狀態。
- 做一張表，每一對「無序的狀態對」{p, q} 各佔一格。把「恰好一個是接受狀態」的每一對都標記起來——它們因 epsilon 而可區分。其餘暫時留白。
- 現在開始傳播。對每一對仍然留白的 {p, q}，以及字母表中的每一個符號 x，看看它們去哪裡：delta(p, x) 與 delta(q, x)。若「那個目的地配對」已經被標記，那麼 {p, q} 也可區分（見證就是 x 再接上目的地的見證）——於是把 {p, q} 標記起來。
- 把整張表一遍又一遍地掃過。每一次完整的掃描，要麼至少新增一個標記、要麼一個都沒加。當某次掃描什麼都沒加時就停下——標記已經抵達不動點。
- 合併。每一對留白未標記的都是不可區分的；把彼此互不標記的狀態聚成一團團。每一團成為最小 DFA 的一個狀態，其轉移與接受身分繼承自團中任一成員（它們全都一致）。
DFA L = "strings of a,b whose length is even" (built clumsily with 4 states)
start q0 (accept, len 0)
q0 --a,b--> q1 q1 --a,b--> q2
q2 --a,b--> q3 q3 --a,b--> q0
accepting: q0, q2 (even length) non-accepting: q1, q3
TABLE (mark = distinguishable). Step 2: split accept vs non-accept.
q1 q2 q3
q0 X . X X = differ on epsilon (accept vs not)
q1 X . . = still blank
q2 X
Step 3 propagate on a (or b): is {q0,q2} distinguishable?
q0 -a-> q1 , q2 -a-> q3 . Pair {q1,q3} is blank -> no new mark yet.
is {q1,q3} distinguishable? q1 -a-> q2 , q3 -a-> q0 . {q2,q0} blank -> no mark.
Step 4: a full sweep adds NOTHING new. Fixed point reached.
Unmarked pairs: {q0,q2} and {q1,q3}. Merge:
A = {q0,q2} (accept) , B = {q1,q3} (reject)
A --a,b--> B , B --a,b--> A ==> minimal DFA has 2 states, not 4.為什麼結果是被逼出來的、而且唯一
如果這個演算法只是「碰巧」把東西變小，那會是場空洞的勝利。深刻之處在於：它產生的答案，是被語言本身「逼出來」的，而這正是上一篇導覽的 Myhill-Nerode 定理兌現的地方。那條定理說：一個語言是正規的，恰好當它的字串落入「有限多個」可區分的類別，而那些類別的數目，就是這個語言的指標。最小 DFA 的狀態，不是別的，正是那些類別。語言把類別交給你；機器沒有自由去發明更少或更多。
所以最小化與 Myhill-Nerode 是同一件事的兩種視角。定理抽象地數類別（按字串的未來行為把它們分組）；填表演算法則藉由塌縮不可區分的狀態，機械地算出同樣的類別。因為類別的「數目」是「語言」的性質，所以該語言的每一台 DFA——無論臃腫或精簡——都至少得有那麼多狀態，而最小那台恰好觸到地板。你無法低於指標；指標是狀態數的硬下界，而這也正是為什麼一個巧妙的 Myhill-Nerode 論證能證明某語言需要許多狀態、或當類別無窮多時，證明它根本不是正規的。
唯一性立刻就掉出來了。同一個語言的兩台最小 DFA，各自恰好有「指標那麼多」個狀態，而你能把它們一類對一類地配起來：在一台機器裡抵達狀態 p 的那組字串，對應到另一台裡抵達某狀態 p' 的那組，轉移與接受標記完美對齊。這個配對就是一個同構——一次忠實的重新命名。所以最小機器真的就只有一台，「那台最小 DFA」是你指得出來的東西，而不只是你盼望存在的東西。
讀懂代價，以及誠實的提醒
找出最小 DFA 要花多少代價？填表法在反覆掃描中觸碰每一對狀態，對 n 個狀態而言，代價落在 n^2 這個量級（每次掃描大約是 n^2 格，而你最多需要 n 次掃描，但配上正確的記帳，仔細的界是整體 O(n^2)）。還有一個更快、更巧妙的方法，由 Hopcroft 提出，藉由「細分分割」而非掃描配對，大約以 O(n log n) 執行。無論哪種，最小化都確實有效率——多項式時間——這和同一個問題在非確定型機器上變得多難，形成一個愉快的對比。
現在來看誠實的細則。其一，乾淨俐落仰賴「從一台 DFA 出發」：你必須先（藉子集合建構法）把一台 NFA 確定化，再去最小化，而那一步本身可能呈指數膨脹——最小化便宜，但「抵達一台 DFA」未必。其二，「最小 NFA」是個截然不同、惡劣許多的問題，沒有唯一答案，所以別假設 DFA 的故事能照搬過去。其三，跳過第 1 步會悄悄毀掉一切：忘了刪除不可達狀態，你可能會「最小化」出一台其實並非最小的機器。
還要把兩個老警告擺在眼前。最小化永遠不改變語言——狀態更少、接受的字串不變——而結果始終待在正規家族內；更小的機器並非更強大的機器。「最小」也仍然不等於「微小」：識別「倒數第 n 個符號是 1」的最小 DFA，可證需要 2^n 個狀態，因為 2^n 種可能的「最後 n 格視窗」各自就是一個不可區分類別。最小 DFA 是最小的「誠實」機器，而非什麼魔法壓縮器——而究竟哪些語言會逼出指數般多的類別，正是下一階（上下文無關語言）要接手的那類問題，做法是遞給機器一個堆疊。