形式語言與自動機(jī) 有窮自動機(jī)

1形式語言與自動機(jī)

第三章有窮自動機(jī)南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院胡軍hujun.nju@139.com01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍2第三章

有窮自動機(jī)1.1非形式化描述1.2有窮自動機(jī)的基本定義1.3非確定的有窮自動機(jī)1.4具有ε轉(zhuǎn)移的有窮自動機(jī)1.5有窮自動機(jī)的應(yīng)用1.6具有輸出的有窮自動機(jī)（*)01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍31.1有窮狀態(tài)系統(tǒng)指針式鐘表共有12*60*60個(gè)狀態(tài)小時(shí)×分鐘×秒圍棋共有3361個(gè)狀態(tài)每一個(gè)格子：（空，黑，白）；格子數(shù)量：19行×19列某些電子產(chǎn)品中的開關(guān)電路，具有n個(gè)門的開關(guān)網(wǎng)絡(luò)有2n種狀態(tài)“網(wǎng)上購物”系統(tǒng)（示例：）01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍42007年圖靈獎(jiǎng)模型檢驗(yàn)（modelchecking）:基于自動機(jī)理論的形式化方法(formalmethods)E.ClarkEmersonSifakis01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍51.2有窮自動機(jī)的基本定義定義3.1一個(gè)有窮自動機(jī)(FiniteAutomata)簡稱FA，是一個(gè)五元組：M=(Q,∑,δ,q0,F)，其中（1）Q是有窮狀態(tài)集；（States）（2）∑是有窮的輸入字母表（Alphabet）（3）δ是轉(zhuǎn)移函數(shù)，它將Q×∑→Q(全映射)；（Transistonfunction）（4）q0∈Q，是初始狀態(tài)；（Initialstate）（5）FQ，是終結(jié)狀態(tài)集。（Acceptingstates）(終止?fàn)顟B(tài)，接受狀態(tài))上述定義的另一個(gè)說法：確定型的有窮自動機(jī)(DeterministicFiniteAutomata：DFA)01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍6DFA例子q0q1q21000,11字母表：S

={0,1}狀態(tài)集：Q={q0,q1,q2}初始狀態(tài)：

q0終結(jié)狀態(tài):F={q0,q1}狀態(tài)集輸入01q0q1q2q0q1q2q2q2q1轉(zhuǎn)換函數(shù)表d:

**→問題：1.接受什么特征的字符串？2.狀態(tài)q2起什么作用？01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍7這兩個(gè)DFA所接受的字符串集合分別是什么？DFA例子q0q1baabS

={a,b}q0q1q2q3q4aaaaabbbbbS

={a,b}01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍8設(shè)計(jì)一個(gè)DFA(字母表為{0,1}),接受如下字符串：設(shè)計(jì)一個(gè)DFA(字母表為{0,1}),接受如下特征的字符串：最多有三個(gè)1.q0q1011q20q31q4+0,1010DFA例子L={010,1}qeq0q1q01q010qdie0,10100,11010,101二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍9設(shè)計(jì)一個(gè)DFA(字母表為{0,1}),接受所有結(jié)尾是01的字符串。提示：DFA得記住讀入字符串的最后兩位。DFA例子qe01q0q1q00q10q01q110101001110001二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍10設(shè)計(jì)一個(gè)DFA(字母表為{0,1}),接受所有結(jié)尾是101的字符串。DFA例子01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍11例3.1給出一個(gè)有窮自動機(jī)Ｍ=({q0,q1,q2,q3},{0,1},δ,q0,{q0})其中：轉(zhuǎn)移函數(shù)δ具體定義如下：

δ(q0,1)=q1 δ(q0,0)=q2

δ(q1,1)=q0

δ(q1,0)=q3

δ(q2,1)=q3

δ(q2,0)=q0

δ(q3,1)=q2

