五、消除非確定性
消除ε邊算法
我們見到的有窮狀態自動機一共有三種：ε-NFA、NFA和DFA。現在我們需要將ε-NFA轉換為DFA。一個DFA中不可能出現ε邊，所以我們首先要消除ε邊。消除ε邊算法基于一個很簡單的想法：如果狀態A通過ε邊到達狀態B的話，那么狀態A無需讀入字符就可以直達狀態B。如果狀態B需要讀入字符x才可以到達狀態C的話，那么狀態A讀入x也可以到達狀態C。因為從A到C的路徑是A B C，其中A到B不需要讀入字符。
于是我們會得到一個很自然的想法：消除從狀態A出發的ε邊，只需要尋找所有從A開始僅通過ε邊就可以到達的狀態，并把從這些狀態觸出發的非ε邊復制到A上即可。剩下的工作就是刪除所有的ε邊和一些因為消除ε邊而變得不可到達的狀態。為了更加形象地描述消除ε邊算法，我們從正則表達式(ab|cd)*構造一個ε-NFA，并在此狀態機上應用消除ε邊算法。
正則表達式(ab|cd)*的狀態圖如下所示：
圖5.1
1：找到所有有效狀態。
有效狀態就是在完成了消除ε邊算法之后仍然存在的狀態。我們可以在開始整個算法之前就預先計算出所有有效狀態。有效狀態的特點是存在非ε邊的輸入。同時，起始狀態也是一個有效狀態。結束狀態不一定是有效狀態，但是如果存在一個有效狀態可以僅通過ε邊到達結束狀態的話，那么這個狀態應該被標記為結束狀態。因此對一個ε-NFA應用消除ε邊算法產生的NFA可能出現多個結束狀態。不過起始狀態仍然只有一個。
我們可以把“存在非ε邊的輸入或者起始狀態”這個判斷方法應用在圖5.1每一個狀態上，計算出圖5.1中所有的有效狀態。結果如下圖所示。
圖5.2
所有非有效狀態的標簽都被刪除
如果一個狀態同時具有ε邊和非ε邊輸入的話，那么這個狀態仍然是有效狀態。因為所有的有效狀態在下一步的操作中，都會得到新的輸出和新的輸入。
2：添加所有必要的邊
接下來我們要對所有的有效狀態都應用一個算法。這個算法分成兩步。第一步是尋找一個狀態的ε閉包，第二步是把這個狀態的ε閉包看成一個整體，把所有從這個閉包中輸出的邊全部復制到當前狀態上。從標記有效狀態的結果我們得到了圖5.1狀態圖的有效狀態集合是{S/E 3 5 7 9}。我們依次對這些狀態應用上述算法。第一步，計算S/E狀態的ε閉包。所謂一個狀態的ε閉包就是從這個狀態出發，僅通過ε邊就可以到達的所有狀態的集合。下圖中標記出了狀態S/E的ε閉包：
圖5.3
現在，我們把狀態S/E從狀態S/E的ε閉包中排除出去。因為從狀態A輸出的非ε邊都屬于從狀態A的ε閉包中輸出的非ε邊，復制這些邊是沒有任何價值的。接下來就是找到從狀態S/E的ε閉包中輸出的非ε邊。在圖5.3我們可以很容易地發現，從狀態1和狀態6(見圖5.1的狀態標簽)分別輸出到狀態3和狀態7的標記了a或者b的邊，就是我們所要尋找的邊。接下來我們把這些邊復制到狀態S/E上，邊的目標狀態仍然保持不變，可以得到下圖：
圖5.4
至此，這個算法在S/E上的應用就結束了，接下來我們分別對剩下的有效狀態{3 5 7 9}分別應用此算法，可以得到下圖：
圖5.5
紅色的邊為新增加的邊
3：刪除所有ε邊和無效狀態
這一步操作是消除ε邊算法的最后步驟。我們只需要刪除所有的ε邊和無效狀態就完成了整個消除ε邊算法?，F在我們對圖5.5的狀態機應用第三步，得到如下狀態圖：
圖5.6
不過并不是只有新增的邊才不被刪除。根據定義，所有從有效狀態出發的非ε邊都是不能刪除的邊。
我們通過把消除ε邊算法應用在圖5.1的狀態機上，得到了圖5.6這個DFA。但是并不是所有的消除ε邊算法都可以直接從ε-NFA直接得到DFA，這個其實跟正則表達式本身有關。至于什么正則表達式可以達到這個效果這里就不深究了。但是因為有可能產生NFA，所以我們還需要一個算法把NFA轉換成DFA。