還不太了解有窮自動機(jī)或是NFA的同學(xué)可以先看我的上一篇文章：正則到NFA的轉(zhuǎn)換
確定型有窮自動機(jī)
確定型有窮自動機(jī)是不確定有窮自動機(jī)中的一個特例，其中：
- 沒有輸出ε之上的轉(zhuǎn)換動作墓律。
- 對每個狀態(tài)s和每個輸入符號a醋界，有且只有一條標(biāo)號為a的邊離開s
確定型有窮自動機(jī)的轉(zhuǎn)換
下面來看看NFA怎么轉(zhuǎn)換為DFA吧
先來看看一會會涉及到操作
以下為算法
看完算法可能還是有些懵逼锚沸，我們一起來過一遍實(shí)例空入。以下圖為例。
-
先構(gòu)建一個這樣的表格
在這里插入圖片描述 然后從起始態(tài)出發(fā)禾进，做空串的kleene閉包姐呐，得到{ 0,1,2,3,4,7}殿怜，填入NFA的第一行，DFA此時命名為A（或數(shù)字1曙砂，甚至是α都可以）头谜，然后對這個得到的閉包做 move（a）操作，即用這個閉包的所有狀態(tài)去匹配a鸠澈，可以得到{1,2,3,4,6,7,8}柱告，發(fā)現(xiàn)是一個全新的狀態(tài)，填到NFA的第二行笑陈，給其DFA命名為B际度，然后在a下填入B。
-
然后還是用A去做 move（b） 操作涵妥，得到全新閉包{1,2,4,5,6,7}乖菱，例如NFA第三行，稱其為C，在b的第一行填入C窒所。至此鹉勒，得到下表
在這里插入圖片描述 -
然后再對B做 move（a）和 move（b）操作，得到
在這里插入圖片描述 -
操作C得到
在這里插入圖片描述 -
操作D得到
在這里插入圖片描述 -
操作E得到吵取，此時發(fā)現(xiàn)舊狀態(tài)全部處理完禽额，且沒有出現(xiàn)新狀態(tài)。那么我們的DFA就求完了皮官。
在這里插入圖片描述 -
將狀態(tài)表轉(zhuǎn)換為狀態(tài)圖（這里需要注意脯倒，A為第一個起始狀態(tài)，所以A為起始態(tài)捺氢。由于E包含接收態(tài)10藻丢，故E為接收態(tài)），整個轉(zhuǎn)換過程就全部結(jié)束了讯沈。這個方法我們稱其為子集構(gòu)造法
在這里插入圖片描述
DFA的簡化
對于同一個語言，可以存在多個識別此語言的DFA婿奔，所以缺狠，求出DFA后，通常我們還需要對DFA進(jìn)行簡化操作萍摊，求出最簡DFA挤茄。
簡化的本質(zhì)是合并性質(zhì)相同的狀態(tài)，以減少整個圖的大小冰木。
算法
- 將得到的狀態(tài)進(jìn)行劃分 ∏ 穷劈，劃分為兩部分，一部分為接收態(tài)踊沸，一部分為為非接收態(tài)組歇终。
- 繼續(xù)進(jìn)行劃分，通過其可以匹配的字符進(jìn)行判斷逼龟，若該組內(nèi)所有成員匹配字符都落在同一組內(nèi)评凝，即不可再分，否則重新劃分組
- 若 ∏new = ∏ 腺律，則進(jìn)入步驟4奕短，否則返回2
- 在分組 ∏new 每個組中選取一個狀態(tài)作為代表，代表DFA的最簡狀態(tài)匀钧。
實(shí)例
直接用上圖轉(zhuǎn)換出來的DFA來做翎碑。
- 分組，得到 {A,B,C,D} {E}
- {E} 獨(dú)自分組之斯，無法操作日杈。 {A,B,C,D}做a操作，發(fā)現(xiàn)都轉(zhuǎn)為狀態(tài)B，做b操作达椰，A翰蠢，B，C在 {A,B,C,D} 組內(nèi)成員啰劲，而D在另一個組內(nèi)梁沧，重新分組得到 {A,B,C} {D} {E}
- {D} {E}無法操作， {A,B,C} 做a操作蝇裤，都在同一組內(nèi)廷支，做b操作，B不在同一組內(nèi)栓辜，重新劃分恋拍，重新分組得到 {A,C} {B} {D} {E}
- {A,C} 進(jìn)行a操作和b操作都在同一組內(nèi)，無法繼續(xù)向下劃分了藕甩。操作到此結(jié)束施敢。可以將 {A,C}合并
-
得到以下轉(zhuǎn)換表
在這里插入圖片描述 -
轉(zhuǎn)換為狀態(tài)圖后
最簡DFA
至此我們NFA轉(zhuǎn)DFA及DFA的簡化全部完成了狭莱。