δ(q3,0)=q1→*DFA例子01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍12有窮自動機(jī)的擴(kuò)充定義定義3.2對于有窮自動機(jī)M=(Q，∑，δ，q0，F(xiàn))，它的擴(kuò)充轉(zhuǎn)移函數(shù)

,是從Q×∑*到Q的映射，其具體定義如下：

（1）(q,ε)=q；

（2）(q,wa)=δ((q,w),a)。

其中q∈Q，w∈∑*，a∈∑。例如，對于例3.1中的有窮自動機(jī)，就有： (q0,010)=δ((q0,01),0)=δ(δ((q0,0),1),0)=δ(δ(δ((q0,ε),0),1),0)=δ(δ(δ(q0,0),1),0)=δ(δ(q2,1),0)=δ(q3,0)=q1。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍13有窮自動機(jī)的基本定義從δ到

的擴(kuò)充是很自然的，δ就是

的特例（當(dāng)|x|=1時(shí)）。今后在提到FA的轉(zhuǎn)移函數(shù)時(shí)，不再強(qiáng)調(diào)

這種寫法，一律用δ表示，即δ的第二個(gè)變元既可以是單個(gè)字符也可以是一個(gè)字符串。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍14有窮自動機(jī)模型開始時(shí)，“讀頭”指向帶上的第一個(gè)輸入符號，控制器中放的是FA的初始狀態(tài)。然后，依據(jù)轉(zhuǎn)移函數(shù)δ做動作：若控制器中的當(dāng)前狀態(tài)是q，且“讀頭”指向帶上符號為a，則控制器中狀態(tài)將變成p=δ(q,a)，且“讀頭”向右移指向帶上下一個(gè)符號，如此可以繼續(xù)進(jìn)行下去。(注意：讀頭不能回頭，只能一直向右移動)→*01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍15有窮自動機(jī)的模型定義3.3給出FA：M=(Q,∑,δ,q0,F)，若δ(q0,x)=p∈F(x∈∑*)，則稱字符串x被M接受。進(jìn)一步地，被M接受的全部字符串構(gòu)成的集合，稱為被有窮自動機(jī)M接受的語言，并記為L(M)。用集合描述法就是 L(M)={x∣δ(q0,x)∈F}。FA所能接受的只是∑*的一部分子集，有很多∑*的子集是任何FA都不能接受的。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍16從給定集合構(gòu)造接受該集合的FA例3.3：設(shè)計(jì)一個(gè)接受能被5整除的二進(jìn)制數(shù)的FAM用qs表示初始狀態(tài)，用q0、q1、q2、q3、q4分別表示二進(jìn)制數(shù)被5整除時(shí)余0（即能被5整除，所以它是終結(jié)狀態(tài)。）、余1、余2、余3、余4的狀態(tài)。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍17一個(gè)FA(字母表為{0,1}),接受所有結(jié)尾是101的字符串。能否給FA增加猜測選擇的能力？假設(shè)我們具有猜測何時(shí)輸入串還剩下三個(gè)字符的能力。

1.3非確定的有窮自動機(jī)(NFA)qdie101還剩三個(gè)字符01001二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍18NFA每個(gè)狀態(tài)對同樣的一個(gè)輸入字符，可能有0,1,或者多條轉(zhuǎn)換發(fā)生（"猜測"）.1010,1q0q1q2q301二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍19NFA：可以進(jìn)行猜測選擇1010,1q0q1q2q3狀態(tài)q0有兩個(gè)標(biāo)記為1的轉(zhuǎn)換；讀入1,NFA可以選擇停留在q0，或者繼續(xù)往前到狀態(tài)q101二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍20NFA：可以進(jìn)行猜測選擇1010,1q0q1q2q3狀態(tài)q1對于輸入

1沒有相應(yīng)的轉(zhuǎn)換；

q1上讀入1時(shí),NFA就運(yùn)行不下去了(die);而讀入0時(shí)候,NFA可以繼續(xù)到狀態(tài)q2；狀態(tài)q2類似的行為。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍211010,1q0q1q2q3q3沒有任何轉(zhuǎn)換出來；

