理論上可以證明，每一個(gè)正則集合可以由一個(gè)狀態(tài)數(shù)最小的DFA識(shí)別，且這個(gè)DFA是唯一的。本博客將介紹如何把一個(gè)DFA的狀態(tài)數(shù)化簡(jiǎn)到最小，而不影響接受的語(yǔ)言。
化簡(jiǎn)的DFA：當(dāng)且僅當(dāng)它沒(méi)有多余狀態(tài)并且它的狀態(tài)集中沒(mé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}),其中δ見(jiàn)表
| 狀態(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})，其中δ見(jiàn)表
| 狀態(tài) | a | b |
|---|---|---|
| A | A | B |
| B | A | C |
| C | C | B |
