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