有限自動機(jī)分為確定有限自動機(jī)（DFA）和不確定有限自動機(jī)（NFA），這里介紹DFA,即確定有限自動機(jī)。

1. DFA的形式定義

從形式上說，一個有限狀態(tài)自動機(jī)可以用下面的5個參數(shù)來定義:

• Q: 狀態(tài)q0, q1, ... , qN的有限集合
• Σ: 有限的輸入符號字母表
• q0: 初始狀態(tài)
• F: 終極狀態(tài)的集合， F∈Q
• δ(q, i): 狀態(tài)之間的轉(zhuǎn)移函數(shù)或轉(zhuǎn)移矩陣。給定一個狀態(tài)q∈Q和一個輸入符號i∈Σ， δ(q, i)返回一個新的狀態(tài)q'∈Q。

2.DFA的java實現(xiàn)

       這里定義了一個抽象父類FA，DFA和NFA繼承了FA類。

以上就是自己實現(xiàn)的DFA對應(yīng)的類實例變量的定義。其中 FAState 類表示一個狀態(tài)節(jié)點，包含一個實例屬性id，

用于唯一區(qū)分一個FAState。

       構(gòu)造DFA對象時，需要傳入一個特定格式的文本文件的路徑。

       文件的格式,舉例如下:
                         5 3
                         1 2 3 4 5
                         b a !
                         1
                         5
                         1 -1 -1
                         -1 2 -1
                         -1 3 -1
                         -1 3 4
                         -1 -1 -1
       其中，第一行的兩個數(shù)字分別表示自動機(jī)狀態(tài)的數(shù)目和符號字母表中符號的數(shù)目
                    第二行的數(shù)字為每一個狀態(tài)的id
                    第三行為符號串(符號串間以空格隔開)
                    第四行的數(shù)字為開始狀態(tài)的id
                    第五行的數(shù)字為結(jié)束狀態(tài)的id
                    最后幾行為狀態(tài)轉(zhuǎn)換矩陣(其中數(shù)字表示跳轉(zhuǎn)到的狀態(tài)在狀態(tài)列表中的下標(biāo)，-1表示一個狀態(tài)不能遇到相應(yīng)的符號)

          上面的例子表示的DFA對象如下圖所示:
                      

3. 使用DFA識別符號串

        DFA構(gòu)造好了之后就可以用來識別符號串。這里引用了NFA/DFA算法 - 于公攤的雜貨鋪中的一個例子:

      如何通過設(shè)計狀態(tài)及其轉(zhuǎn)移方法來實現(xiàn)一個分析器呢？當(dāng)然，如果一個字符串僅僅包含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ù)。當(dāng)工作還沒開始的時候，分析器已經(jīng)讀入的字符串是空串，那么理所當(dāng)然的起始狀態(tài)應(yīng)當(dāng)是AB。當(dāng)分析器讀完所有

 字符的時候，我們期望讀入的字符串的a和b的數(shù)量都是偶數(shù)，那么結(jié)束的狀態(tài)也應(yīng)該是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)。

標(biāo)有字符”a”的箭頭從AB指向aB, 代表如果分析器處于狀態(tài)AB并且讀入的字符是a的話，就轉(zhuǎn)移到狀態(tài)aB上。我們把這個狀態(tài)圖

應(yīng)用在兩個字符串上，分別是”abaabbba”和”aababbaba”。

      其中，第一個字符串是可以接受的，第二個字符串是不可接受的(因為有5個a和4個b)。

      分析第一個字符串的時候，狀態(tài)機(jī)所經(jīng)過的狀態(tài)是：

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

      分析第二個字符串的時候，狀態(tài)機(jī)所經(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)機(jī)在狀態(tài)AB上停了下來，于是這個字符串是可以接受的。第二個字符串”aababbaba”讓狀態(tài)機(jī)

 在狀態(tài)aB上停了下來 ，于是這個字符串是不可以接受的。

        DFA識別符號串的核心算法實現(xiàn)如下:        

4.DFA最小化

4.1 最小狀態(tài)DFA的含義

1.沒有多余狀態(tài)(死狀態(tài))

2. 沒有兩個狀態(tài)是互相等價（不可區(qū)別）

4.2 兩個狀態(tài)s和t等價的條件

兼容性（一致性）條件——同是終態(tài)或同是非終態(tài)
傳播性（蔓延性）條件——從s出發(fā)讀入某個a和從t出發(fā)經(jīng)過某個a并且經(jīng)過某個b到達(dá)的狀態(tài)等價。

4.3 舉例說明

下面就以如下圖所示的DFA對象為例說明最小化DFA的操作

                                                   

DFA的最小化

1. 將狀態(tài)列表S中的狀態(tài)分為兩個子集:終結(jié)狀態(tài)s1(也叫可接受狀態(tài))和非終結(jié)狀態(tài)s2

    對于上圖中的DFA, s1 = {4, 5, 6, 7}, s2 = {1, 2, 3}

2. 查看s2 = {1, 2, 3}是否可以繼續(xù)劃分

    狀態(tài)2遇到a轉(zhuǎn)向s1中的狀態(tài)4,不在s2中，于是將s2繼續(xù)劃分，分為{1, 3}和{2}這兩個集合。

    繼續(xù)查看{1, 3}是否可以繼續(xù)劃分。由于3遇到b轉(zhuǎn)向s1中的狀態(tài)5,于是將{1, 3}繼續(xù)劃分，分為{1}和{3}這兩個集合。

3. 查看 s1= {4, 5, 6, 7}是否可以繼續(xù)劃分

     因為4, 5, 6, 7經(jīng)過a和b跳轉(zhuǎn)到的狀態(tài)都在s1中，不可再分。因而這四個節(jié)點可以用一個節(jié)點來表示。

需要注意的是，當(dāng)最終所以的子集不可再分時，如果一個子集內(nèi)的狀態(tài)不止一個，則由于同一子集內(nèi)的狀態(tài)等價，

同一子集內(nèi)的節(jié)點之間的狀態(tài)跳轉(zhuǎn)可以不用考慮。但是如果這個子集內(nèi)的某一狀態(tài)遇到一個符號轉(zhuǎn)向本身時，

這種向自身的轉(zhuǎn)移要體現(xiàn)在新的替換的狀態(tài)上。例如4,5,6,7最終屬于同一子集，最終用節(jié)點4來替換這4個節(jié)點時，

需要在狀態(tài)轉(zhuǎn)移矩陣中加上遇到a跳轉(zhuǎn)到節(jié)點4，與遇到b跳轉(zhuǎn)到節(jié)點4的情況。

      最終得到的最小化DFA如下圖所示:

                             

4.4 具體實現(xiàn)

DFA最小化的核心算法如下: