1. 根據(jù)上面的狀態(tài)轉(zhuǎn)換圖寫(xiě)出狀態(tài)轉(zhuǎn)換表，什么！不知道什么是狀態(tài)轉(zhuǎn)換表？那你來(lái)對(duì)地方了。狀態(tài)轉(zhuǎn)換表是轉(zhuǎn)臺(tái)轉(zhuǎn)換圖的另外一種表示形式，如下圖，左側(cè)表頭0~9表示的

    是狀態(tài)，上方表頭a,b,c表示的是條件。其余部分表示的是后繼狀態(tài)

ε-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沒(méi)有關(guān)系

接著寫(xiě)出狀態(tài)A經(jīng)過(guò)上面轉(zhuǎn)換圖中所有轉(zhuǎn)換條件得到的狀態(tài)，后繼狀態(tài)里面不包括自身，這里的轉(zhuǎn)換條件包括a和b，注意，不包括ε，轉(zhuǎn)換的一個(gè)目的就是消除ε。

ε-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. 畫(huà)出DFA狀態(tài)轉(zhuǎn)換表（每一個(gè)狀態(tài)只有一個(gè)后繼狀態(tài)）

5. 畫(huà)出DFA狀態(tài)轉(zhuǎn)換圖

6. DFA的最小化

    （1） 消除多余狀態(tài)

              Ⅰ. 什么是多余狀態(tài)

                    · 從這個(gè)狀態(tài)出發(fā)沒(méi)有通路到達(dá)終態(tài)

                    ·  從開(kāi)始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)

               Ⅱ. 如何消除多余狀態(tài)

                     刪除

             （2）  等價(jià)狀態(tài)

                      Ⅰ. 何為等價(jià)狀態(tài)，對(duì)于兩個(gè)狀態(tài)s和t

                            ·  一致性條件：狀態(tài)s和t必須同時(shí)為終態(tài)或非終態(tài)

                            ·  蔓延性條件：對(duì)于所有輸入符號(hào)，狀態(tài)s和狀態(tài)t必須轉(zhuǎn)化到等價(jià)的狀態(tài)里

                   接下來(lái)是關(guān)于如何利用上面的兩個(gè)條件來(lái)判斷是否為等價(jià)狀態(tài)，來(lái)一張復(fù)雜的狀態(tài)轉(zhuǎn)換圖，是不是有點(diǎn)暈，哈哈

                   首先，畫(huà)出狀態(tài)轉(zhuǎn)換表

                  看1和2，1和2都是非終態(tài)，滿(mǎn)足條件1，1和2都可以轉(zhuǎn)換成狀態(tài)2，滿(mǎn)足條件2，將兩者合并。

                  看6和7，6和7都是終態(tài)，滿(mǎn)足條件2，6和7都可以轉(zhuǎn)化成狀態(tài)6，滿(mǎn)足條件2，將兩者合并。

                  以此類(lèi)推，當(dāng)然，2和5也是可以合并的，記住最后的結(jié)果只有一種，只要滿(mǎn)足合并后的狀態(tài)最少就行

                   轉(zhuǎn)化

                  1,2→A

                   3,4→B

                   5→C

                   6,7→D

                   列出轉(zhuǎn)化后的轉(zhuǎn)臺(tái)轉(zhuǎn)換表

                 再畫(huà)出相應(yīng)的狀態(tài)轉(zhuǎn)換圖就大功告成啦~~