q3上如果讀入0,1,NFA也運(yùn)行進(jìn)入死狀態(tài)。NFA：可以進(jìn)行猜測選擇01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍22NFA：猜測的能力1010,1q0q1q2q3猜測是否已經(jīng)到了最后三位字符的位置了？如果是，則猜測最后三位字符應(yīng)該是與101相匹配判斷是否到達(dá)輸入字符串的最末端NFA的運(yùn)行過程中某個(gè)時(shí)刻是會同時(shí)處于多個(gè)狀態(tài)中，只要輸入串x結(jié)束時(shí)NFA所處的多個(gè)狀態(tài)中至少有一個(gè)是接受狀態(tài)，就判斷NFA接受x。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍23

NFA的形式化定義定義3.4一個(gè)非確定的有窮自動機(jī)(NondeterministicFiniteAutomata)簡記為NFA，是一個(gè)五元組 M=(Q,∑,δ,q0,F)

其中Q、∑、q0和F與確定的有窮自動機(jī)的含意相同，只是轉(zhuǎn)移函數(shù)δ的定義不同，它是從Q×∑→2Q（Q的冪集）上的映射。在FA中，δ的一般形式是δ(q,a)=p(q,p∈Q)，而在NFA中，δ的一般形式是δ(q,a)={p1,p2,…,pk}(pi∈Q,i=1,2,…k)，或δ(q,a)=φ（空集）。在NFA中轉(zhuǎn)移函數(shù)δ的取值是一個(gè)狀態(tài)集，即使只有一個(gè)狀態(tài)p，也要寫成集合形式{p}。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍24

NFA的形式化定義定義3.5對于NFAM=(Q,∑,δ,q0,F)，它的擴(kuò)充轉(zhuǎn)移函數(shù)

是從Q×∑*→2Q的映射，具體定義如下： (1)(q,ε)={q}, (2)(q,wa)={p|p∈δ(r,a),r∈(q,w)}。對于例3.4中的NFA，(q0,01001)的求值過程如下圖：01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍25NFA接受的語言定義3.7給出NFAM=(Q,∑,δ,q0,F)，若δ(q0,x)∩F非空（x∈∑*），則稱字符串x被M接受。被NFAM接受的全體字符串稱為M接受的語言，記作L(M)。也就是 L(M)={x∣x∈∑*,且δ(q0,x)∩F非空}。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍26NFA與DFA的等價(jià)NFA能識別（接受）DFA所識別（接受）的所有語言。（為什么？）反過來成立嗎？任一個(gè)NFA都能轉(zhuǎn)換成一個(gè)DFA，二者所識別的語言是相等的。YES01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍27NFA→DFA:直觀的理解100,1q0q1q2NFA:DFA:1q0q0orq11q0orq2100001二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍28NFA→DFA:子集構(gòu)造法

(subsetconstruction)100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0,q1,q2}{q1,q2}{q0}{q1}{q2}?NFA中的任一個(gè)狀態(tài)子集都是所構(gòu)造的DFA的一個(gè)狀態(tài)

01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍29NFA→DFA:狀態(tài)之間的轉(zhuǎn)換100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0,q1,q2}{q1,q2}{q0}{q1}{q2}?01010,1010101010,101二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍30NFA→DFA:確定DFA接受狀態(tài)100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0,q1,q2}{q1,q2}{q0}{q1}{q2}?01010,1010101010,1DFA中包含NFA接受狀態(tài)的子集狀態(tài)設(shè)為accepting01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍31NFA→DFA:消除無用的狀態(tài)100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0}010101{q0,q1,q2}010{q1,q2}{q1}{q2}?01,1010,1將DFA中不可達(dá)的狀態(tài)消除掉。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍32子集構(gòu)造法的一般步驟NFADFA狀態(tài)q0,q1,…,qnφ,{q0},{q1},{q0,q1},…,{q0,…,qn}每個(gè)狀態(tài)都是NFA的一個(gè)子集。初始狀態(tài)q0{q0}轉(zhuǎn)換dd’({qi1,…,qik},a)=

