最小有限自動(dòng)機(jī)，是指滿足下述條件的確定有限自動(dòng)機(jī)
⑴ 沒(méi)有無(wú)用狀態(tài)(無(wú)用狀態(tài)已刪除)；⑵ 沒(méi)有等價(jià)狀態(tài)(等價(jià)狀態(tài)已合并)。
Ⅰ.刪除無(wú)用狀態(tài)算法
【定義】無(wú)用狀態(tài)是指自動(dòng)機(jī)從開始態(tài)出發(fā)，對(duì)任何符號(hào)串都不能到達(dá)的狀態(tài)。
【判別算法】 構(gòu)造有用狀態(tài)集 Qus
⑴ 設(shè) q0 為開始態(tài)，則 令 q0∈Qus ；
⑵ 若 qi∈Qus 且有 d(qi,a)= qj 則令 qj∈Qus ；
⑶ 重復(fù)執(zhí)行⑵，直到Qus不再增大為止。
⑷ 從狀態(tài)集Q中，刪除不在Qus中的所有狀態(tài)。
Ⅱ. 合并等價(jià)狀態(tài)算法
【原理】?jī)蓚€(gè)狀態(tài)i,j等價(jià)，當(dāng)且僅當(dāng)滿足下面兩個(gè)條件：
① 必須同是結(jié)束態(tài)，或同不是結(jié)束態(tài)；
② 對(duì)所有字母表上符號(hào)，狀態(tài)i,j必變換到等價(jià)狀態(tài)。
Ⅱ. 合并等價(jià)狀態(tài)算法
劃分不等價(jià)狀態(tài)集
⑴ 初始，把狀態(tài)集Q化分成兩個(gè)不等價(jià)子集:
Q1(結(jié)束狀態(tài)集)， Q2(非結(jié)束狀態(tài)集)；
⑵ 把每個(gè)Qi再劃分成不同的子集，條件是：
對(duì)同一Qi中兩個(gè)狀態(tài)i和j，若對(duì)字母表中的某個(gè)符號(hào)，變換到已劃分的不同的狀態(tài)集中，則i和j應(yīng)分離:
如 d(i,a)∈Qm , d(j,a)∈Qn 且 m≠n
⑶ 重復(fù)步驟⑵，直到再不能劃分為止；
⑷ 合并最終劃分的每個(gè)子集中的各狀態(tài)(合而為一)。