形式語言與自動機理論--第三章 有限狀態(tài)自動機-2（第七周）

1、第第3章章 有窮狀態(tài)自動機有窮狀態(tài)自動機 1.語言的識別語言的識別2.有窮狀態(tài)自動機有窮狀態(tài)自動機3.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機4.帶空轉移的有窮狀態(tài)自動機帶空轉移的有窮狀態(tài)自動機5.FA是正則語言的識別器是正則語言的識別器6.FA的一些變形的一些變形7.小結小結13.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機 確定的有窮狀態(tài)自動機確定的有窮狀態(tài)自動機DFA:在任一狀態(tài)下給在任一狀態(tài)下給定輸入，下一個跳轉狀態(tài)是唯一的。定輸入，下一個跳轉狀態(tài)是唯一的。 另一種構造自動機的可能：另一種構造自動機的可能：希望是接受希望是接受L=L=x|x0，1*，且，且x含有子串含有子串00或或

2、11的的FA：23.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機希望是接受希望是接受x|x0，1*，且，且x 的倒數(shù)第的倒數(shù)第10個字符為個字符為1的的FA如下如下 ：33.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機這兩個圖所給的這兩個圖所給的“FA”與前面我們所定義的與前面我們所定義的D DFA的區(qū)的區(qū)別在于：別在于： 并不是對于所有的并不是對于所有的(q，a)Q,(q，a)都有都有一個狀態(tài)與它對應；一個狀態(tài)與它對應； 并不是對于所有的并不是對于所有的(q，a)Q,(q，a)只對只對應一個狀態(tài)。應一個狀態(tài)。 “FA”在任意時刻可以處于有窮多個狀態(tài)。在任意時刻可以處于有窮多個狀態(tài)。 “FA”

3、具有具有“智能智能”。43.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機定義定義3-7：不確定的有窮狀態(tài)自動機：不確定的有窮狀態(tài)自動機(non-deterministic finite automaton ,NFA) M是一個五元組是一個五元組M=(Q，q0，F(xiàn)) Q、q0、F的意義同的意義同DFA。：Q2Q，對，對 (q，a)Q，(q，a)= p1，p2，pm表示表示M在狀態(tài)在狀態(tài)q讀入字符讀入字符a，可以選擇地將狀，可以選擇地將狀態(tài)變成態(tài)變成p1、或者、或者p2、或者、或者pm ，并將讀頭向右移動一，并將讀頭向右移動一個帶方格而指向輸入字符串的下一個字符。個帶方格而指向輸入字符串的下一個字

4、符。 53.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機FA的狀態(tài)轉移圖、的狀態(tài)轉移圖、FA的狀態(tài)對應的等價類、的狀態(tài)對應的等價類、FA的即時描的即時描述對述對NFA都有效。都有效。接受接受x|x0，1*，且，且x含有子串含有子串00或或11的的FA對應的移動對應的移動函數(shù)定義表。函數(shù)定義表。63.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機狀態(tài)說明狀態(tài)說明狀態(tài)狀態(tài)輸入字符輸入字符01啟動狀態(tài)啟動狀態(tài)q0q0，q1 q0，q2 q1q3 q2q3終止狀態(tài)終止狀態(tài)q3q3q373.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機接受接受x|x0，1*，且，且x 的倒數(shù)第的倒數(shù)第10個字符為個字符為1

5、的的FA對應的移動函數(shù)定義表。對應的移動函數(shù)定義表。83.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機狀態(tài)說明狀態(tài)說明狀態(tài)狀態(tài)輸入字符輸入字符01啟動狀態(tài)啟動狀態(tài)q0q0 q0，q1 q1q2q2 q2q3q3 q3q4q4 q4q5q5 q5q6q6 q6q7q7 q7q8q8 q8q9 q9 q9q10 q10終止狀態(tài)終止狀態(tài)q1093.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機將將擴充為擴充為QQ2:*對任意的對任意的qQ，w*，a，定義，定義 a)，(rp，使得w)，(q r|p),() 2(),() 1 (waqqq103.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機a)(q,a)

