理論上可以證明铡溪，每一個(gè)正則集合可以由一個(gè)狀態(tài)數(shù)最小的DFA識(shí)別毅否，且這個(gè)DFA是唯一的矮固。本博客將介紹如何把一個(gè)DFA的狀態(tài)數(shù)化簡(jiǎn)到最小刑桑，而不影響接受的語言氯质。
化簡(jiǎn)的DFA：當(dāng)且僅當(dāng)它沒有多余狀態(tài)并且它的狀態(tài)集中沒有兩個(gè)狀態(tài)是相互等價(jià)的。
等價(jià)狀態(tài)：是指對(duì)于DFA中所有狀態(tài)s和t祠斧，對(duì)于所有輸入符號(hào)c闻察，存在Ic(s)=Ic(t),即狀態(tài)s,t具有相同的后繼，則稱s和t是等價(jià)的。
狀態(tài)s和t等價(jià)的條件是：
（1）一致性條件：狀態(tài)s和t必須同時(shí)為接受狀態(tài)和不接受狀態(tài)辕漂。（是否屬于終止?fàn)顟B(tài)集）
（2）蔓延性條件：對(duì)于所有輸入符號(hào)呢灶，狀態(tài)s和t必須轉(zhuǎn)換到等價(jià)狀態(tài)里。
下面介紹一種具體的DFA化簡(jiǎn)方法——分割法钉嘹。
Sample：
已知一個(gè)確定的有窮自動(dòng)機(jī)M=({0,1,2,3,4,5}, {a,b}, δ, 0, {0,1}),其中δ見表
| 狀態(tài) | a | b |
|---|---|---|
| 0 | 1 | 2 |
| 1 | 1 | 4 |
| 2 | 1 | 3 |
| 3 | 3 | 2 |
| 4 | 0 | 5 |
| 5 | 5 | 4 |
Step 1:
根據(jù)一致性條件鸯乃，將狀態(tài)分為兩類。0跋涣，1屬于終止?fàn)顟B(tài)集缨睡，歸為一類，其他歸為另一類陈辱。
| 狀態(tài) | a | b | 類別 |
|---|---|---|---|
| 0 | 1(A) | 2(B) | A |
| 1 | 1(A) | 4(B) | A |
| 2 | 1(A) | 3(B) | B |
| 3 | 3(B) | 2(B) | B |
| 4 | 0(A) | 5(B) | B |
| 5 | 5(B) | 4(B) | B |
Step 2:
根據(jù)蔓延性條件奖年，對(duì)狀態(tài)進(jìn)行再分類。由上圖可以看出：2沛贪，4屬于同一類陋守；3，5屬于另一類鹏浅。
| 狀態(tài) | a | b | 類別 |
|---|---|---|---|
| 0 | 1(A) | 2(B) | A |
| 1 | 1(A) | 4(B) | A |
| 2 | 1(A) | 3(C) | B |
| 3 | 3(C) | 2(B) | C |
| 4 | 0(A) | 5(C) | B |
| 5 | 5(C) | 4(B) | C |
然后我們?cè)龠M(jìn)行檢查嗅义，發(fā)現(xiàn)A，B隐砸，C三類中狀態(tài)都已等價(jià)（每一個(gè)狀態(tài)都有相同的后繼）之碗。如果不等價(jià)，則按照剛才方法進(jìn)行再分季希。
所以我們得到的最小化DFA為M'=({A,B,C}, {a,b}, δ褪那，A，{A})式塌，其中δ見表
| 狀態(tài) | a | b |
|---|---|---|
| A | A | B |
| B | A | C |
| C | C | B |
