版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1形式語言與自動(dòng)機(jī)
第三章有窮自動(dòng)機(jī)南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院胡軍hujun.nju@139.com01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍2第三章
有窮自動(dòng)機(jī)1.1非形式化描述1.2有窮自動(dòng)機(jī)的基本定義1.3非確定的有窮自動(dòng)機(jī)1.4具有ε轉(zhuǎn)移的有窮自動(dòng)機(jī)1.5有窮自動(dòng)機(jī)的應(yīng)用1.6具有輸出的有窮自動(dòng)機(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)上購(gòu)物”系統(tǒng)(示例:)01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍42007年圖靈獎(jiǎng)模型檢驗(yàn)(modelchecking):基于自動(dòng)機(jī)理論的形式化方法(formalmethods)E.ClarkEmersonSifakis01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍51.2有窮自動(dòng)機(jī)的基本定義定義3.1一個(gè)有窮自動(dòng)機(jī)(FiniteAutomata)簡(jiǎn)稱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è)說法:確定型的有窮自動(dòng)機(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è)有窮自動(dòng)機(jī)M=({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有窮自動(dòng)機(jī)的擴(kuò)充定義定義3.2對(duì)于有窮自動(dòng)機(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∈∑。例如,對(duì)于例3.1中的有窮自動(dòng)機(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有窮自動(dòng)機(jī)的基本定義從δ到
的擴(kuò)充是很自然的,δ就是
的特例(當(dāng)|x|=1時(shí))。今后在提到FA的轉(zhuǎn)移函數(shù)時(shí),不再?gòu)?qiáng)調(diào)
這種寫法,一律用δ表示,即δ的第二個(gè)變?cè)瓤梢允菃蝹€(gè)字符也可以是一個(gè)字符串。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍14有窮自動(dòng)機(jī)模型開始時(shí),“讀頭”指向帶上的第一個(gè)輸入符號(hào),控制器中放的是FA的初始狀態(tài)。然后,依據(jù)轉(zhuǎn)移函數(shù)δ做動(dòng)作:若控制器中的當(dāng)前狀態(tài)是q,且“讀頭”指向帶上符號(hào)為a,則控制器中狀態(tài)將變成p=δ(q,a),且“讀頭”向右移指向帶上下一個(gè)符號(hào),如此可以繼續(xù)進(jìn)行下去。(注意:讀頭不能回頭,只能一直向右移動(dòng))→*01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍15有窮自動(dòng)機(jī)的模型定義3.3給出FA:M=(Q,∑,δ,q0,F),若δ(q0,x)=p∈F(x∈∑*),則稱字符串x被M接受。進(jìn)一步地,被M接受的全部字符串構(gòu)成的集合,稱為被有窮自動(dòng)機(jī)M接受的語言,并記為L(zhǎng)(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增加猜測(cè)選擇的能力?假設(shè)我們具有猜測(cè)何時(shí)輸入串還剩下三個(gè)字符的能力。
1.3非確定的有窮自動(dòng)機(jī)(NFA)qdie101還剩三個(gè)字符01001二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍18NFA每個(gè)狀態(tài)對(duì)同樣的一個(gè)輸入字符,可能有0,1,或者多條轉(zhuǎn)換發(fā)生("猜測(cè)").1010,1q0q1q2q301二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍19NFA:可以進(jìn)行猜測(cè)選擇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)行猜測(cè)選擇1010,1q0q1q2q3狀態(tài)q1對(duì)于輸入
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)行猜測(cè)選擇01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍22NFA:猜測(cè)的能力1010,1q0q1q2q3猜測(cè)是否已經(jīng)到了最后三位字符的位置了?如果是,則猜測(cè)最后三位字符應(yīng)該是與101相匹配判斷是否到達(dá)輸入字符串的最末端NFA的運(yùn)行過程中某個(gè)時(shí)刻是會(huì)同時(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è)非確定的有窮自動(dòng)機(jī)(NondeterministicFiniteAutomata)簡(jiǎn)記為NFA,是一個(gè)五元組 M=(Q,∑,δ,q0,F)
其中Q、∑、q0和F與確定的有窮自動(dòng)機(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對(duì)于NFAM=(Q,∑,δ,q0,F),它的擴(kuò)充轉(zhuǎn)移函數(shù)
是從Q×∑*→2Q的映射,具體定義如下: (1)(q,ε)={q}, (2)(q,wa)={p|p∈δ(r,a),r∈(q,w)}。對(duì)于例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能識(shí)別(接受)DFA所識(shí)別(接受)的所有語言。(為什么?)反過來成立嗎?任一個(gè)NFA都能轉(zhuǎn)換成一個(gè)DFA,二者所識(shí)別的語言是相等的。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è)非確定的有窮自動(dòng)機(jī)接受的語言,則存在一個(gè)確定的有窮自動(dòng)機(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)
對(duì)x的長(zhǎng)度∣x∣用歸納來證明。
歸納基礎(chǔ)
∣x∣=0,即x=ε。因?yàn)?/p>
δ′(q0′,ε)=q0′=[q0],
δ(q0,ε)={q0}。
根據(jù)δ′的定義。所以(3-1)式成立。
歸納步驟
設(shè)對(duì)于|x|≤m的輸入串(3-1)式成立,現(xiàn)在考慮長(zhǎng)度為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)閤長(zhǎng)度為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兩類自動(dòng)機(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)集;每一步僅對(duì)狀態(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)移的有窮自動(dòng)機(jī)該自動(dòng)機(jī)的狀態(tài)集為{q0,q1,q2},輸入字母表為{0,1,2}。由初始狀態(tài)q0開始,當(dāng)接到輸入符號(hào)0時(shí),轉(zhuǎn)移到狀態(tài)q0本身,但不遇到任何符號(hào)(用ε表示)即可從q0轉(zhuǎn)移到q1,從q1到q2也有類似的情況。這種自動(dòng)機(jī)在NFA的基礎(chǔ)上又增加了一種不確定性,它不僅在某些情況下有更簡(jiǎn)潔表達(dá)能力,而且在證明一些理論問題時(shí),更是不可缺少的工具。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍40另一個(gè)ε-NFA的例子設(shè)計(jì)一個(gè)NFA識(shí)別語言:字符串要么包含偶數(shù)個(gè)0,或奇數(shù)個(gè)1;r0r11100evennumberof0ss0s10011oddnumberof1sq0e-transitions不需要讀入任何符號(hào)即可發(fā)生狀態(tài)轉(zhuǎn)換01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍41具有ε轉(zhuǎn)移的有窮自動(dòng)機(jī)定義3.8具有ε轉(zhuǎn)移的有窮自動(dòng)機(jī)(簡(jiǎn)稱ε-NFA)是一個(gè)五元組 M=(Q,∑,δ,q0,F)
其中Q,∑,q0,F的含義與一般的DFA或NFA相同,而δ是從
Q×(∑∪{ε})→2Q的映射。對(duì)于前面給出的自動(dòng)機(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)移的有窮自動(dòng)機(jī)定義3.9在一個(gè)具有ε轉(zhuǎn)移的有窮自動(dòng)機(jī)中,對(duì)于狀態(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)一步地,對(duì)于狀態(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),就是對(duì)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)移的有窮自動(dòng)機(jī)定義3.10對(duì)于一個(gè)具有ε轉(zhuǎn)移的有窮自動(dòng)機(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中的自動(dòng)機(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)移的有窮自動(dòng)機(jī)定義3.11對(duì)于一個(gè)具有ε轉(zhuǎn)移的有窮自動(dòng)機(jī)M=(Q,∑,δ,q0,F),它接受的語言定義為:
L(M)={w|d(q0,w)∩F非空}。定理3.2如果L被一個(gè)具有ε轉(zhuǎn)移的有窮自動(dòng)機(jī)接受,則L也被一個(gè)不具有ε轉(zhuǎn)移的NFA接受。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍45具有ε轉(zhuǎn)移的有窮自動(dòng)機(jī)證明(定理3.2)
設(shè)M=(Q,∑,δ,q0,F)是具有ε轉(zhuǎn)移的有窮自動(dòng)機(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。
下面我們將對(duì)∣x∣作歸納法來證明下式:
δ′(q0,x)=(q0,x)。
(3-2)
注意當(dāng)x=ε時(shí),(3-2)式不一定成立,因?yàn)棣摹?q0,ε)={q0},而
(q0,ε)=ε-CLOSURE({q0})。所以只能對(duì)∣x∣≥1證明(3-2)式成立。
歸納基礎(chǔ)
∣x∣=1,即x=a(a∈∑)。根據(jù)δ′的定義,(3-2)式顯然成立。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍46具有ε轉(zhuǎn)移的有窮自動(dòng)機(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)移的有窮自動(dòng)機(jī)
我們對(duì)(2)式的右部再進(jìn)一步推導(dǎo),得出 (q,a)=ε-CLOSURE(δ(ε-CLOSURE(q),a)) =ε-CLOSURE(δ(ε-CLOSURE(q),a)) =ε-CLOSURE(δ(q,a))。
(4)
其中最后一步簡(jiǎn)化是因?yàn)閷?duì)P=(q0,w)中的任何狀態(tài)q,ε-CLOSURE(q)已經(jīng)在P中,所以在對(duì)P中狀態(tài)求和的情況下,可以將ε-CLOSURE(q)用q來代替。
綜合(1),(2),(3),(4)式,最后得出
δ′(q0,wa)=(q0,wa)。
到這里,我們用歸納法證明了對(duì)一切x(∣x∣≥1),(3-2)式成立。01二月2023南京航空航天大學(xué)計(jì)算機(jī)學(xué)院胡軍48具有ε轉(zhuǎn)移的有窮自動(dòng)機(jī)為了完成定理的證明,我們要證:
對(duì)一切x∈∑*,δ′(q,x)∩F’非空,當(dāng)且僅當(dāng)(q,x)∩F非空。對(duì)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自
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- GB/T 44450-2024光學(xué)和光子學(xué)光學(xué)材料和元件0.78 μm~25 μm紅外光譜用光學(xué)材料特性
- 商業(yè)計(jì)劃書書范文(完整版)
- 商場(chǎng)工作總結(jié)13篇
- 高爐煉鐵工練習(xí)練習(xí)測(cè)試題附答案
- 語文統(tǒng)編版(2024)一年級(jí)上冊(cè)拼音14 教案
- 第2講 國(guó)內(nèi)常用文獻(xiàn)數(shù)據(jù)庫課件
- 學(xué)校傳染病防控課件
- 2024屆上海市建平實(shí)驗(yàn)中學(xué)高三5月單元檢測(cè)試題(月考)數(shù)學(xué)試題
- 第3章 圓的基本性質(zhì) 浙教版數(shù)學(xué)九年級(jí)上冊(cè)復(fù)習(xí)卷
- 5年中考3年模擬試卷初中道德與法治七年級(jí)下冊(cè)04專項(xiàng)素養(yǎng)綜合全練(四)
- 改變世界的機(jī)器 精益生產(chǎn)之道
- 手機(jī)攝影入門基礎(chǔ)知識(shí)教程
- 《反應(yīng)時(shí)間上》課件
- 教師培訓(xùn)課件教學(xué)設(shè)計(jì)與教案編寫
- 海事集裝箱裝箱檢查員考試題庫
- 【自考復(fù)習(xí)資料】00288社會(huì)調(diào)查方法(按章節(jié)整理)
- 小學(xué)生安全伴我成長(zhǎng)主題班會(huì)課件
- 口腔門診醫(yī)生晉升副高工作總結(jié)
- 混凝土質(zhì)量控制與強(qiáng)度評(píng)定培訓(xùn)課件
- 水利工程危險(xiǎn)源辨識(shí)清單全
- 第9課+隋唐時(shí)期的經(jīng)濟(jì)、科技與文化-【中職專用】《中國(guó)歷史》(高教版2023基礎(chǔ)模塊)
評(píng)論
0/150
提交評(píng)論