6、(q,p|pa)(r,p,|pa)(r,p),(q, r|p),(),(qraqaq和關于和關于DFADFA的結論一樣，兩值相同，也不的結論一樣，兩值相同，也不用區(qū)分這兩個符號。用區(qū)分這兩個符號。 113.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機進一步擴充進一步擴充的定義域：的定義域：2Q*2Q。對任意的。對任意的P Q，w*PqwqwP),(),(123.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機由于，對由于，對 (q，w)Q* ),(),(),(wqwqwqqq所以，不一定嚴格地區(qū)分所以，不一定嚴格地區(qū)分的第的第1個分量是一個個分量是一個狀態(tài)還是一個含有一個元素的集合。狀態(tài)還是一個含

7、有一個元素的集合。 133.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機對任意的對任意的qQ，w*，a： (q，wa)=(q，w)，a) 對輸入字符串對輸入字符串a(chǎn)1a2an (q，a1a2an)=(q, a1), a2)，)，an) 。143.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機定義定義3-8：M接受接受(識別識別)的語言的語言 設設M=(Q，q0，F(xiàn)) 是一個是一個NFA，對于對于 x*，如果如果(q0，x) F，則稱，則稱x被被M接受，如果接受，如果(q0，x)F=，則稱，則稱M不不接受接受x。L(M)=x| x*且且(q0，x) F，稱為稱為由由M接受接受(識別識別)的語言。的

8、語言。 153.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機對于一個輸入字符，對于一個輸入字符，NFA與與DFA的差異是前者可以的差異是前者可以進入若干個狀態(tài)，而后者只能進入一個惟一的狀態(tài)。進入若干個狀態(tài)，而后者只能進入一個惟一的狀態(tài)。雖然從雖然從DFA看待問題的角度來說，看待問題的角度來說，NFA在某一時刻在某一時刻同時進入若干個狀態(tài)，但是，這若干個狀態(tài)合在一同時進入若干個狀態(tài)，但是，這若干個狀態(tài)合在一起的起的“總效果總效果”相當于它處于這些狀態(tài)對應的一個相當于它處于這些狀態(tài)對應的一個“綜合狀態(tài)綜合狀態(tài)”。因此，我們考慮讓因此，我們考慮讓DFA用一個狀態(tài)去對應用一個狀態(tài)去對應NFA的一的一組

9、狀態(tài)。組狀態(tài)。 163.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機NFA M1=(Q，1，q0，F(xiàn)1)與與DFA M2=(Q2，2，q0，F(xiàn)2)的對應關系：的對應關系：NFA從開始狀態(tài)從開始狀態(tài)q0啟動，我們就讓相應的啟動，我們就讓相應的DFA從狀態(tài)從狀態(tài)q0啟動。所以啟動。所以q0= q0。 對于對于NFA 的一個狀態(tài)組的一個狀態(tài)組q1，q2，qn，如果，如果NFA在此狀態(tài)組時讀入字符在此狀態(tài)組時讀入字符a后可以進入狀態(tài)組后可以進入狀態(tài)組p1，p2，pm,則讓相應的則讓相應的DFA在狀態(tài)在狀態(tài)q1，q2，qn讀入字符讀入字符a時，進入狀態(tài)時，進入狀態(tài)p1，p2，pm。 173.不確定的有窮

10、狀態(tài)自動機不確定的有窮狀態(tài)自動機定理定理 3-1 NFA與與DFA等價。等價。證明：證明：只需證明對于任意給定的只需證明對于任意給定的NFA，存在與之等價的，存在與之等價的DFA。(1)(1)構造與構造與NFA M1等價的等價的DFA M2 。 M1=(Q，1，q0，F(xiàn)1) M2=(Q2，2，q0，F(xiàn)2) Q2=2Q F2=p1，p2，pm|p1，p2，pm Q&p1，p2，pmF1 183.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機2(q1，q2，qn，a)=p1，p2，pm1(q1，q2，qn，a)= p1，p2，pm (2) 證明證明1(q0，x)= p1，p2，pm 2(q0

11、，x)=p1，p2，pm。 設設x*，施歸納于，施歸納于|x| x=，1(q0，)= q0,2(q0，)=q0 193.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機設當設當|x|=n是結論成立。下面證明當是結論成立。下面證明當|x|=n+1是結論也成立。是結論也成立。不妨設不妨設x=wa，|w|=n，a 1 1(q(q0 0，wa)=wa)=1 1( (1 1(q(q0 0，w)w)，a)a) = =1 1(q(q1 1，q q2 2，q qn n ，a)a) =p=p1 1，p p2 2，p pm m 由歸納假設，由歸納假設， 1 1(q(q0 0，w)=qw)=q1 1，q q2 2，q

