從NFA到DFA
NFA是非確定性的狀態(tài)機(jī)，DFA是確定性的狀態(tài)機(jī)。確定性和非確定性的最大區(qū)別就是：從一個(gè)狀態(tài)讀入一個(gè)字符，確定性的狀態(tài)機(jī)得到一個(gè)狀態(tài)，而非確定性的狀態(tài)機(jī)得到一個(gè)狀態(tài)的集合。如果我們把NFA的起始狀態(tài)S看成一個(gè)集合{S}的話，對(duì)于一個(gè)狀態(tài)集合S’，給定一個(gè)輸入，就可以用NFA計(jì)算出對(duì)應(yīng)的狀態(tài)集合T’。因此我們?cè)跇?gòu)造DFA的時(shí)候，只需要把起始狀態(tài)對(duì)應(yīng)到S’，并且找到所有可能在NFA同時(shí)出現(xiàn)的狀態(tài)集合，把這些集合都轉(zhuǎn)換成DFA的一個(gè)狀態(tài)，那么任務(wù)就完成了。因?yàn)?/span>NFA的狀態(tài)是有限的，所以NFA所有狀態(tài)的集合的冪集的元素個(gè)數(shù)也是有限的，因此使用這個(gè)方法構(gòu)造DFA是完全可能的。
為了形象地表達(dá)出這個(gè)算法的過(guò)程，我們將構(gòu)造一個(gè)正則表達(dá)式，然后給出該正則表達(dá)式轉(zhuǎn)換成NFA的結(jié)果，并把構(gòu)造DFA的算法應(yīng)用在NFA上。假設(shè)一個(gè)字符串只有a、b和c三種字符，判斷一個(gè)字符串是不是以abc開始并且以cba結(jié)束正則表達(dá)式如下：
abc(a|b|c)*cba
通過(guò)上文的算法，可以得出如下圖所示的NFA：
圖5.7
現(xiàn)在我們開始構(gòu)造DFA，具體算法如下：
1：把{S}放進(jìn)隊(duì)列L和集合D中。其中S是NFA的起始狀態(tài)。隊(duì)列L放置的是未被處理的已經(jīng)創(chuàng)建了的DFA狀態(tài)，集合D放置的是已經(jīng)存在的DFA狀態(tài)。根據(jù)上文的討論，DFA的每一個(gè)狀態(tài)都對(duì)應(yīng)著NFA的一些狀態(tài)。
2：從隊(duì)列L中取出一個(gè)狀態(tài)，計(jì)算從這個(gè)狀態(tài)輸出的所有邊所接受的字符集的并集，然后對(duì)該集合中的每一個(gè)字符尋找接受這個(gè)字符的邊，把這些邊的目標(biāo)狀態(tài)的并集T計(jì)算出來(lái)。如果T∈D則代表當(dāng)前字符指向了一個(gè)已知的DFA狀態(tài)。否則則代表當(dāng)前字符指向了一個(gè)未創(chuàng)建的DFA狀態(tài)，這個(gè)時(shí)候就把T放進(jìn)L和D中。在這個(gè)步驟里有兩層循環(huán)：第一層是遍歷所有接受的字符的并集，第二層是對(duì)每一個(gè)可以接受的字符遍歷所有輸出的邊計(jì)算目標(biāo)DFA狀態(tài)所包含的NFA狀態(tài)的集合。
3：如果L非空則跳到2。
現(xiàn)在我們開始對(duì)圖5.7的狀態(tài)機(jī)應(yīng)用DFA構(gòu)造算法。
首先執(zhí)行第一步，我們得到：
圖5.8
從上到下分別是隊(duì)列L、集合D和DFA的當(dāng)前狀態(tài)。就這樣一直執(zhí)行該算法直到狀態(tài)3進(jìn)入集合D，我們得到：
圖5.9
現(xiàn)在從隊(duì)列L中取出{3}，經(jīng)過(guò)分析得到狀態(tài)集合{3}接受的字符集合為{a b c}。{3}讀入a到達(dá){4}，讀入b到達(dá){5}，讀入c到達(dá){6 7}。因?yàn)?/span>{4}、{5}和{6 7}都不屬于D，所以把它們都放入隊(duì)列L和集合D：
圖5.10
從隊(duì)列中取出4進(jìn)行計(jì)算，我們得到：
圖5.11
顯然，對(duì)于狀態(tài){4}的處理并沒(méi)有發(fā)現(xiàn)新的DFA狀態(tài)。于是處理{5}和{6 7}，我們可以得到：
圖5.12
在處理狀態(tài){5}的時(shí)候沒(méi)有發(fā)現(xiàn)新的DFA狀態(tài)，處理{6 7}在輸入{a c}之后的跳轉(zhuǎn)也沒(méi)有發(fā)現(xiàn)新的DFA狀態(tài)，但是我們發(fā)現(xiàn)了{6 7}輸入b卻得到了新的DFA狀態(tài){5 8}。把算法執(zhí)行完，我們得到一個(gè)DFA：
圖5.13
至此，對(duì)圖5.7的狀態(tài)機(jī)應(yīng)用DFA構(gòu)造算法的流程就結(jié)束了，我們得到了圖5.13的DFA，其功能與圖5.7的NFA等價(jià)。在DFA中，起始狀態(tài)是0，結(jié)束狀態(tài)是4E。凡是包含了NFA的結(jié)束狀態(tài)的DFA狀態(tài)都必須是結(jié)束狀態(tài)。