NFA轉(zhuǎn)DFA的算法在編譯原理的課本上都有，只不過(guò)課本上的算法太拗口，不好記！我在這里邊說(shuō)的都很通俗，只要看得懂字的都會(huì)懂。在本篇文章里用一個(gè)例子來(lái)說(shuō)明怎么實(shí)現(xiàn)NFA轉(zhuǎn)DFA與DFA簡(jiǎn)化，NFA轉(zhuǎn)DFA會(huì)講的比較細(xì)，DFA簡(jiǎn)化只是大概帶過(guò)。

有一個(gè)NFA，如圖：

要是想把NFA轉(zhuǎn)成DFA，首先需要構(gòu)造一張表（最主要的就是這張表），如圖：

上圖沒(méi)有給出全部的轉(zhuǎn)換關(guān)系，當(dāng)然，大家這么聰明，在看了構(gòu)造表的算法之后就會(huì)自己構(gòu)造轉(zhuǎn)換表了。構(gòu)造轉(zhuǎn)換表的算法如下（表中的第一列是給為化簡(jiǎn)的DFA狀態(tài)取的名字，第二列也是DFA中的狀態(tài)，第三列和第四列是DFA在某一狀態(tài)在讀取a、b時(shí)跳轉(zhuǎn)到的狀態(tài)）：

1. 首先把NFA轉(zhuǎn)換為上圖所示的模樣。
2. 從NFA的初始狀態(tài)開(kāi)始，把從初始狀態(tài)跳空能到的狀態(tài)以及該狀態(tài)跳空能到的狀態(tài)填在第二列第二行中，直到?jīng)]有新的狀態(tài)能夠由已得到的狀態(tài)跳空得到為止，就如{X，1,2}。
3. 第二列的狀態(tài)分別對(duì)應(yīng)NFA圖來(lái)分別跳a，跳a后的狀態(tài)填在Ia列以及跳a行對(duì)應(yīng)的單元中，得到的狀態(tài)再跳空，如果NFA對(duì)應(yīng)的狀態(tài)有跳空則把跳空后的狀態(tài)也填入同一個(gè)單元格中，如上表的{1,3,2}。
4. 跳b的情況也與跳a的情況類(lèi)似，把第三步的跳a改成跳b即可。
5. 經(jīng)過(guò)3、4步得到的狀態(tài)再把他們分別填在第二列中，用2-4的步驟來(lái)生成經(jīng)他們讀a、b能到的狀態(tài)。
6. 重復(fù)3-5。
   
7. 當(dāng)表中的所有狀態(tài)都出現(xiàn)在第一列時(shí)說(shuō)明表的構(gòu)造已經(jīng)完成了。

在構(gòu)造了表之后就可以通過(guò)這個(gè)表來(lái)構(gòu)造相應(yīng)的DFA了（有X的是初態(tài)，有Y的是終態(tài)），在這里不再贅述怎么用表來(lái)構(gòu)造DFA。

在構(gòu)造了DFA之后就需要來(lái)化簡(jiǎn)它了，化簡(jiǎn)DFA的算法如下：

1. 先分成非終態(tài)和終態(tài)兩個(gè)大的狀態(tài)。
2. 再在這兩個(gè)狀態(tài)里邊找跳a、b后所到的狀態(tài)不在其所在集合里邊的狀態(tài)，把它單獨(dú)作為一個(gè)狀態(tài)分出去（即需要區(qū)分狀態(tài)內(nèi)部是否識(shí)別a、b）。
3. 得到的新?tīng)顟B(tài)再分別使用步驟2的方法，直到?jīng)]有新的狀態(tài)產(chǎn)生為止（即所有的狀態(tài)內(nèi)部都能夠識(shí)別a和b）。

上述所說(shuō)的方法結(jié)合例子來(lái)看就更容易理解了！