12、qn n 2 2(q(q0 0 ，w)=qw)=q1 1，q q2 2，q qn n 203.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機根據(jù)根據(jù)2的定義，的定義， 2(q1，q2，qn，a)=p1，p2，pm 1(q1，q2，qn，a)=p1，p2，pm 所以，所以，2(q0，wa)=2(2(q0，w)，a) =2(q1，q2，qn，a) =p1，p2，pm 213.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機 故，如果故，如果1(q0，wa)= p1，p2，pm則必有則必有2(q0，wa)= p1，p2，pm。由上述推導可知，反向的推導也成立。這就是說，由上述推導可知，反向的推導也成立。這

13、就是說，結論對結論對|x|=n+1也成立。也成立。 由歸納法原理，結論對由歸納法原理，結論對 x*成立。成立。 223.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機(3) 證明證明L(M1)=L(M2) 設設xL(M1)，且，且1(q0，x)= p1，p2，pm，從而從而1(q0，x)F1,這就是說，這就是說， p1，p2，pmF1，由由F2的定義，的定義，p1，p2，pmF2。233.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機再由再由(2)知，知，2(q0，x)=p1，p2，pm所以，所以，xL(M2)。故。故L(M1) L(M2)。 反過來推，可得反過來推，可得L(M2) L(M1)。從

14、而從而L(M1)=L(M2)得證。得證。 綜上所述，定理成立。綜上所述，定理成立。24例例 3-7 圖圖3-9所示的所示的NFA 對應的對應的DFA的狀的狀態(tài)轉移函數(shù)如表態(tài)轉移函數(shù)如表3-7所示。所示。 圖圖3-925表表3-7 狀態(tài)轉移函數(shù)狀態(tài)轉移函數(shù)狀態(tài)說明狀態(tài)說明狀態(tài)狀態(tài)輸入字符輸入字符01啟動啟動 q0q0,q1q0,q2 q1q3 q2q3終止終止 q3q3q3 q0,q1q0,q1,q3q0,q2 q0,q2q0,q1q0,q2,q3終止終止 q0,q3q0,q1,q3q0,q2,q3 q1,q2q3q3終止終止 q1,q3q3q3終止終止 q2,q3q3q3 q0,q1,q2q0

15、,q1,q3q0,q2,q3終止終止 q0,q1,q3q0,q1,q3q0,q2,q3終止終止 q0,q2,q3q0,q1,q3q0,q2,q3終止終止 q1,q2,q3q3q3終止終止 q0,q1,q2,q3q0,q1,q3q0,q2,q3 263.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機不可達狀態(tài)不可達狀態(tài)(inaccessible state)(inaccessible state)：不存在從不存在從qq0 0 對應的頂點出發(fā)，到達該狀態(tài)對應的頂點的路。我對應的頂點出發(fā)，到達該狀態(tài)對應的頂點的路。我們稱此狀態(tài)從開始狀態(tài)是不可達的。們稱此狀態(tài)從開始狀態(tài)是不可達的。表表3-7中，所有標記

16、中，所有標記“ ”的狀態(tài)是從開始狀態(tài)可達的狀態(tài)是從開始狀態(tài)可達的，其他是不可達的的，其他是不可達的無用的。無用的。 273.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機構造給定構造給定NFA等價的等價的DFA策略策略（1 1）先只把開始狀態(tài)）先只把開始狀態(tài)q0填入表的狀態(tài)列中，計算填入表的狀態(tài)列中，計算在在q0狀態(tài)下各輸入的輸出；將得到的新狀態(tài)填入狀狀態(tài)下各輸入的輸出；將得到的新狀態(tài)填入狀態(tài)列表中；態(tài)列表中；（2 2）如果狀態(tài)列表有未處理的狀態(tài)，則任選一個未）如果狀態(tài)列表有未處理的狀態(tài)，則任選一個未處理的狀態(tài)處理的狀態(tài)q1，q2，qn，對，對中的每個字符中的每個字符a，計算計算(q1，q2，q

17、n，a)，并填入相應的表項中，并填入相應的表項中（3 3）如果）如果(q1，q2，qn，a)在表的狀態(tài)列未出在表的狀態(tài)列未出現(xiàn)過，則將它填入表的狀態(tài)列?，F(xiàn)過，則將它填入表的狀態(tài)列。（4 4）如此重復下去，直到表的狀態(tài)列中不存在未處）如此重復下去，直到表的狀態(tài)列中不存在未處理的狀態(tài)。理的狀態(tài)。 283.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機圖圖 3-11 圖圖3-9所示所示NFA的等價的等價DFA 294. 帶空移動的有窮狀態(tài)自動機帶空移動的有窮狀態(tài)自動機 接受語言接受語言0n1m2k|n，m，k0的的NFA 304. 帶空移動的有窮狀態(tài)自動機帶空移動的有窮狀態(tài)自動機 接受語言接受語言0n

