DFA 最小化（DFA minimization）
DFA 最小化是一道清理程序，把有限自動機壓縮到「在不改變所接受語言的前提下」狀態數最少。想像你草草畫了一台機器，結果出現幾個「行為完全相同」的重複房間——最小化會找出這些冗餘房間並合併它們。結果辨識「完全相同」的語言，沒有任何浪費的狀態。
標準演算法是「分割細化」（partition refinement），又稱「填表法」。首先丟掉任何無法到達的狀態（沒有輸入能抵達它們）。再從一個粗略的猜測開始：兩組，接受狀態與非接受狀態，因為這兩者明顯能由「空續接」區分。接著反覆「細化」：同一組中的兩個狀態，若對某個符號 a，它們的轉移 δ（delta）通往「不同的」當前組別，就把它們拆開——那個符號暴露了它們未來的差異。持續拆分，直到沒有任何組可再拆。最終的各組就是「不可區分」類；每一類成為最小 DFA 的一個狀態，轉移從任一成員繼承而來。填表法的變體則「標記」出所有可區分的狀態對，向後傳播標記直到穩定。
為什麼要這麼做？最小 DFA 是最省的實作（需儲存的狀態最少、最易推理），也是用來「檢驗兩台 DFA 是否接受相同語言」的典範形式——把兩台都最小化再比較即可。演算法找到的那些類，正是 Myhill-Nerode 等價類，這也是為何此程序「可證明」會抵達真正的最小值，而非只是一台較小的機器。
從 {接受狀態} 對 {非接受狀態} 開始。若兩個非接受狀態 p、q 在讀「a」時都到接受狀態、讀「b」時都到非接受狀態，它們留在同一組。但若 p 在「a」到接受狀態、而 q 到非接受狀態，就拆開它們——符號「a」區分了它們。重複到穩定為止；把每個最終組別合併成一個狀態。
藉由拆開「轉移通往不同組別」的狀態來細化分割。
細化「之前」先移除「無法到達」的狀態，否則可能多報語言根本不會造訪的狀態。最小化只對 DFA 有定義；NFA 須先確定化，而填表演算法在多項式時間內完成（Hopcroft 的版本為 O(n log n)）。