NFA的確定化過(guò)程簡(jiǎn)析

【摘 要】 在編譯原理的學(xué)習(xí)中，從上下文無(wú)關(guān)文法的初步理解進(jìn)階到詞法分析過(guò)程，是理解整個(gè)編譯過(guò)程的關(guān)鍵一步;其中，確定性有限自動(dòng)機(jī)（DFA）和非確定性有限自動(dòng)機(jī)（NFA）的等價(jià)與轉(zhuǎn)換，是這一部分的難點(diǎn)之一。本文將首先介紹DFA和NFA相關(guān)的幾個(gè)基本概念，然后著重介紹確定性有限自動(dòng)機(jī)（DFA）和非確定性有限自動(dòng)機(jī)（NFA）的等價(jià)變化過(guò)程。

【關(guān)鍵詞】 編譯原理 詞法分析 DFA NFA 有限自動(dòng)機(jī)

一、基本概念

（一）正規(guī)集和正規(guī)式

所謂正規(guī)集，就是一個(gè)集合，是一個(gè)字符的集合。正規(guī)指的就是，該集合中的字符，對(duì)于我們所研究的程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，是合法的。正規(guī)式則是正規(guī)集的另一種表示方式。或者說(shuō)，在研究編譯原理的過(guò)程中，用正規(guī)式來(lái)表示正規(guī)集。二者的對(duì)應(yīng)關(guān)系可以參考如下示例：設(shè)有字母表Σ，則Σ上的字符a和b都是正規(guī)式，它們分別表示Σ上的正規(guī)集{a}和。

詞法分析中的等價(jià)關(guān)系判定的充要條件，就是：被研究的兩個(gè)對(duì)象，其所表示的正規(guī)式是否相同。

（二）DFA和NFA

首先，F(xiàn)A（finite automaton），有限自動(dòng)機(jī)，本質(zhì)上就是狀態(tài)轉(zhuǎn)換圖（表示詞法分析器逐個(gè)識(shí)別輸入字符并進(jìn)行狀態(tài)轉(zhuǎn)換的過(guò)程）。一個(gè)有限自動(dòng)機(jī)由一個(gè)五元式組成：

S：有窮狀態(tài)集;Σ：有窮輸入字母表;f：狀態(tài)轉(zhuǎn)換函數(shù);S0：初始狀態(tài);F：終態(tài)

有限自動(dòng)機(jī)中的狀態(tài)轉(zhuǎn)換函數(shù)是其精髓所在。狀態(tài)轉(zhuǎn)換函數(shù)將詞法分析器的狀態(tài)轉(zhuǎn)換過(guò)程抽象為一個(gè)雙輸入單輸出的函數(shù)，而這樣的函數(shù)很容易使用矩陣來(lái)表示，從而使詞法分析器的工作過(guò)程得以數(shù)字化，進(jìn)而可以使用代碼來(lái)實(shí)現(xiàn)。

DFA（deterministic finite automaton），確定的有限自動(dòng)機(jī);

NFA（Nondeterministic finite automaton），非確定的有限自動(dòng)機(jī)。

二者的區(qū)別主要有三點(diǎn)：

DFA的初始狀態(tài)是唯一的，但NFA的初始狀態(tài)可以不唯一（注意，DFA和NFA的終態(tài)結(jié)點(diǎn)都可以不唯一）;

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

DFA中，每個(gè)狀態(tài)接收輸入后的轉(zhuǎn)換關(guān)系是一定的，但是在這一轉(zhuǎn)換關(guān)系NFA中不是確定的。

二、DFA和NFA之間的等價(jià)轉(zhuǎn)換過(guò)程

通過(guò)以上三點(diǎn)區(qū)別，不難看出，DFA是NFA的一種特例，或者說(shuō)NFA可以確定化為DFA。接下來(lái)我們討論NFA的確定化過(guò)程。根據(jù)DFA和NFA的三點(diǎn)區(qū)別，確定化的過(guò)程也分為三步：初態(tài)唯一化、拆分輸入、轉(zhuǎn)換關(guān)系確定化。

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

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

若S∈I，則從S出發(fā)經(jīng)過(guò)任意條ε弧而能到達(dá)的任何狀態(tài)S都屬于ε-closure（I）。

即集合形式： ε-closure（I）= I∪{S|從某個(gè)S∈I出發(fā)經(jīng)過(guò)任意條ε弧能到達(dá)S}。

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

J為I中所有狀態(tài)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)集合;

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

由此而達(dá)到的效果是，從I中的某個(gè)狀態(tài)出發(fā)經(jīng)過(guò)一條a弧而可以達(dá)到的所有狀態(tài)都在Ia之中。從而使得狀態(tài)之間的轉(zhuǎn)換變成狀態(tài)集之間的轉(zhuǎn)換。

接下來(lái)，先準(zhǔn)備一個(gè)大集合 I0，在圖3的狀態(tài)轉(zhuǎn)換圖中，經(jīng)過(guò)如下步驟：

1）從初始狀態(tài)開始，計(jì)算每一個(gè)狀態(tài)的I集合，放入 I0中;

2）再?gòu)腎出發(fā)，計(jì)算每一個(gè)I的Ja（狀態(tài)經(jīng)過(guò)一條a弧到達(dá)的狀態(tài)集合），再計(jì)算 Ia;

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

4）循環(huán)步驟2、3，直至所有的都出現(xiàn)在 I0中。

（這里請(qǐng)注意，步驟中的a代指的是狀態(tài)轉(zhuǎn)換圖中的所有非ε終結(jié)符;示例的具體計(jì)算步驟比較繁瑣，但是并不難理解，在此不再詳述）

至此，NFA和DFA的三方面差別都被消除。之后還可以對(duì)DFA進(jìn)行簡(jiǎn)化使結(jié)果更加直觀。以上既是NFA向DFA的轉(zhuǎn)換過(guò)程，也可以間接證明二者的等價(jià)。

【參考文獻(xiàn)】

[1] 陳火旺，等.程序設(shè)計(jì)語(yǔ)言編譯原理（第3版）[M].北京：國(guó)防工業(yè)出版社，2006： 46-53

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

作者簡(jiǎn)介：劉楊（1999——）男，漢族，河南信陽(yáng)人，單位：河南大學(xué)計(jì)算機(jī)與信息工程學(xué)院，本科，軟件工程專業(yè)，軟件工程：