形式語(yǔ)言與自動(dòng)機(jī)有窮自動(dòng)機(jī)

1、1形式語(yǔ)言與自動(dòng)機(jī) 第三章 有窮自動(dòng)機(jī)南京航空航天大學(xué)南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 胡胡 軍軍2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍2第三章 有窮自動(dòng)機(jī)o 1.1 非形式化描述o 1.2 有窮自動(dòng)機(jī)的基本定義o 1.3 非確定的有窮自動(dòng)機(jī)o 1.4 具有轉(zhuǎn)移的有窮自動(dòng)機(jī)o 1.5 有窮自動(dòng)機(jī)的應(yīng)用 o 1.6 具有輸出的有窮自動(dòng)機(jī)（*)2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍31.1 有窮狀態(tài)系統(tǒng)o指針式鐘表共有12*60*60個(gè)狀態(tài)n 小時(shí)分鐘秒o圍棋共有3361個(gè)狀態(tài)n 每一個(gè)格子：（空，黑，白）；n 格子數(shù)量：19行19列

2、o某些電子產(chǎn)品中的開關(guān)電路， 具有n個(gè)門的開關(guān)網(wǎng)絡(luò)有2n種狀態(tài)o“網(wǎng)上購(gòu)物”系統(tǒng)（示例：）2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍4o 2007年圖靈獎(jiǎng)年圖靈獎(jiǎng) n 模型檢驗(yàn)（model checking）:基于自動(dòng)機(jī)理論的形式化方法(formal methods)E. ClarkEmersonSifakis2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍51.2 有窮自動(dòng)機(jī)的基本定義定義3.1 一個(gè)有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)(Finite Automata)簡(jiǎn)稱簡(jiǎn)稱FA，是一個(gè)五元組：M = (Q,q0,F)，其中（1）Q是有窮狀態(tài)集；（States）（2）是有窮的輸入

3、字母表 （Alphabet）（3）是轉(zhuǎn)移函數(shù)，它將QQ (全映射)；（Transiston function）（4）q0Q，是初始狀態(tài)；（Initial state）（5）F Q，是終結(jié)狀態(tài)集。（Accepting states）(終止?fàn)顟B(tài)，接受狀態(tài)) 上述定義的另一個(gè)說法：確定型的有窮自動(dòng)機(jī)確定型的有窮自動(dòng)機(jī)(Deterministic Finite Automata： DFA)2022年4月27日星期三南京航空航天大學(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)集輸

4、入01q0q1q2q0q1q2q2q2q1轉(zhuǎn)換函數(shù)表 d: *問題：?jiǎn)栴}： 1. 接受什么特征的字符串？接受什么特征的字符串？ 2. 狀態(tài)狀態(tài)q2起什么作用？起什么作用？2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍7這兩個(gè)DFA所接受的字符串集合分別是什么？DFA 例子q0q1baabS = a, bq0q1q2q3q4aaaaabbbbbS = a, b2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍8o 設(shè)計(jì)一個(gè)DFA(字母表為0,1),接受如下字符串：o 設(shè)計(jì)一個(gè)DFA (字母表為0,1),接受如下特征的字符串：最多有三個(gè)1. q0q1011q20q31q4+0,

5、 1010DFA 例子L = 010, 1qeq0q1q01q010qdie0, 10100, 11010, 12022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍9o 設(shè)計(jì)一個(gè)DFA(字母表為0,1),接受所有結(jié)尾是01的字符串。o 提示：DFA得記住 讀入字符串的最后兩位。DFA 例子qe01q0q1q00q10q01q11010100111002022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍10o 設(shè)計(jì)一個(gè)DFA(字母表為0,1),接受所有結(jié)尾是101的字符串。DFA 例子2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍11例3.1 給出一個(gè)有窮自動(dòng)機(jī)=(q0,

6、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 例子2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍12有窮自動(dòng)機(jī)的擴(kuò)充定義o定義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)。其中qQ，w*，a。o例如，對(duì)于例3.1中的有窮自動(dòng)機(jī)，就有：(q0,010)=( (q

7、0,01),0)=( (q0,0),1),0)=( (q0,),0),1),0)=(q0,0),1),0)= (q2,1),0)= (q3,0)= q1 。dddddddd2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍13有窮自動(dòng)機(jī)的基本定義o 從到 的擴(kuò)充是很自然的，就是 的特例（當(dāng)|x|=1時(shí)）。o 今后在提到FA的轉(zhuǎn)移函數(shù)時(shí)，不再?gòu)?qiáng)調(diào) 這種寫法，一律用表示，即的第二個(gè)變?cè)瓤梢允菃蝹€(gè)字符也可以是一個(gè)字符串。ddd2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍14有窮自動(dòng)機(jī)模型o開始時(shí)，“讀頭”指向帶上的第一個(gè)輸入符號(hào)，控制器中放的是FA的初始狀態(tài)。然后，依據(jù)轉(zhuǎn)移函

