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