四、從正則表達式到ε-NFA
通過第二節(jié)所描述的內(nèi)容，我們知道一個正則表達式的基本元素就是字符集。通過對規(guī)則的串聯(lián)、并聯(lián)、重復、可選等操作，我們可以構(gòu)造除更復雜的正則表達式。如果從正則表達式構(gòu)造狀態(tài)機的時候也可以用這幾種操作對狀態(tài)圖進行組合的話，那么方法將會變得很簡單。接下來我們將一一對這5個構(gòu)造正則表達式的方法進行討論。使用下文描述的算法構(gòu)造出來的所有ε-NFA都有且只有一個結(jié)束狀態(tài)。
1：字符集
字符集是正則表達式最基本的元素，因此反映到狀態(tài)圖上，字符集也會是構(gòu)成狀態(tài)圖的基本元素。對于字符集C，如果有一個規(guī)則只接受C的話，這個規(guī)則對應(yīng)的狀態(tài)圖將會被構(gòu)造成以下形式：
圖4.1
這個狀態(tài)圖的初始狀態(tài)是Start，結(jié)束狀態(tài)是End。Start狀態(tài)讀入字符集C跳轉(zhuǎn)到End狀態(tài)，不接受其他字符集。
2：串聯(lián)
如果我們使用A⊙B表示規(guī)則A和規(guī)則B的串聯(lián)，我們可以很容易的知道串聯(lián)這個操作具有結(jié)合性，也就是說(A⊙B)⊙C=A⊙(B⊙C)。因此對于n個規(guī)則的串聯(lián)，我們只需要先將前n-1個規(guī)則進行串連，然后把得到的規(guī)則看成一個整體，跟最后一個規(guī)則進行串聯(lián)，那么就得到了所有規(guī)則的串聯(lián)。如果我們知道如何將兩個規(guī)則串聯(lián)起來的話，也就等于知道了如何把n個規(guī)則進行串聯(lián)。
為了將兩個串聯(lián)的規(guī)則轉(zhuǎn)換成一個狀態(tài)圖，我們只需要先將這兩個規(guī)則轉(zhuǎn)換成狀態(tài)圖，然后讓第一個狀態(tài)的結(jié)束狀態(tài)跳轉(zhuǎn)到第二個狀態(tài)圖的起始狀態(tài)。這種跳轉(zhuǎn)必須是不讀入字符的跳轉(zhuǎn)，也就是令這兩個狀態(tài)等價。因此，第一個狀態(tài)圖跳轉(zhuǎn)到了結(jié)束狀態(tài)的時候，就可以當成第二個狀態(tài)圖的起始狀態(tài)，繼續(xù)第二個規(guī)則的檢查。因此我們使用了ε邊連接兩個狀態(tài)圖：
圖4.2
3：并聯(lián)
并聯(lián)的方法跟串聯(lián)類似。為了可以在起始狀態(tài)讀入一個字符的時候就知道這個字符可能走的是并聯(lián)的哪一些分支并進行跳轉(zhuǎn)，我們需要先把所有分支的狀態(tài)圖構(gòu)造出來，然后把起始狀態(tài)連接到所有分支的起始狀態(tài)上。而且，在某個分支成功接受了一段字符串之后，為了讓那個狀態(tài)圖的結(jié)束狀態(tài)反映在整個狀態(tài)圖的結(jié)束狀態(tài)上，我們也把所有分支的結(jié)束狀態(tài)都連接到大規(guī)則的結(jié)束狀態(tài)上。如下所示：
圖4.3
4：重復
對于一個重復，我們可以設(shè)立兩個狀態(tài)。第一個狀態(tài)是起始狀態(tài)，第二個狀態(tài)是結(jié)束狀態(tài)。當狀態(tài)走到結(jié)束狀態(tài)的時候，如果遇到一個可以讓規(guī)則接受的字符串，則再次回到結(jié)束狀態(tài)。這樣的話就可以用一個狀態(tài)圖來表示重復了。于是對于重復，我們可以構(gòu)造狀態(tài)圖如下所示：
圖4.4
5：可選
為可選操作建立狀態(tài)圖比較簡單。為了完成可選操作，我們需要在接受一個字符的時候，如果字符串的前綴被當前規(guī)則接受則走當前規(guī)則的狀態(tài)圖，如果可選規(guī)則的后續(xù)規(guī)則接受了字符串則走后續(xù)規(guī)則的狀態(tài)圖，如果都接受的話就兩個圖都要走。為了達到這個目的，我們把規(guī)則的狀態(tài)圖的起始狀態(tài)和結(jié)束狀態(tài)連接起來，得到了如下狀態(tài)圖：
圖4.5
如果重復使用的是0次以上重復，也就是原來的重復加上可選的結(jié)果，那么可以簡單地把圖4.4的Start狀態(tài)去掉，讓End狀態(tài)同時擁有起始狀態(tài)和結(jié)束狀態(tài)兩個角色，[Start]和[End]則保持原狀。
至此，我們已經(jīng)將5種構(gòu)造狀態(tài)圖的辦法都對應(yīng)到了5種構(gòu)造規(guī)則的辦法上了。對于任意的一個正則表達式，我們僅需要把這個表達式還原成那5種構(gòu)造的嵌套，然后把每一步構(gòu)造都對應(yīng)到一個狀態(tài)圖的構(gòu)造上，就可以將一個正則表達式轉(zhuǎn)換成一個ε-NFA了。舉個例子，我們使用正則表達式來表達“一個字符串僅包含偶數(shù)個a和偶數(shù)個b”，然后把它轉(zhuǎn)換成ε-NFA。
我們先對這個問題進行分析。如果一個字符串僅包含偶數(shù)個a和偶數(shù)個b的話，那么這個字符串一定是偶數(shù)長度的。于是我們可以把這個字符串分割成兩個兩個的字符段。而且這些字符段只有四種：aa、bb、ab和ba。對于aa和bb來說，無論出現(xiàn)多少次都不會影響字符串中a和b的數(shù)量的奇偶性(理由：在一個模2加法系統(tǒng)里，0是不變項，也就是說對于任何屬于模2加法的數(shù)X有X+0 = 0+X = X)。對于ab和ba的話，如果一個字符串的開始和結(jié)束是ab或者ba，中間的部分是aa或者bb的任意組合，這個字符串也是具有偶數(shù)個a和偶數(shù)個b的。我們現(xiàn)在得到了兩種構(gòu)造偶數(shù)個a和偶數(shù)個b的字符串的方法。把串聯(lián)、并聯(lián)、可選、重復等操作應(yīng)用在這些字符串上，仍然會得到具有偶數(shù)個a和偶數(shù)個b的字符串。于是我們可以把正則表達式書寫成以下形式：
((aa|bb)|((ab|ba)(aa|bb)*(ab|ba)))*
根據(jù)上文提到的方法，我們可以把這個正則表達式轉(zhuǎn)換成以下狀態(tài)機：
圖4.6
至此，我們已經(jīng)得到了把一個正則表達式轉(zhuǎn)換為ε-NFA的方法了。但是只得到ε-NFA還是不行的，因為ε-NFA的不確定性太大了，直接根據(jù)ε-NFA跑的話，每一次都會得到大量的臨時狀態(tài)集合，會極大地降低效率。因此，我們還需要一個辦法消除一個狀態(tài)機的非確定性。