8、數(shù)做動(dòng)作：若控制器中的當(dāng)前狀態(tài)是q ，且“讀頭”指向帶上符號(hào)為a，則控制器中狀態(tài)將變成p=(q,a)，且“讀頭”向右移指向帶上下一個(gè)符號(hào)，如此可以繼續(xù)進(jìn)行下去。(注意：讀頭不能回頭，只能一直向右移動(dòng))*2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍15有窮自動(dòng)機(jī)的模型o定義 3.3 給出FA： M=(Q,q0,F)，若(q0,x)=pF (x*)，則稱字符串字符串x被被M接受接受。進(jìn)一步地，被M接受的全部字符串構(gòu)成的集合，稱為被有窮自動(dòng)機(jī)M接受的語(yǔ)言接受的語(yǔ)言，并記為L(zhǎng)(M)。用集合描述法就是 L(M)= x (q0,x)F。oFA所能接受的只是*的一部分子集，有很多*的子集是任何

9、FA都不能接受的。2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍16從給定集合構(gòu)造接受該集合的FAo例3.3： 設(shè)計(jì)一個(gè)接受能被5整除的二進(jìn)制數(shù)的FA Mo用qs表示初始狀態(tài)，用q0、q1、q2、q3、q4分別表示二進(jìn)制數(shù)被5整除時(shí)余0（即能被5整除，所以它是終結(jié)狀態(tài)。）、余1、余2、余3、余4的狀態(tài)。2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍17o一個(gè)FA(字母表為0,1),接受所有結(jié)尾是101的字符串。o能否給FA增加猜測(cè)選擇的能力？假設(shè)我們具有猜測(cè)何時(shí)輸入串還剩下三個(gè)字符的能力。1.3 非確定的有窮自動(dòng)機(jī)(NFA)qdie101還剩三個(gè)字符0102022年4月

10、27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍18NFAo 每個(gè)狀態(tài)對(duì)同樣的一個(gè)輸入字符，可能有0,1,或者多條轉(zhuǎn)換發(fā)生（猜測(cè)）.1010, 1q0q1q2q32022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍19NFA：可以進(jìn)行猜測(cè)選擇1010, 1q0q1q2q3o 狀態(tài) q0 有兩個(gè)標(biāo)記為 1 的轉(zhuǎn)換；o 讀入1, NFA可以選擇停留在q0 ，或者繼續(xù)往前到狀態(tài)q12022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍20NFA：可以進(jìn)行猜測(cè)選擇1010, 1q0q1q2q3o 狀態(tài)q1 對(duì)于輸入 1沒有相應(yīng)的轉(zhuǎn)換；o q1 上讀入1時(shí),NFA就運(yùn)行不下去了(die); 而讀入

11、 0時(shí)候, NFA可以繼續(xù)到狀態(tài)q2；o 狀態(tài)q2 類似的行為。2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍211010, 1q0q1q2q3o q3 沒有任何轉(zhuǎn)換出來；o q3 上如果讀入0,1, NFA也運(yùn)行進(jìn)入死狀態(tài)。NFA：可以進(jìn)行猜測(cè)選擇2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍22NFA： 猜測(cè)的能力1010, 1q0q1q2q3猜測(cè)是否已經(jīng)到了最后三位字符的位置了？如果是，則猜測(cè)最后三位字符應(yīng)該是與101相匹配判斷是否到達(dá)輸入字符串的最末端NFA的運(yùn)行過程中某個(gè)時(shí)刻是會(huì)的運(yùn)行過程中某個(gè)時(shí)刻是會(huì)同時(shí)處于多個(gè)狀態(tài)中同時(shí)處于多個(gè)狀態(tài)中，只要，只要輸入串輸入

12、串x結(jié)束時(shí)結(jié)束時(shí)NFA所處的多個(gè)狀態(tài)中所處的多個(gè)狀態(tài)中至少有一個(gè)是接受狀態(tài)至少有一個(gè)是接受狀態(tài)，就判斷就判斷NFA接受接受x。2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍23NFA的形式化定義o定義3.4 一個(gè)非確定的有窮自動(dòng)機(jī)(Nondeterministic Finite Automata)簡(jiǎn)記為NFA，是一個(gè)五元組M=(Q,q0 , F)其中Q、q0和F與確定的有窮自動(dòng)機(jī)的含意相同，只是轉(zhuǎn)移函數(shù)的定義不同，它是從Q2Q（Q的冪集）上的映射。o在FA中，的一般形式是(q,a)=p (q,pQ)，而在NFA中，的一般形式是(q,a)=p1,p2,pk(piQ,i=1,2,k)，

