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