三、有窮狀態(tài)自動機
人閱讀正則表達式會比較簡單，但是機器閱讀正則表達式就是一件非常困難的事情了。而且，直接使用正則表達式進行匹配配的話，不僅工作量大，而且速度緩慢。因此我們還需要另外一種專門為機器設計的表達方式。本文在以后的章節(jié)中會給出一種算法把正則表達式轉(zhuǎn)換為機器可以閱讀的形式，就是這一章節(jié)所描述的有窮狀態(tài)自動機。
有窮狀態(tài)自動機這個名字聽起來比較可怕，不過實際上這種自動機并沒有想象中的那么復雜。狀態(tài)機的這種概念被廣泛的應用在各種各樣的領域中。軟件工程的統(tǒng)一建模語言(UML)有狀態(tài)圖，數(shù)字邏輯中也有狀態(tài)轉(zhuǎn)移圖。不過這些各種各樣的圖在本質(zhì)上都跟狀態(tài)機沒有什么區(qū)別。我將會通過一個例子來講述狀態(tài)的實際意義。
假設我們現(xiàn)在需要檢查一個字符串中a的數(shù)量和b的數(shù)量是否都是偶數(shù)。當然我們可以用一個正則表達式來描述它。不過對于這個問題來說，用正則表達式來描述遠遠不如構造狀態(tài)機方便。我們可以設計出一個狀態(tài)的集合，然后指定集合中的某一個元素為“起始狀態(tài)”。其實狀態(tài)就是在工作還沒開始的時候，分析器所處的狀態(tài)。分析器在每一次進行一項新的工作的時候，都要把狀態(tài)重置為起始狀態(tài)。分析器每讀入一個字符就修改一次狀態(tài)，修改的方法我們也可以指定。分析器在讀完所有的字符以后，必然停留在一個確定的狀態(tài)中。如果這個狀態(tài)跟我們所期望的狀態(tài)一致的話，我們就說這個分析器接受了這個字符串，否則我們就說這個分析器拒絕了這個字符串。
如何通過設計狀態(tài)及其轉(zhuǎn)移方法來實現(xiàn)一個分析器呢？當然，如果一個字符串僅僅包含a或者b的話，那么分析器的狀態(tài)只有四種：“奇數(shù)a奇數(shù)b”、“奇數(shù)a偶數(shù)b”、“偶數(shù)a奇數(shù)b”、“偶數(shù)a偶數(shù) b”。我們把這些狀態(tài)依次命名為aa、aB、Ab、AB。大寫代表偶數(shù)，小寫代表奇數(shù)。當工作還沒開始的時候，分析器已經(jīng)讀入的字符串是空串，那么理所當然的起始狀態(tài)應當是AB。當分析器讀完所有字符的時候，我們期望讀入的字符串的a和b的數(shù)量都是偶數(shù)，那么結(jié)束的狀態(tài)也應該是AB。于是我們給出這樣的一個狀態(tài)圖：
圖3.1
檢查一個字符串是否由偶數(shù)個a和偶數(shù)個b組成的狀態(tài)圖
在這個狀態(tài)圖里，有一個短小的箭頭指向了AB，代表AB這個狀態(tài)是初始狀態(tài)。AB狀態(tài)有粗的邊緣，代表AB這個狀態(tài)是結(jié)束的可接受狀態(tài)。一個狀態(tài)圖的結(jié)束狀態(tài)可以是一個或者多個。在這個例子里，起始狀態(tài)和結(jié)束狀態(tài)剛好是同一個狀態(tài)。標有字符”a”的箭頭從AB指向aB，代表如果分析器處于狀態(tài)AB并且讀入的字符是a的話，就轉(zhuǎn)移到狀態(tài)aB上。
我們把這個狀態(tài)圖應用在兩個字符串上，分別是”abaabbba”和”aababbaba”。其中，第一個字符串是可以接受的，第二個字符串是不可接受的(因為有5個a和4個b)。
分析第一個字符串的時候，狀態(tài)機所經(jīng)過的狀態(tài)是：
AB[a]aB[b]ab[a]Ab[a]ab[b]aB[b]ab[b]aB[a]AB
分析第二個字符串的時候，狀態(tài)機所經(jīng)過的狀態(tài)是：
AB[a]aB[a]AB[b]Ab[a]ab[b]aB[b]ab[a]Ab[b]AB[a]aB
第一個字符串”abaabbba”讓狀態(tài)機在狀態(tài)AB上停了下來，于是這個字符串是可以接受的。第二個字符串”aababbaba”讓狀態(tài)機在狀態(tài)aB上停了下來，于是這個字符串是不可以接受的。
在機器內(nèi)部表示這個狀態(tài)圖的話，我們可以使用一種比較簡單的方法。這種方法僅僅把狀態(tài)與狀態(tài)之間的箭頭、起始狀態(tài)和結(jié)束狀態(tài)集合記錄下來。對應于這個狀態(tài)圖的話，我們就可以把這個狀態(tài)圖表示成以下形式：
起始狀態(tài)：AB
結(jié)束狀態(tài)集合：AB
(AB,a,aB)
(AB,b,Ab)
(aB,a,AB)
(aB,b,ab)
(Ab,a,ab)
(Ab,b,AB)
(ab,a,Ab)
(ab,b,aB)
用一個狀態(tài)圖來表示狀態(tài)機的時候有時候會遇到確定性與非確定性的問題。所謂的確定性就是指對于任何一個狀態(tài)，輸入一個字符都可以跳轉(zhuǎn)到另一個確定的狀態(tài)中去。確定性和非確定性的區(qū)別有一個直觀的描述：狀態(tài)圖的任何一個狀態(tài)都可以有不定數(shù)量的邊指向另一個狀態(tài)，如果在這些邊里面，存在兩條邊，它們所承載的字符如果相同，那么這個狀態(tài)輸入這個就字符可以跳轉(zhuǎn)到另外兩個狀態(tài)中去，于是該狀態(tài)機就是不確定的。如圖所示：
圖3.2
正則表達式ba*b的一個確定的狀態(tài)機表示
圖3.3
正則表達式ba*b的一個非確定的狀態(tài)機表示
圖3.3中的狀態(tài)機的起始狀態(tài)讀入字符b后可以跳轉(zhuǎn)到中間的兩個狀態(tài)里，因此這個狀態(tài)機是非確定的。相反，圖3.2中的狀態(tài)機，雖然功能跟圖3.3的狀態(tài)機一致，但卻是確定的。我們還可以使用一種特殊的邊來進行狀態(tài)的轉(zhuǎn)換。我們用ε邊來表示一個狀態(tài)可以不讀入字符就跳轉(zhuǎn)到另一個狀態(tài)上。下圖給出了一個跟圖3.3功能一致的包含ε邊的非確定的狀態(tài)機：
圖3.4
正則表達式ba*b的一個帶有ε邊的非確定的狀態(tài)機
在教科書中，通常把確定的有窮狀態(tài)自動機(有窮狀態(tài)自動機也就是本文討論的這種狀態(tài)機)稱為DFA，把非確定的有窮狀態(tài)自動機稱為NFA，把帶有ε邊的非確定的狀態(tài)機稱為ε-NFA。下文中也將采用這幾個術語來指示各種類型的有窮狀態(tài)自動機。
在剛剛接觸到ε邊的時候，一個通常的疑問就是這種邊存在的理由。事實上如果是人直接畫狀態(tài)機的話，有時候也可以直接畫出一個確定的狀態(tài)機，復雜一點的話也可以畫出一個非確定的狀態(tài)機，在有些極端的情況下我們需要使用ε邊來更加簡潔的表示我們的意圖。不過ε邊存在的最大的理由就是：我們可以通過使用ε邊來給出一個簡潔的算法把一個正則表達式轉(zhuǎn)換成ε-NFA。