最小DFA
對於每個正則語言，都存在一個 最小自動機接受它，即一個有著最小狀態數目的DFA，且這個DFA是唯一的（除去狀態命名不同的差別）。最小DFA保證了其在模式匹配等計算套用中開銷的最小。
在不影響原始DFA所接受語言的情況下，有兩類狀態可以被移除或合併，以實現最小化過程。
•不可達狀態指DFA在任意輸入串下都無法達到的狀態。
•等價狀態指在同一輸入串下不產生區別的狀態。
DFA最小化通常要經歷三個步驟，分別對應於相關狀態的移除或合併。因為等價狀態的消解開銷高昂，通常會將其放到最後一步。
不可達狀態
確定有限狀態自動機最小化
確定有限狀態自動機最小化
確定有限狀態自動機最小化
確定有限狀態自動機最小化
確定有限狀態自動機最小化DFA 的狀態 是不可達的，若不存在 上的串 ，使得 。可達狀態可以用如下算法來找到：
將不可達狀態從DFA中移去並不會影響其接受的語言。
等價狀態
Moore算法
確定有限狀態自動機最小化
確定有限狀態自動機最小化
確定有限狀態自動機最小化
確定有限狀態自動機最小化
確定有限狀態自動機最小化 確定有限狀態自動機最小化 確定有限狀態自動機最小化
確定有限狀態自動機最小化
確定有限狀態自動機最小化Moore DFA最小化算法由Edward F. Moore(1956)給出。與 Hopcroft 算法類似地，它維護一個劃分，且這個劃分的初值為接受和拒絕狀態的劃分，並同樣反覆細化直至無法繼續細化。在每一步中，它都會用s+ 1個劃分的最粗公細化(coarsest common refinement) 來替代當前的劃分，這 個劃分中的一個是當前劃分，其他的 個則是當前劃分在轉移函式和在所有輸入符號下的原象。當這一操作無法改善當前劃分時，算法即停止。這個算法在最壞情況下的複雜度是 ：算法的每個步驟都需要 ，這是基數排序一個變種用以重排狀態的複雜度，狀態重排使得新劃分下同一集合中狀態的編號順序是接連的。又，最多會有 輪，因為除最後一輪外，每輪都使得劃分中的集合數目增加。在Moore算法下導致最壞情況的DFA最小化問題實例和Hopcroft算法是相同的。算法的輪數會比 小得多，所以平均上（ 是常數），其性能可達 甚至 ，結果取決於建模平均情況行為的自動機隨機選取分布方式。
Brzozowski算法
Brzozowski (1963) 注意到，將DFA的邊反轉將產生一個原語言反序的非確定有限狀態自動機(NFA)。再將這個NFA用標準的冪集構造法（只構造轉換後DFA的可達狀態）轉換為DFA，就會產生原語言反序的最小DFA。重複反轉操作，就可以得到原語言的最小DFA。Brzozowski算法在最壞情況下的複雜度是指數的，因為存在這樣的正則語言，其反序的最小DFA的規模是原語言DFA規模的指數大。但通常來說這個算法比最壞情況表現得要好。
NFA最小化
以上的步驟都對DFA有效，可是劃分的方法並不適用於非確定有限狀態自動機(NFA)。雖然窮舉搜尋可以最小化NFA，但並沒有一個多項式時間的算法可以完成該過程，除非P=PSPACE（計算複雜性理論中的一個未解決問題，一般認為很可能P≠PSPACE）。然而的確存在比暴力搜尋可能更加有效的NFA最小化算法。