13、或(q,a)=（空集）。o在NFA中轉(zhuǎn)移函數(shù)的取值是一個(gè)狀態(tài)集，即使只有一個(gè)狀態(tài)p，也要寫成集合形式p。2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍24NFA的形式化定義o定義3.5 對(duì)于NFA M=(Q,q0 ,F)，它的擴(kuò)充轉(zhuǎn)移函數(shù) 是從Q*2Q的映射，具體定義如下：(1) (q,)=q,(2) (q,wa)=p |p(r,a),r (q,w)。o對(duì)于例3.4中的NFA， (q0,01001)的求值過程如下圖：dddd2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍25NFA接受的語(yǔ)言o定義3.7 給出NFA M=(Q,q0 , F)，若(q0,x)F非空（x*），

14、則稱字符串x被M接受接受。被NFA M接受的全體字符串稱為M接受的語(yǔ)言，記作L(M)。也就是 L(M)=x x*,且(q0,x)F非空非空。2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍26NFA與 DFA的等價(jià)o NFA 能識(shí)別（接受）DFA所識(shí)別（接受）的所有語(yǔ)言。（為什么？）o 反過來成立嗎？任一個(gè)NFA都能轉(zhuǎn)換成一個(gè)DFA，二者所識(shí)別的語(yǔ)言是相等的。YES2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍27NFA DFA: 直觀的理解100, 1q0q1q2NFA:DFA:1q0q0 or q11q0 or q210002022年4月27日星期三南京航空航天大學(xué)計(jì)

15、算機(jī)學(xué)院 胡軍28NFA DFA:子集構(gòu)造法(subset construction)100, 1q0q1q2NFA:DFA:q0, q1q0, q2q0, q1, q2q1, q2q0q1q2NFA中的任一個(gè)狀態(tài)子集都是所構(gòu)造的中的任一個(gè)狀態(tài)子集都是所構(gòu)造的DFA的一個(gè)狀態(tài)的一個(gè)狀態(tài) 2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍29NFA DFA: 狀態(tài)之間的轉(zhuǎn)換100, 1q0q1q2NFA:DFA:q0, q1q0, q2q0, q1, q2q1, q2q0q1q201010, 1010101010, 12022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍30NFA

16、DFA: 確定DFA接受狀態(tài)100, 1q0q1q2NFA:DFA:q0, q1q0, q2q0, q1, q2q1, q2q0q1q201010, 1010101010, 1DFA中包含中包含NFA接受狀態(tài)的子集狀態(tài)設(shè)為接受狀態(tài)的子集狀態(tài)設(shè)為accepting2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍31NFA DFA: 消除無用的狀態(tài) 100, 1q0q1q2NFA:DFA:q0, q1q0, q2q0010101q0, q1, q2010q1, q2q1q201, 1010, 1將將DFA中不可達(dá)的狀態(tài)消除掉。中不可達(dá)的狀態(tài)消除掉。2022年4月27日星期三南京航空航天大

17、學(xué)計(jì)算機(jī)學(xué)院 胡軍32子集構(gòu)造法的一般步驟NFADFA狀態(tài)q0, q1, , qn, q0, q1, q0,q1, , q0,qn每個(gè)狀態(tài)都是每個(gè)狀態(tài)都是NFA的一個(gè)子集的一個(gè)子集。初始狀態(tài)q0q0轉(zhuǎn)換dd(qi1,qik, a) = d(qi1, a) d(qik, a)接受狀態(tài)F Q F = S: S 包含 F中至少一個(gè)狀中至少一個(gè)狀態(tài)態(tài) 2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍33NFA-DFA等價(jià)性的形式化證明o 定理定理3.1 設(shè)設(shè)L是被一個(gè)非確定的有窮自動(dòng)機(jī)接受的語(yǔ)是被一個(gè)非確定的有窮自動(dòng)機(jī)接受的語(yǔ)言，則存在一個(gè)確定的有窮自動(dòng)機(jī)也接受這個(gè)語(yǔ)言言，則存在一個(gè)確定的有

