三、有窮狀態自動機

人閱讀正則表達式會比較簡單，但是機器閱讀正則表達式就是一件非常困難的事情了。而且，直接使用正則表達式進行匹配配的話，不僅工作量大，而且速度緩慢。因此我們還需要另外一種專門為機器設計的表達方式。本文在以后的章節中會給出一種算法把正則表達式轉換為機器可以閱讀的形式，就是這一章節所描述的有窮狀態自動機。

有窮狀態自動機這個名字聽起來比較可怕，不過實際上這種自動機并沒有想象中的那么復雜。狀態機的這種概念被廣泛的應用在各種各樣的領域中。軟件工程的統一建模語言(UML)有狀態圖，數字邏輯中也有狀態轉移圖。不過這些各種各樣的圖在本質上都跟狀態機沒有什么區別。我將會通過一個例子來講述狀態的實際意義。

假設我們現在需要檢查一個字符串中a的數量和b的數量是否都是偶數。當然我們可以用一個正則表達式來描述它。不過對于這個問題來說，用正則表達式來描述遠遠不如構造狀態機方便。我們可以設計出一個狀態的集合，然后指定集合中的某一個元素為“起始狀態”。其實狀態就是在工作還沒開始的時候，分析器所處的狀態。分析器在每一次進行一項新的工作的時候，都要把狀態重置為起始狀態。分析器每讀入一個字符就修改一次狀態，修改的方法我們也可以指定。分析器在讀完所有的字符以后，必然停留在一個確定的狀態中。如果這個狀態跟我們所期望的狀態一致的話，我們就說這個分析器接受了這個字符串，否則我們就說這個分析器拒絕了這個字符串。

如何通過設計狀態及其轉移方法來實現一個分析器呢？當然，如果一個字符串僅僅包含a或者b的話，那么分析器的狀態只有四種：“奇數a奇數b”、“奇數a偶數b”、“偶數a奇數b”、“偶數a偶數 b”。我們把這些狀態依次命名為aa、aB、Ab、AB。大寫代表偶數，小寫代表奇數。當工作還沒開始的時候，分析器已經讀入的字符串是空串，那么理所當然的起始狀態應當是AB。當分析器讀完所有字符的時候，我們期望讀入的字符串的a和b的數量都是偶數，那么結束的狀態也應該是AB。于是我們給出這樣的一個狀態圖：

 

 

圖3.1

檢查一個字符串是否由偶數個a和偶數個b組成的狀態圖

在這個狀態圖里，有一個短小的箭頭指向了AB，代表AB這個狀態是初始狀態。AB狀態有粗的邊緣，代表AB這個狀態是結束的可接受狀態。一個狀態圖的結束狀態可以是一個或者多個。在這個例子里，起始狀態和結束狀態剛好是同一個狀態。標有字符”a”的箭頭從AB指向aB，代表如果分析器處于狀態AB并且讀入的字符是a的話，就轉移到狀態aB上。

我們把這個狀態圖應用在兩個字符串上，分別是”abaabbba”和”aababbaba”。其中，第一個字符串是可以接受的，第二個字符串是不可接受的(因為有5個a和4個b)。

分析第一個字符串的時候，狀態機所經過的狀態是：

AB[a]aB[b]ab[a]Ab[a]ab[b]aB[b]ab[b]aB[a]AB

分析第二個字符串的時候，狀態機所經過的狀態是：

AB[a]aB[a]AB[b]Ab[a]ab[b]aB[b]ab[a]Ab[b]AB[a]aB

第一個字符串”abaabbba”讓狀態機在狀態AB上停了下來，于是這個字符串是可以接受的。第二個字符串”aababbaba”讓狀態機在狀態aB上停了下來，于是這個字符串是不可以接受的。

在機器內部表示這個狀態圖的話，我們可以使用一種比較簡單的方法。這種方法僅僅把狀態與狀態之間的箭頭、起始狀態和結束狀態集合記錄下來。對應于這個狀態圖的話，我們就可以把這個狀態圖表示成以下形式：

起始狀態：AB

結束狀態集合：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)

用一個狀態圖來表示狀態機的時候有時候會遇到確定性與非確定性的問題。所謂的確定性就是指對于任何一個狀態，輸入一個字符都可以跳轉到另一個確定的狀態中去。確定性和非確定性的區別有一個直觀的描述：狀態圖的任何一個狀態都可以有不定數量的邊指向另一個狀態，如果在這些邊里面，存在兩條邊，它們所承載的字符如果相同，那么這個狀態輸入這個就字符可以跳轉到另外兩個狀態中去，于是該狀態機就是不確定的。如圖所示：