d(qi1,a)∪…∪

d(qik,a)接受狀態(tài)Fí

QF’={S:S包含

F中至少一個(gè)狀態(tài)}

01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍33NFA-DFA等價(jià)性的形式化證明定理3.1設(shè)L是被一個(gè)非確定的有窮自動機(jī)接受的語言，則存在一個(gè)確定的有窮自動機(jī)也接受這個(gè)語言L。 證明

設(shè)

M=(Q,∑,δ,q0,F)是一個(gè)接受L的NFA，現(xiàn)在構(gòu)造一個(gè)DFAM′=(Q′,∑,δ′,q0′,F′)，其中：

Q′=2Q,即Q的每一個(gè)子集作為Q′的一個(gè)狀態(tài)，若子集為{q1,q2,…,qk}，則Q′中狀態(tài)記為[q1,q2,…,qk]； q0′={q0}；

F′2Q:F′的每個(gè)元素至少包含F(xiàn)中的一個(gè)狀態(tài)；

δ′的定義為：δ′([q1,q2,…,qi],a)=[p1,p2,…,pj]當(dāng)且僅當(dāng)

δ（{q1,q2,…,qi},a）={p1,p2,…,pj}(a∈∑)。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍34NFA-DFA等價(jià)性的形式化證明證明L(M′)=L(M)=L。先證一個(gè)更一般的命題：

δ′(q0’,x)=[q1,q2,…,qk] iffδ(q0,x)={q1,q2,…,qk}（x∈∑*）。 (3-1)

對x的長度∣x∣用歸納來證明。

歸納基礎(chǔ)

∣x∣=0，即x=ε。因?yàn)?/p>

δ′(q0′,ε)=q0′=[q0],

δ(q0,ε)={q0}。

根據(jù)δ′的定義。所以（3-1）式成立。

歸納步驟

設(shè)對于|x|≤m的輸入串（3-1）式成立，現(xiàn)在考慮長度為m+1的輸入串xa(x∈∑*，a∈∑)。因?yàn)橐环矫?/p>

δ′(q0′,xa)=δ′(δ′(q0′,x),a)，

（1）另一方面

δ(q0,xa)=δ(δ(q0,x),a)。

（2）01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍35NFA-DFA等價(jià)性的形式化證明由歸納法假設(shè)，因?yàn)閤長度為m，以下（3）式成立，即δ′(q0′,x)=[p1,p2,…,pj]當(dāng)且僅當(dāng)δ(q0,x)={p1,p2,…,pj}。（3）

再由δ′的定義：

δ′([p1,p2,…,pj],a)=[r1,r2,…,rs]當(dāng)且僅當(dāng)

δ({p1,p2,…,pj},a)={r1,r2,…,rs}（4）

將（3），（4）代入（1），（2）兩式，即得出

δ′(q0′,xa)=[r1,r2,…,rs]當(dāng)且僅當(dāng)δ(q0,xa)={r1,r2,…,rs}。

從而（3-1）式得到證明。

有了（3-1）式之后，若[q1,q2,…,qk]∈F′,則q1,q2,…,qk

至少有一個(gè)在F中；反之，若{q1,q2,…,qk}中有一個(gè)狀態(tài)在F中，則[q1,q2,…,qk]∈F′。這就是說，M和M′接受的語言是相同的，即L(M′)=L(M)=L。定理證畢。這個(gè)定理不僅證明了NFA和DFA兩類自動機(jī)的等價(jià)性，而且還給出了從一個(gè)NFA構(gòu)造與它等價(jià)的DFA的具體步驟，這種證明稱為構(gòu)造性的證明方法。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍36NFA-DFA等價(jià)構(gòu)造的例子例3.5設(shè)M=({q0,q1},{0,1},δ,q0,{q1})是一個(gè)NFA，其中：

