NFA轉(zhuǎn)DFA的算法在編譯原理的課本上都有，只不過課本上的算法太拗口，不好記！我在這里邊說的都很通俗，只要看得懂字的都會(huì)懂。在本篇文章里用一個(gè)例子來說明怎么實(shí)現(xiàn)NFA轉(zhuǎn)DFA與DFA簡化，NFA轉(zhuǎn)DFA會(huì)講的比較細(xì)，DFA簡化只是大概帶過。
有一個(gè)NFA，如圖：
要是想把NFA轉(zhuǎn)成DFA，首先需要構(gòu)造一張表（最主要的就是這張表），如圖：
上圖沒有給出全部的轉(zhuǎn)換關(guān)系，當(dāng)然，大家這么聰明，在看了構(gòu)造表的算法之后就會(huì)自己構(gòu)造轉(zhuǎn)換表了。構(gòu)造轉(zhuǎn)換表的算法如下（表中的第一列是給為化簡的DFA狀態(tài)取的名字，第二列也是DFA中的狀態(tài)，第三列和第四列是DFA在某一狀態(tài)在讀取a、b時(shí)跳轉(zhuǎn)到的狀態(tài)）：
- 首先把NFA轉(zhuǎn)換為上圖所示的模樣。
- 從NFA的初始狀態(tài)開始，把從初始狀態(tài)跳空能到的狀態(tài)以及該狀態(tài)跳空能到的狀態(tài)填在第二列第二行中，直到?jīng)]有新的狀態(tài)能夠由已得到的狀態(tài)跳空得到為止，就如{X，1,2}。
- 第二列的狀態(tài)分別對應(yīng)NFA圖來分別跳a，跳a后的狀態(tài)填在Ia列以及跳a行對應(yīng)的單元中，得到的狀態(tài)再跳空，如果NFA對應(yīng)的狀態(tài)有跳空則把跳空后的狀態(tài)也填入同一個(gè)單元格中，如上表的{1,3,2}。
- 跳b的情況也與跳a的情況類似，把第三步的跳a改成跳b即可。
- 經(jīng)過3、4步得到的狀態(tài)再把他們分別填在第二列中，用2-4的步驟來生成經(jīng)他們讀a、b能到的狀態(tài)。
- 重復(fù)3-5。
- 當(dāng)表中的所有狀態(tài)都出現(xiàn)在第一列時(shí)說明表的構(gòu)造已經(jīng)完成了。
在構(gòu)造了表之后就可以通過這個(gè)表來構(gòu)造相應(yīng)的DFA了（有X的是初態(tài)，有Y的是終態(tài)），在這里不再贅述怎么用表來構(gòu)造DFA。
在構(gòu)造了DFA之后就需要來化簡它了，化簡DFA的算法如下：
- 先分成非終態(tài)和終態(tài)兩個(gè)大的狀態(tài)。
- 再在這兩個(gè)狀態(tài)里邊找跳a、b后所到的狀態(tài)不在其所在集合里邊的狀態(tài)，把它單獨(dú)作為一個(gè)狀態(tài)分出去（即需要區(qū)分狀態(tài)內(nèi)部是否識(shí)別a、b）。
- 得到的新狀態(tài)再分別使用步驟2的方法，直到?jīng)]有新的狀態(tài)產(chǎn)生為止（即所有的狀態(tài)內(nèi)部都能夠識(shí)別a和b）。
上述所說的方法結(jié)合例子來看就更容易理解了！
本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請
點(diǎn)擊舉報(bào)。