18、窮自動(dòng)機(jī)也接受這個(gè)語(yǔ)言L。證明 設(shè) M=(Q,q0 , F)是一個(gè)接受L的NFA，現(xiàn)在構(gòu)造一個(gè)DFA M=(Q,q0,F)，其中：nQ=2Q, 即Q的每一個(gè)子集作為Q的一個(gè)狀態(tài)，若子集為q1,q2,qk，則 Q中狀態(tài)記為q1,q2,qk；nq0=q0；n F 2Q:F的每個(gè)元素至少包含F(xiàn)中的一個(gè)狀態(tài)；n的定義為： (q1,q2,qi,a)= p1,p2,pj 當(dāng)且僅當(dāng) （q1,q2,qi,a）= p1,p2,pj (a)。2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍34NFA-DFA等價(jià)性的形式化證明o證明L(M)=L(M)=L。先證一個(gè)更一般的命題：(q0,x)=q1,q2,q

19、k iff (q0,x)=q1,q2,qk （x*）。(3-1)對(duì)對(duì)x的長(zhǎng)度的長(zhǎng)度 x 用歸納來證明用歸納來證明。歸納基礎(chǔ)歸納基礎(chǔ) x =0，即x=。因?yàn)?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)橐环矫?q0,xa)=(q0,x),a)， （1）另一方面(q0,xa)=(q0,x),a) 。 （2）2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍35NFA-DFA等價(jià)性的形式化證明o由歸納法假設(shè)，因?yàn)閤長(zhǎng)度為m，以下（3）式成立，即(q0,

20、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,qkF,則q1,q2,qk 至少有一個(gè)在F中；反之，若q1,q2,qk中有一個(gè)狀態(tài)在F中，則q1,q2,qkF。這就是說，M和M接受的語(yǔ)言是相同的，即L(M)=L(M)=L。定理證畢。o這個(gè)定理不僅證明了NFA和DFA兩類自動(dòng)機(jī)

21、的等價(jià)性，而且還給出了從一給出了從一個(gè)個(gè)NFA構(gòu)造與它等價(jià)的構(gòu)造與它等價(jià)的DFA的具體步驟，這種證明稱為構(gòu)造性的證明方法。的具體步驟，這種證明稱為構(gòu)造性的證明方法。2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍36NFA-DFA等價(jià)構(gòu)造的例子o例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。o根據(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

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

23、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。2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍38子集構(gòu)造法的實(shí)際實(shí)現(xiàn)第四步第四步 處理新增加的兩個(gè)狀態(tài)處理新增加的兩個(gè)狀

24、態(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)處理新增加的兩個(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。o到這一步為止，不再增加新的狀態(tài)

25、，所求的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中去。2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍391.4 具有轉(zhuǎn)移的有窮自動(dòng)機(jī)o該自動(dòng)機(jī)的狀態(tài)集為q0,q1,q2,輸入字母表為0，1，2。o由初始狀態(tài)q0開始，當(dāng)接到輸入符號(hào)0時(shí)，轉(zhuǎn)移到狀態(tài)q0本身，但不遇到任何符號(hào)（用表示）即可從q0轉(zhuǎn)移到q1，從q1到q2也有類似的情況。o這種自動(dòng)機(jī)在NFA的基礎(chǔ)上又增加了一種不確定性又增加了一種不確定性，它不僅在某些情況下有更簡(jiǎn)潔表達(dá)能力，而且在證明一些

26、理論問題時(shí)，更是不可缺少的工具。2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍40另一個(gè)-NFA的例子o 設(shè)計(jì)一個(gè)NFA識(shí)別語(yǔ)言：字符串要么包含偶數(shù)個(gè)0，或奇數(shù)個(gè)1；r0r11100even number of 0ss0s10011odd number of 1sq0eee-transitions不需要讀入任何符號(hào)即可發(fā)生狀態(tài)轉(zhuǎn)換2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍41具有轉(zhuǎn)移的有窮自動(dòng)機(jī)o定義3.8 具有轉(zhuǎn)移的有窮自動(dòng)機(jī)（簡(jiǎn)稱-NFA）是一個(gè)五元組M=(Q,q0 , F)其中Q,q0,F的含義與一般的DFA或 NFA相同，而是從 Q()2Q的映射的映射。o對(duì)

27、于前面給出的自動(dòng)機(jī)，它的函數(shù)是：(q0,0)=q0， (q0,)=q1，(q1,1)=q1， (q1,)=q2，(q2,2)=q2。o凡是沒有寫出的，如(q0,1)，(q1,2)，(q2,1)等等，都是沒有定義的，這和一般的NFA相同。2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍42具有轉(zhuǎn)移的有窮自動(dòng)機(jī)o定義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)不再增加

28、為止。進(jìn)一步地，對(duì)于狀態(tài)集P的-CLOSURE，我們規(guī)定-CLOSURE(P) = -CLOSURE(q)。o所謂-CLOSURE(q)，從轉(zhuǎn)移圖上看，就是從狀態(tài)從狀態(tài)q出發(fā)，沿著標(biāo)有出發(fā)，沿著標(biāo)有的有的有向邊所能達(dá)到的一切狀態(tài)所構(gòu)成的集合（包括狀態(tài)向邊所能達(dá)到的一切狀態(tài)所構(gòu)成的集合（包括狀態(tài)q本身）本身）。所謂-CLOSURE(P)，就是對(duì)P中一切狀態(tài)q，分別求出-CLOSURE(q)，然后將這些狀態(tài)集求并而得的狀態(tài)集。o例如，-CLOSURE(q0)=q0,q1,q2,-CLOSURE(q1)=q1,q2。Pq2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍43具有轉(zhuǎn)移的有窮自動(dòng)

29、機(jī)o定義3.10 對(duì)于一個(gè)具有轉(zhuǎn)移的有窮自動(dòng)機(jī)，它的擴(kuò)充轉(zhuǎn)移函數(shù)擴(kuò)充轉(zhuǎn)移函數(shù) 定義如下：（1） (q,)=-CLOSURE(q),（2） (q,wa)=-CLOSURE(P),P = (r,a)。其中qQ, a, w*。o例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。ddddddd)w, q(r d2022年4月27日星期三

30、南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍44具有轉(zhuǎn)移的有窮自動(dòng)機(jī)o定義3.11 對(duì)于一個(gè)具有轉(zhuǎn)移的有窮自動(dòng)機(jī) M=(Q,q0 , F)，它接受的語(yǔ)言定義為：L(M)=w | d(q0,w)F非空非空。o定理定理3.2 如果如果L被一個(gè)具有被一個(gè)具有轉(zhuǎn)移的有窮自動(dòng)機(jī)接受，則轉(zhuǎn)移的有窮自動(dòng)機(jī)接受，則L也被一也被一個(gè)不具有個(gè)不具有轉(zhuǎn)移的轉(zhuǎn)移的NFA接受。接受。2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍45具有轉(zhuǎn)移的有窮自動(dòng)機(jī)o證明(定理定理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)=

31、(q,a), qQ, a。如果-CLOSURE(q0)F非空，則F=Fq0；否則，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）式顯然成立。dd2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍46具有轉(zhuǎn)移的有窮自動(dòng)機(jī)o歸納步驟 設(shè) x =m (m1)時(shí)，（3-2）式成立，現(xiàn)在要證當(dāng) x =m+1時(shí)，（3-2）式成立。設(shè)x = wa (a, w

32、 =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)。 ddddddPqPqPq2022年4月27日星期三南京航空航天大學(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)化

33、是因?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）式成立。PqPqPqPqddd2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍48具有轉(zhuǎn)移的有窮自動(dòng)機(jī)o為了完成定理的證明，我們要證：對(duì)一切x*, (q,x)F非空，當(dāng)且僅當(dāng) (q,x)F非空。o對(duì)x=和x分兩種情況考慮。首先，當(dāng)x=時(shí)，若M接受它，則-CLOSURE(q0)至少包含F(xiàn)中的一個(gè)狀態(tài)，由F

34、的定義，則q0在F中，那么M也接受。反之，若M接受，因?yàn)镸是一個(gè)不具有轉(zhuǎn)移的NFA，則q0必須在F中。進(jìn)一步分析，若q0也在F中，則M自然接受；若q0不在F中，由F的定義，則-CLOSURE(q0)至少包含F(xiàn)中的一個(gè)狀態(tài)，這也表示M接受。d2022年4月27日星期三南京航空航天大學(xué)計(jì)算機(jī)學(xué)院 胡軍49具有轉(zhuǎn)移的有窮自動(dòng)機(jī)o再考慮x的情況。設(shè)M接受x，即 (q0,x)包含F(xiàn)中的一個(gè)狀態(tài)，則由（3-2）式，(q0,x)也包含F(xiàn)中的同一個(gè)狀態(tài)，而此狀態(tài)自然也在F中，即M也接受x 。反之，設(shè)M接受x，若(q0,x)包含F(xiàn)中的非q0狀態(tài)（F中的一個(gè)狀態(tài)），則由（3-2）式， (q0,x)也包含F(xiàn)中的這個(gè)狀態(tài)，即M也接受x 。但是，若