δ（q0,0）={q0,q1}, δ（q0,1）={q1},

δ（q1,0）=Φ, δ（q1,1）={q0,q1}。根據(jù)定理3.1，我們能構(gòu)造出等價(jià)的DFA: M′=(Q,{0,1},δ′,[q0],F)

其中： Q={[q0],[q1],[q0,q1],Ф},F={[q1],[q0,q1]},

δ′([q0],0)=[q0,q1], δ′([q0],1)=[q1],

δ′([q1],0)=Φ, δ′([q1],1)=[q0,q1],

δ′([q0,q1],0)=[q0,q1], δ′([q0,q1],1)=[q0,q1],

δ′(Φ,0)=Φ, δ′(Φ,1)=Φ。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍37子集構(gòu)造法的實(shí)際實(shí)現(xiàn)從狀態(tài)[q0]出發(fā)，通過狀態(tài)轉(zhuǎn)移函數(shù)δ′，逐步擴(kuò)充狀態(tài)集；每一步僅對狀態(tài)集中新增加的狀態(tài)，才寫出狀態(tài)轉(zhuǎn)移函數(shù)；此過程一直繼續(xù)下去，直到不再增加新的狀態(tài)為止，最后就得到了DFA。例3.6將例3.4中的NFA化為等價(jià)的DFA，可按下述步驟構(gòu)造：

第一步

從[q0]開始：

δ′([q0],0)=[q0,q3],δ′([q0],1)=[q0,q1]。

第二步

處理兩個(gè)新狀態(tài)[q0,q3]和[q0,q1]

：

δ′([q0,q3],0)=[q0,q3,q4]，

δ′([q0,q3],1)=[q0,q1]；

δ′([q0,q1],0)=[q0,q3]，

δ′([q0,q1],1)=[q0,q1,q2]。

第三步

處理新增加的兩個(gè)狀態(tài)[q0,q3,q4]和[q0,q1,q2]

：

δ′([q0,q3,q4],0)=[q0,q3,q4],δ′([q0,q3,q4],1)=[q0,q1,q4]；

δ′([q0,q1,q2],0)=[q0,q3,q2],δ′([q0,q1,q2],1)=[q0,q3,q2]。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍38子集構(gòu)造法的實(shí)際實(shí)現(xiàn)

第四步

處理新增加的兩個(gè)狀態(tài)[q0,q1,q4]和[q0,q3,q2]：δ′([q0,q1,q4],0)=[q0,q3,q4],δ′([q0,q1,q4],1)=[q0,q1,q2,q4]；

δ′([q0,q3,q2],0)=[q0,q3,q4,q2],δ′([q0,q3,q2],1)=[q0,q1,q2]。

第五步

處理新增加的兩個(gè)狀態(tài)[q0,q1,q2,q4]和[q0,q3,q4,q2]：

δ′([q0,q1,q2,q4],0)=[q0,q3,q4,q2],δ′([q0,q1,q2,q4],1)=[q0,q1,q2,q4]；

