NFA的確定化過程簡析

【摘 要】 在編譯原理的學習中，從上下文無關文法的初步理解進階到詞法分析過程，是理解整個編譯過程的關鍵一步;其中，確定性有限自動機（DFA）和非確定性有限自動機（NFA）的等價與轉換，是這一部分的難點之一。本文將首先介紹DFA和NFA相關的幾個基本概念，然后著重介紹確定性有限自動機（DFA）和非確定性有限自動機（NFA）的等價變化過程。

【關鍵詞】 編譯原理 詞法分析 DFA NFA 有限自動機

一、基本概念

（一）正規集和正規式

所謂正規集，就是一個集合，是一個字符的集合。正規指的就是，該集合中的字符，對于我們所研究的程序設計語言來說，是合法的。正規式則是正規集的另一種表示方式。或者說，在研究編譯原理的過程中，用正規式來表示正規集。二者的對應關系可以參考如下示例：設有字母表Σ，則Σ上的字符a和b都是正規式，它們分別表示Σ上的正規集{a}和{b}。

詞法分析中的等價關系判定的充要條件，就是：被研究的兩個對象，其所表示的正規式是否相同。

（二）DFA和NFA

首先，FA（finite automaton），有限自動機，本質上就是狀態轉換圖（表示詞法分析器逐個識別輸入字符并進行狀態轉換的過程）。一個有限自動機由一個五元式組成：

S：有窮狀態集;Σ：有窮輸入字母表;f：狀態轉換函數;S0：初始狀態;F：終態

有限自動機中的狀態轉換函數是其精髓所在。狀態轉換函數將詞法分析器的狀態轉換過程抽象為一個雙輸入單輸出的函數，而這樣的函數很容易使用矩陣來表示，從而使詞法分析器的工作過程得以數字化，進而可以使用代碼來實現。

DFA（deterministic finite automaton），確定的有限自動機;

NFA（Nondeterministic finite automaton），非確定的有限自動機。

二者的區別主要有三點：

DFA的初始狀態是唯一的，但NFA的初始狀態可以不唯一（注意，DFA和NFA的終態結點都可以不唯一）;

DFA中，每個狀態的輸入只能是單個字符，且不包括ε（空字符）;但是在NFA中，可以是一個字或者單個字符或者ε;

DFA中，每個狀態接收輸入后的轉換關系是一定的，但是在這一轉換關系NFA中不是確定的。

二、DFA和NFA之間的等價轉換過程

通過以上三點區別，不難看出，DFA是NFA的一種特例，或者說NFA可以確定化為DFA。接下來我們討論NFA的確定化過程。根據DFA和NFA的三點區別，確定化的過程也分為三步：初態唯一化、拆分輸入、轉換關系確定化。

為了方便討論，我們以圖1（a）為NFA狀態轉換圖的示例。首先，引進新的初態結點X和終態結點Y（X、Y不屬于原NFA的狀態集），從X到NFA的原初態集合中的任意一個結點連一條ε弧，從原終態集合中的任意一個結點連一條ε弧到Y，使X、Y成為新的初態和終態結點，完成初態結點的確定化，如圖1（b）所示。這樣并沒有改變原NFA的識別能力。接著，將圖中弧線上的多個字符拆分，方法是在有個u個字符的弧線上，添加u-1個狀態結點，多字符弧線分解為一個字符一條弧線，效果如圖1（c）所示。狀態函數確定化的關鍵是，要將每個狀態所連接的ε弧和其本身的非ε弧到達的狀態統一起來。這里要用到子集法。討論子集法之前，要先了解兩個概念。

1.設有狀態S，狀態集I是整個狀態集的一個子集，則定義I的ε-閉包——ε-closure（I）為：若S∈I，則S∈ε-closure（I）;

若S∈I，則從S出發經過任意條ε弧而能到達的任何狀態S都屬于ε-closure（I）。

即集合形式： ε-closure（I）= I∪{S|從某個S∈I出發經過任意條ε弧能到達S}。

2.設a是Σ中的一個字符，定義 Ia=ε-closure（J） ：

J為I中所有狀態經過一條a弧而到達的狀態集合;

將ε-closure（I）的定義套用在集合J上。

由此而達到的效果是，從I中的某個狀態出發經過一條a弧而可以達到的所有狀態都在Ia之中。從而使得狀態之間的轉換變成狀態集之間的轉換。

接下來，先準備一個大集合 I0，在圖3的狀態轉換圖中，經過如下步驟：

1）從初始狀態開始，計算每一個狀態的I集合，放入 I0中;

2）再從I出發，計算每一個I的Ja（狀態經過一條a弧到達的狀態集合），再計算 Ia;

3）檢查 I0中是否有 Ia，如果沒有，就將 Ia放入I0中，將 Ia看作新的集合I，再計算其Ja和Ia;

4）循環步驟2、3，直至所有的都出現在 I0中。

（這里請注意，步驟中的a代指的是狀態轉換圖中的所有非ε終結符;示例的具體計算步驟比較繁瑣，但是并不難理解，在此不再詳述）

至此，NFA和DFA的三方面差別都被消除。之后還可以對DFA進行簡化使結果更加直觀。以上既是NFA向DFA的轉換過程，也可以間接證明二者的等價。

【參考文獻】

[1] 陳火旺，等.程序設計語言編譯原理（第3版）[M].北京：國防工業出版社，2006： 46-53

[2] [美] Andrew W.Appel.現代編譯原理[M].趙克佳，等，譯.北京：人民郵電出版社， 2006： 18-20

作者簡介：劉楊（1999——）男，漢族，河南信陽人，單位：河南大學計算機與信息工程學院，本科，軟件工程專業，軟件工程：