四、從正則表達式到ε-NFA

通過第二節所描述的內容，我們知道一個正則表達式的基本元素就是字符集。通過對規則的串聯、并聯、重復、可選等操作，我們可以構造除更復雜的正則表達式。如果從正則表達式構造狀態機的時候也可以用這幾種操作對狀態圖進行組合的話，那么方法將會變得很簡單。接下來我們將一一對這5個構造正則表達式的方法進行討論。使用下文描述的算法構造出來的所有ε-NFA都有且只有一個結束狀態。

1：字符集

字符集是正則表達式最基本的元素，因此反映到狀態圖上，字符集也會是構成狀態圖的基本元素。對于字符集C，如果有一個規則只接受C的話，這個規則對應的狀態圖將會被構造成以下形式：

 

 

圖4.1

這個狀態圖的初始狀態是Start，結束狀態是End。Start狀態讀入字符集C跳轉到End狀態，不接受其他字符集。

2：串聯

如果我們使用A⊙B表示規則A和規則B的串聯，我們可以很容易的知道串聯這個操作具有結合性，也就是說(A⊙B)⊙C=A⊙(B⊙C)。因此對于n個規則的串聯，我們只需要先將前n-1個規則進行串連，然后把得到的規則看成一個整體，跟最后一個規則進行串聯，那么就得到了所有規則的串聯。如果我們知道如何將兩個規則串聯起來的話，也就等于知道了如何把n個規則進行串聯。

為了將兩個串聯的規則轉換成一個狀態圖，我們只需要先將這兩個規則轉換成狀態圖，然后讓第一個狀態的結束狀態跳轉到第二個狀態圖的起始狀態。這種跳轉必須是不讀入字符的跳轉，也就是令這兩個狀態等價。因此，第一個狀態圖跳轉到了結束狀態的時候，就可以當成第二個狀態圖的起始狀態，繼續第二個規則的檢查。因此我們使用了ε邊連接兩個狀態圖：

 

 

圖4.2

3：并聯

并聯的方法跟串聯類似。為了可以在起始狀態讀入一個字符的時候就知道這個字符可能走的是并聯的哪一些分支并進行跳轉，我們需要先把所有分支的狀態圖構造出來，然后把起始狀態連接到所有分支的起始狀態上。而且，在某個分支成功接受了一段字符串之后，為了讓那個狀態圖的結束狀態反映在整個狀態圖的結束狀態上，我們也把所有分支的結束狀態都連接到大規則的結束狀態上。如下所示：

圖4.3

4：重復

對于一個重復，我們可以設立兩個狀態。第一個狀態是起始狀態，第二個狀態是結束狀態。當狀態走到結束狀態的時候，如果遇到一個可以讓規則接受的字符串，則再次回到結束狀態。這樣的話就可以用一個狀態圖來表示重復了。于是對于重復，我們可以構造狀態圖如下所示：

圖4.4

5：可選

為可選操作建立狀態圖比較簡單。為了完成可選操作，我們需要在接受一個字符的時候，如果字符串的前綴被當前規則接受則走當前規則的狀態圖，如果可選規則的后續規則接受了字符串則走后續規則的狀態圖，如果都接受的話就兩個圖都要走。為了達到這個目的，我們把規則的狀態圖的起始狀態和結束狀態連接起來，得到了如下狀態圖：

圖4.5

如果重復使用的是0次以上重復，也就是原來的重復加上可選的結果，那么可以簡單地把圖4.4的Start狀態去掉，讓End狀態同時擁有起始狀態和結束狀態兩個角色，[Start]和[End]則保持原狀。

至此，我們已經將5種構造狀態圖的辦法都對應到了5種構造規則的辦法上了。對于任意的一個正則表達式，我們僅需要把這個表達式還原成那5種構造的嵌套，然后把每一步構造都對應到一個狀態圖的構造上，就可以將一個正則表達式轉換成一個ε-NFA了。舉個例子，我們使用正則表達式來表達“一個字符串僅包含偶數個a和偶數個b”，然后把它轉換成ε-NFA。

我們先對這個問題進行分析。如果一個字符串僅包含偶數個a和偶數個b的話，那么這個字符串一定是偶數長度的。于是我們可以把這個字符串分割成兩個兩個的字符段。而且這些字符段只有四種：aa、bb、ab和ba。對于aa和bb來說，無論出現多少次都不會影響字符串中a和b的數量的奇偶性(理由：在一個模2加法系統里，0是不變項，也就是說對于任何屬于模2加法的數X有X+0 = 0+X = X)。對于ab和ba的話，如果一個字符串的開始和結束是ab或者ba，中間的部分是aa或者bb的任意組合，這個字符串也是具有偶數個a和偶數個b的。我們現在得到了兩種構造偶數個a和偶數個b的字符串的方法。把串聯、并聯、可選、重復等操作應用在這些字符串上，仍然會得到具有偶數個a和偶數個b的字符串。于是我們可以把正則表達式書寫成以下形式：

((aa|bb)|((ab|ba)(aa|bb)*(ab|ba)))*

根據上文提到的方法，我們可以把這個正則表達式轉換成以下狀態機：

圖4.6

至此，我們已經得到了把一個正則表達式轉換為ε-NFA的方法了。但是只得到ε-NFA還是不行的，因為ε-NFA的不確定性太大了，直接根據ε-NFA跑的話，每一次都會得到大量的臨時狀態集合，會極大地降低效率。因此，我們還需要一個辦法消除一個狀態機的非確定性。