δ′([q0,q3,q4,q2],0)=[q0,q3,q4,q2],δ′([q0,q3,q4,q2],1)=[q0,q1,q2,q4]。到這一步為止，不再增加新的狀態(tài)，所求的DFA只包含9個(gè)狀態(tài)。因?yàn)樵瓉淼腘FA有5個(gè)狀態(tài)，若按定理3.1的構(gòu)造方法，就要設(shè)25=32個(gè)狀態(tài)，是從初始狀態(tài)[q0]不能到達(dá)的，不必把這些狀態(tài)和相關(guān)的轉(zhuǎn)移函數(shù)包含到所求的DFA中去。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍391.4具有ε轉(zhuǎn)移的有窮自動機(jī)該自動機(jī)的狀態(tài)集為{q0,q1,q2},輸入字母表為{0，1，2}。由初始狀態(tài)q0開始，當(dāng)接到輸入符號0時(shí)，轉(zhuǎn)移到狀態(tài)q0本身，但不遇到任何符號（用ε表示）即可從q0轉(zhuǎn)移到q1，從q1到q2也有類似的情況。這種自動機(jī)在NFA的基礎(chǔ)上又增加了一種不確定性，它不僅在某些情況下有更簡潔表達(dá)能力，而且在證明一些理論問題時(shí)，更是不可缺少的工具。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍40另一個(gè)ε-NFA的例子設(shè)計(jì)一個(gè)NFA識別語言：字符串要么包含偶數(shù)個(gè)0，或奇數(shù)個(gè)1；r0r11100evennumberof0ss0s10011oddnumberof1sq0e-transitions不需要讀入任何符號即可發(fā)生狀態(tài)轉(zhuǎn)換01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍41具有ε轉(zhuǎn)移的有窮自動機(jī)定義3.8具有ε轉(zhuǎn)移的有窮自動機(jī)（簡稱ε-NFA）是一個(gè)五元組 M=(Q,∑,δ,q0,F)

其中Q,∑,q0,F的含義與一般的DFA或NFA相同，而δ是從

Q×(∑∪{ε})→2Q的映射。對于前面給出的自動機(jī)，它的δ函數(shù)是：

δ(q0,0)={q0}，

δ(q0,ε)={q1}，

δ(q1,1)={q1}，

δ(q1,ε)={q2}，

δ(q2,2)={q2}。凡是沒有寫出的δ，如δ(q0,1)，δ(q1,2)，δ(q2,1)等等，都是沒有定義的，這和一般的NFA相同。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍42具有ε轉(zhuǎn)移的有窮自動機(jī)定義3.9在一個(gè)具有ε轉(zhuǎn)移的有窮自動機(jī)中，對于狀態(tài)q，它的ε-CLOSURE(q)是由下述規(guī)則定義的狀態(tài)集：

（1）q在ε-CLOSURE(q)中；

（2）若p在ε-CLOSURE(q)中，則δ(p,ε)也都在ε-CLOSURE(q)中；

（3）重復(fù)（2），直到ε-CLOSURE(q)中狀態(tài)不再增加為止。

進(jìn)一步地，對于狀態(tài)集P的ε-CLOSURE，我們規(guī)定

ε-CLOSURE(P)=ε-CLOSURE(q)。所謂ε-CLOSURE(q)，從轉(zhuǎn)移圖上看，就是從狀態(tài)q出發(fā)，沿著標(biāo)有ε的有向邊所能達(dá)到的一切狀態(tài)所構(gòu)成的集合（包括狀態(tài)q本身）。所謂ε-CLOSURE(P)，就是對P中一切狀態(tài)q，分別求出ε-CLOSURE(q)，然后將這些狀態(tài)集求并而得的狀態(tài)集。例如，ε-CLOSURE(q0)={q0,q1,q2},ε-CLOSURE(q1)={q1,q2}。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍43具有ε轉(zhuǎn)移的有窮自動機(jī)定義3.10對于一個(gè)具有ε轉(zhuǎn)移的有窮自動機(jī)，它的擴(kuò)充轉(zhuǎn)移函數(shù)

定義如下：

（1）(q,ε)=ε-CLOSURE(q),

（2）(q,wa)=ε-CLOSURE(P),P=δ(r,a)。其中q∈Q,a∈∑,w∈∑*。例3.6考慮圖3.11中的自動機(jī) (q0,0)=ε-CLOSURE(δ((q0,ε),0)) =ε-CLOSURE(δ({q0,q1,q2},0)) =ε-CLOSURE({q0})={q0,q1,q2}。 (q0,01)=ε-CLOSURE(δ((q0,0),1)) =ε-CLOSURE(δ({q0,q1,q2},1)) =ε-CLOSURE({q1})={q1,q2}。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍44具有ε轉(zhuǎn)移的有窮自動機(jī)定義3.11對于一個(gè)具有ε轉(zhuǎn)移的有窮自動機(jī)M=(Q,∑,δ,q0,F)，它接受的語言定義為：

