1. 根據(jù)上面的狀態(tài)轉(zhuǎn)換圖寫出狀態(tài)轉(zhuǎn)換表，什么！不知道什么是狀態(tài)轉(zhuǎn)換表？那你來對地方了。狀態(tài)轉(zhuǎn)換表是轉(zhuǎn)臺轉(zhuǎn)換圖的另外一種表示形式，如下圖，左側(cè)表頭0~9表示的
是狀態(tài)，上方表頭a,b,c表示的是條件。其余部分表示的是后繼狀態(tài)
| a | b | ε |
0 | 1, 7 | ||
1 | 2, 4 | ||
2 | 3 | ||
3 | 6 | ||
4 | 5 | ||
5 |
| 6 | |
6 | 1, 7 | ||
7 | 8 | ||
8 | 9 | ||
9 |
ε-closure(0)={0,1,2,4,7}
ε-closure(1)={1,2,4}
ε-closure(2)={2}
ε-closure(3)={1,2,3,4,6,7}
ε-closure(4)={4}
ε-closure(5)={1,2,4,5,6,7}
ε-closure(6)={1,2,4,6,7}
ε-closure(7)={7}
ε-closure(8)={8}
ε-closure(9)={9}
3. 轉(zhuǎn)換，下面就是真正劇情了
首先將初始態(tài)的轉(zhuǎn)換閉包ε-closure(0)設(shè)為狀態(tài)A，即A={0,1,2,4,7}，注意這里的狀態(tài)A是DFA中的，和前面的狀態(tài)0,1,2,3,4,5沒有關(guān)系
接著寫出狀態(tài)A經(jīng)過上面轉(zhuǎn)換圖中所有轉(zhuǎn)換條件得到的狀態(tài)，后繼狀態(tài)里面不包括自身，這里的轉(zhuǎn)換條件包括a和b，注意，不包括ε，轉(zhuǎn)換的一個目的就是消除ε。
ε-closure(0) = A
ε-closure(move(A,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = B
ε-closure(move(A,b)) = ε-closure(5) = {1,2,4,5,6,7} = C
ε-closure(move(B,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = B
ε-closure(move(B,b)) = ε-closure({5,9}) = {1,2,4,5,6,7,9} = D
ε-closure(move(C,a)) = ε-closure()
ε-closure(move(C,b))
ε-closure(move(D,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = B
ε-closure(move(D,b)) = ε-closure(5) = {1,2,4,5,6,7} = C
4. 畫出DFA狀態(tài)轉(zhuǎn)換表（每一個狀態(tài)只有一個后繼狀態(tài)）
| a | b |
A | B | C |
B | B | D |
C | B | C |
D | B | C |
5. 畫出DFA狀態(tài)轉(zhuǎn)換圖
6. DFA的最小化
（1） 消除多余狀態(tài)
Ⅰ. 什么是多余狀態(tài)
· 從這個狀態(tài)出發(fā)沒有通路到達終態(tài)
· 從開始狀態(tài)出發(fā)，任何輸入串也不能到達的那個狀態(tài)
Ⅱ. 如何消除多余狀態(tài)
刪除
（2） 等價狀態(tài)
Ⅰ. 何為等價狀態(tài)，對于兩個狀態(tài)s和t
· 一致性條件：狀態(tài)s和t必須同時為終態(tài)或非終態(tài)
· 蔓延性條件：對于所有輸入符號，狀態(tài)s和狀態(tài)t必須轉(zhuǎn)化到等價的狀態(tài)里
接下來是關(guān)于如何利用上面的兩個條件來判斷是否為等價狀態(tài)，來一張復(fù)雜的狀態(tài)轉(zhuǎn)換圖，是不是有點暈，哈哈
首先，畫出狀態(tài)轉(zhuǎn)換表
看1和2，1和2都是非終態(tài)，滿足條件1，1和2都可以轉(zhuǎn)換成狀態(tài)2，滿足條件2，將兩者合并。
看6和7，6和7都是終態(tài)，滿足條件2，6和7都可以轉(zhuǎn)化成狀態(tài)6，滿足條件2，將兩者合并。
以此類推，當(dāng)然，2和5也是可以合并的，記住最后的結(jié)果只有一種，只要滿足合并后的狀態(tài)最少就行
轉(zhuǎn)化
1,2→A
3,4→B
5→C
6,7→D
列出轉(zhuǎn)化后的轉(zhuǎn)臺轉(zhuǎn)換表
再畫出相應(yīng)的狀態(tài)轉(zhuǎn)換圖就大功告成啦~~