18、1m2k|n，m，k0的的NFA是否可以構造成是否可以構造成下圖所示的下圖所示的“-NFA ”？ 其構造顯然比圖其構造顯然比圖1-13所示的所示的NFA更容易。更容易。當然還希望它們是等價的。當然還希望它們是等價的。314. 帶空移動的有窮狀態(tài)自動機帶空移動的有窮狀態(tài)自動機 定義定義3-9：帶空移動的不確定的有窮狀態(tài)自動機：帶空移動的不確定的有窮狀態(tài)自動機(non-deterministic finite automaton with -moves,-NFA)M=(Q，q0，F(xiàn))，Q、q0、F的意義同的意義同DFA。 ：Q()2Q 324. 帶空移動的有窮狀態(tài)自動機帶空移動的有窮狀態(tài)自動機 非

19、空移動非空移動 (q，a)Q(q，a)= p1，p2，pm表示表示M在狀態(tài)在狀態(tài)q讀入字符讀入字符a，可以選擇地，可以選擇地將狀態(tài)變成將狀態(tài)變成p1、p2、或者或者pm ，并將讀，并將讀頭向右移動一個帶方格而指向輸入字符頭向右移動一個帶方格而指向輸入字符串的下一個字符。串的下一個字符。334. 帶空移動的有窮狀態(tài)自動機帶空移動的有窮狀態(tài)自動機 空移動空移動 qQ(q，)= p1，p2，pm表示表示M在狀態(tài)在狀態(tài)q不讀入任何字符，可以不讀入任何字符，可以選擇地將狀態(tài)變成選擇地將狀態(tài)變成p1、p2、或者或者pm 。也可以叫做也可以叫做M在狀態(tài)在狀態(tài)q做一個空移動做一個空移動(又又可以稱為可以稱為移

20、動移動)，并且選擇地將狀態(tài)變，并且選擇地將狀態(tài)變成成p1、p2、或者或者pm。344. 帶空移動的有窮狀態(tài)自動機帶空移動的有窮狀態(tài)自動機 進一步擴充進一步擴充的定義域：的定義域：2Q*2Q。對任意的。對任意的P Q，w* 。對任意的對任意的qQ，w*，a。 -CLOSURE(q)=p|從從q到到p有一條標記為有一條標記為的路的路。定義為從定義為從 q 經(jīng)所有的經(jīng)所有的路徑可以到達的狀態(tài)（包括路徑可以到達的狀態(tài)（包括q自身）自身） PppCLOSUREPCLOSURE)()()2(354. 帶空移動的有窮狀態(tài)自動機帶空移動的有窮狀態(tài)自動機)(),() 3(qCLOSUREq),(),(),(),

21、(|)(),()4(wqrararpwqrpPPCLOSUREwaq使得36 4. 帶空移動的有窮狀態(tài)自動機帶空移動的有窮狀態(tài)自動機進一步擴展移動函數(shù)：進一步擴展移動函數(shù)：2 Q2Q 。 對任意對任意(P，a)2 Q。 PqaqaP),(),()5(PqwqwP),(),()6(374. 帶空移動的有窮狀態(tài)自動機帶空移動的有窮狀態(tài)自動機在在-NFA中，對任意中，對任意a，qQ，),(),(aqaq需要嚴格區(qū)分。需要嚴格區(qū)分。38圖圖3-14 所示所示-NFA狀狀態(tài)態(tài) 012012q0 q1 q0q0,q1,q2q0,q1,q2q1,q2q2q1 q2 q1q1,q2q1,q2q2q2 q2q2q2394. 帶空移動的有窮狀態(tài)自動機帶空移動的有窮狀態(tài)自動機定義定義3-10：M接受接受