L(M)={w|d(q0,w)∩F非空}。定理3.2如果L被一個(gè)具有ε轉(zhuǎn)移的有窮自動機(jī)接受，則L也被一個(gè)不具有ε轉(zhuǎn)移的NFA接受。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍45具有ε轉(zhuǎn)移的有窮自動機(jī)證明(定理3.2)

設(shè)M=(Q,∑,δ,q0,F)是具有ε轉(zhuǎn)移的有窮自動機(jī)，且L(M)=L?，F(xiàn)在構(gòu)造M′=(Q,∑,δ′,q0,F′)是一個(gè)不具有ε轉(zhuǎn)移的NFA，其中：

δ′(q,a)=δ(q,a),q∈Q,a∈∑。

如果ε-CLOSURE({q0})∩F非空，則F′=F∪{q0}；否則，F(xiàn)′=F。

下面我們將對∣x∣作歸納法來證明下式：

δ′(q0,x)=(q0,x)。

（3-2）

注意當(dāng)x=ε時(shí)，（3-2）式不一定成立，因?yàn)棣摹?q0,ε)={q0}，而

(q0,ε)=ε-CLOSURE({q0})。所以只能對∣x∣≥1證明(3-2)式成立。

歸納基礎(chǔ)

∣x∣=1，即x=a(a∈∑)。根據(jù)δ′的定義，（3-2）式顯然成立。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍46具有ε轉(zhuǎn)移的有窮自動機(jī)歸納步驟

設(shè)∣x∣=m(m≥1)時(shí)，（3-2）式成立，現(xiàn)在要證當(dāng)∣x∣=m+1時(shí)，（3-2）式成立。

設(shè)x=wa(a∈∑,∣w∣=m)，則由δ′的定義：

δ′(q0,wa)=δ′(δ′(q0,w)，a)。

（1）

由歸納法假設(shè)，δ′(q0,w)=(q0,w)。設(shè)(q0,w)=P，則由δ′的擴(kuò)充定義：

δ′(P,a)=δ′(q,a)=(q,a)。

（2）

另一方面，由

的定義： (q0,wa)=ε-CLOSURE((q,a))。

01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍47具有ε轉(zhuǎn)移的有窮自動機(jī)

我們對（2）式的右部再進(jìn)一步推導(dǎo)，得出 (q,a)=ε-CLOSURE(δ(ε-CLOSURE（q）,a)) =ε-CLOSURE(δ(ε-CLOSURE（q）,a)) =ε-CLOSURE(δ(q,a))。

（4）

其中最后一步簡化是因?yàn)閷=(q0,w)中的任何狀態(tài)q,ε-CLOSURE(q)已經(jīng)在P中，所以在對P中狀態(tài)求和的情況下，可以將ε-CLOSURE(q)用q來代替。

綜合(1),(2),(3),(4)式，最后得出

δ′(q0,wa)=(q0,wa)。

到這里，我們用歸納法證明了對一切x(∣x∣≥1)，（3-2）式成立。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍48具有ε轉(zhuǎn)移的有窮自動機(jī)為了完成定理的證明，我們要證：

對一切x∈∑*,δ′(q,x)∩F’非空，當(dāng)且僅當(dāng)(q,x)∩F非空。對x=ε和x≠ε分兩種情況考慮。首先，當(dāng)x=ε時(shí)，若M接受它，則ε-CLOSURE(q0)至少包含F(xiàn)中的一個(gè)狀態(tài)，由F′的定義，則q0在F′中，那么M′也接受ε。反之，若M′接受ε，因?yàn)镸′是一個(gè)不具有ε轉(zhuǎn)移的NFA，則q0必須在F′中。進(jìn)一步分析，若q0也在F中，則M自