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

1、第第3章章 有窮狀態(tài)自動機有窮狀態(tài)自動機 1.語言的識別語言的識別2.有窮狀態(tài)自動機有窮狀態(tài)自動機3.不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機4.帶空轉(zhuǎn)移的有窮狀態(tài)自動機帶空轉(zhuǎn)移的有窮狀態(tài)自動機5.FA是正則語言的識別器是正則語言的識別器6.FA的一些變形的一些變形7.小結(jié)小結(jié)15. FA是正則語言的識別器是正則語言的識別器對于任意正則語言對于任意正則語言L，都有一個滿足定理，都有一個滿足定理2-1的正則的正則文法文法G=（V,T,P,S），使得），使得L=L（G）。）。由于由于G是右線性的，除了空產(chǎn)生式外，每個產(chǎn)生式是右線性的，除了空產(chǎn)生式外，每個產(chǎn)生式的右部有且僅有一個終極符號。的右部

2、有且僅有一個終極符號。L中任意句子中任意句子a1a2an在推導時有如下特征：在推導時有如下特征：從從G的開始符號的開始符號S開始，除了開始，除了a1a2an外外，每個每個句型中有且僅有一個語法變量，而且此語法變量總句型中有且僅有一個語法變量，而且此語法變量總是句型的尾字符，因此，句型中的終極符號是依據(jù)是句型的尾字符，因此，句型中的終極符號是依據(jù)它被推導出來的先后順序它被推導出來的先后順序a1a2an依次排列的。依次排列的。25. FA是正則語言的識別器是正則語言的識別器 G的每步推導產(chǎn)生且僅能產(chǎn)生的每步推導產(chǎn)生且僅能產(chǎn)生一個終極符號：第一個終極符號：第i步產(chǎn)生終極符號步產(chǎn)生終極符號ai。 使用

3、形如使用形如AaB的產(chǎn)生式的推導，相當于是變的產(chǎn)生式的推導，相當于是變量量A產(chǎn)生出產(chǎn)生出aB，而，而B負責后續(xù)字符的產(chǎn)生。負責后續(xù)字符的產(chǎn)生。 使用形如使用形如Aa的產(chǎn)生式的推導，相當于是變量的產(chǎn)生式的推導，相當于是變量A產(chǎn)生產(chǎn)生a后，整個推導就結(jié)束了。后，整個推導就結(jié)束了。35. FA是正則語言的識別器是正則語言的識別器 A0 a1A1 對應(yīng)產(chǎn)生式對應(yīng)產(chǎn)生式A0 a1A1 a1a2A2對應(yīng)產(chǎn)生式對應(yīng)產(chǎn)生式A1 a2A2 a1a2an-1An-1對應(yīng)產(chǎn)生式對應(yīng)產(chǎn)生式An-2 an-1An-1 a1a2an-1an對應(yīng)產(chǎn)生式對應(yīng)產(chǎn)生式An-1 an45. FA是正則語言的識別器是正則語言的識別器

4、如果存在一個如果存在一個DFA M=(Q，q0，F(xiàn))，處理，處理句子句子a1a2an的特性。的特性。 M按照句子按照句子a1a2an中字符的出現(xiàn)順序，從開始中字符的出現(xiàn)順序，從開始狀態(tài)狀態(tài)q0開始，依次處理字符開始，依次處理字符a1、a2、an，在這，在這個處理過程中，每處理一的字符進入一個狀態(tài)，最個處理過程中，每處理一的字符進入一個狀態(tài)，最后停止在某個終止狀態(tài)。后停止在某個終止狀態(tài)。 55. FA是正則語言的識別器是正則語言的識別器 它每次處理且僅處理一個字符：第它每次處理且僅處理一個字符：第i步處理輸入字步處理輸入字符符ai。 對應(yīng)于使用對應(yīng)于使用(q，a)=p的狀態(tài)轉(zhuǎn)移函數(shù)的處理，的狀態(tài)

5、轉(zhuǎn)移函數(shù)的處理，相當于是在狀態(tài)相當于是在狀態(tài)q完成對完成對a的處理，然后由的處理，然后由p接下去接下去實現(xiàn)對后續(xù)字符的處理。實現(xiàn)對后續(xù)字符的處理。 當當(q，a)=pF，且，且a是輸入串的最后一個字符是輸入串的最后一個字符時，時，M完成對此輸入串的處理。完成對此輸入串的處理。 65. FA是正則語言的識別器是正則語言的識別器q0 a1a2an-1ana1q1 a2an-1an對應(yīng)對應(yīng)(q0，a1)=q1a1a2q2an-1an對應(yīng)對應(yīng)(q1，a2)=q2a1a2an-1qn-1an對應(yīng)對應(yīng)(qn-2，an-1)=qn-1a1a2an-1anqn對應(yīng)對應(yīng)(qn-1，an)=qn 75. FA是正

6、則語言的識別器是正則語言的識別器其中其中qn為為M的終止狀態(tài)?？紤]根據(jù)的終止狀態(tài)?？紤]根據(jù)a1、a2、an，讓讓A0與與q0對應(yīng)、對應(yīng)、A1與與q1對應(yīng)、對應(yīng)、A2與與q2對應(yīng)、對應(yīng)、An-2與與qn-2對應(yīng)、對應(yīng)、An-1與與qn-1對應(yīng)。這樣，就有希望對應(yīng)。這樣，就有希望得到滿足定理得到滿足定理2-4-1的正則文法的推導與的正則文法的推導與DFA的互的互相模擬的方式。相模擬的方式。 85. FA是正則語言的識別器是正則語言的識別器定理定理 3-3 FA接受的語言是正則語言。接受的語言是正則語言。證明：證明：(1) 構(gòu)造。構(gòu)造?；舅枷胧亲尰舅枷胧亲孯G的派生對應(yīng)的派生對應(yīng)DFA的移動。的

7、移動。 設(shè)設(shè)DFA M=(Q，q0，F(xiàn))，取右線性文法取右線性文法 G=(Q，P，q0)， P=qap|(q，a)=pqa|(q，a)=pF95. FA是正則語言的識別器是正則語言的識別器（2）證明證明 L(G)=L(M)-。對于對于a1a2an-1an+，q0+ a1a2an-1an q0 a1q1，q1 a2q2，qn-2 an-1qn-1，qn-1 anP (q0，a1)=q1，(q1，a2)=q2，(qn-2，an-1)=qn-1，(qn-1，an)=qn，且，且qnF (q0，a1a2an-1an)= qnF a1a2an-1anL(M) 105. FA是正則語言的識別器是正則語言的

8、識別器（3）關(guān)于關(guān)于句子。句子。 如果如果q0 F，則，則 L(M)，L(G)=L(M)。如果如果q0F，則由定理，則由定理2-6和定理和定理2-7，存在正則文法，存在正則文法G，使得，使得L(G)=L(G) =L(M)。綜上所述，對于任意綜上所述，對于任意DFA M，存在正則文法，存在正則文法G，使，使得得L(G)=L(M)。定理得證。定理得證。 115. FA是正則語言的識別器是正則語言的識別器例例 3-9 與圖與圖3-8 所給所給DFA等價的正則文法等價的正則文法qs0|0q0|1q1q00|0q0|1q1q10q2|1|1q0q20q1|1q2125. FA是正則語言的識別器是正則語言

9、的識別器與圖與圖3-7 所給的所給的DFA等價的等價的正則文法正則文法 q00q1|1qt|2qtq10q1|1q2|2qtq20qt|1q2|2q3|2 q30qt|1qt|2q3|2qt 0qt|1qt|2qt 13去掉陷阱狀態(tài)去掉陷阱狀態(tài)q00q1q10q1|1q2q21q2|2q3|2 q32q3|2 5. FA是正則語言的識別器是正則語言的識別器定理定理3-4 正則語言可以由正則語言可以由FA接受。接受。 證明：證明：（1）構(gòu)造。）構(gòu)造。基本思想：讓基本思想：讓FA模擬模擬RG的派生。的派生。設(shè)設(shè)G=(V，T，P，S)，且，且 L(G)，取取FA M=( VZ，T，S，Z)，Z V。

10、145. FA是正則語言的識別器是正則語言的識別器對對 (a，A)TV B|AaBPZ如果如果AaP(A，a)= B|AaBP如果如果Aa P 用用B(A，a)與產(chǎn)生式與產(chǎn)生式AaB對應(yīng)對應(yīng) 用用Z(A，a)與產(chǎn)生式與產(chǎn)生式Aa對應(yīng)。對應(yīng)。155. FA是正則語言的識別器是正則語言的識別器（2）證明證明L(M)=L(G)對于對于a1a2an-1anT+， a1a2an-1anL(G) S+ a1a2an-1an Sa1A1 a1a2A2 a1a2an-1An-1 a1a2an-1an Sa1A1，A1a2A2，An-2an-1An-1，An-1anP165. FA是正則語言的識別器是正則語言的

11、識別器A1(S，a1)，A2(A1，a2)，An-1(An-2，an-1)，Z(An-1，an) Z(S，a1a2an-1an ) a1a2an-1anL(M)對于對于 ，按照定理，按照定理2-5和定理和定理2-6處理。處理。175. FA是正則語言的識別器是正則語言的識別器例例 3-10 構(gòu)造與所給正則文法等價的構(gòu)造與所給正則文法等價的FA： G1：E0A|1B A1|1C B0|0C C0B|1A 185. FA是正則語言的識別器是正則語言的識別器(E，0)=A對應(yīng)對應(yīng)E0A(E，1)=B對應(yīng)對應(yīng)E1B(A，1)=Z,C對應(yīng)對應(yīng)A1|1C(B，0)=Z,C對應(yīng)對應(yīng)B0|0C(C，0)=B對

12、應(yīng)對應(yīng)C0B(C，1)=A對應(yīng)對應(yīng)C1A195. FA是正則語言的識別器是正則語言的識別器205. FA是正則語言的識別器是正則語言的識別器推論推論3-1 FA與正則文法等價。與正則文法等價。證明：根據(jù)定理證明：根據(jù)定理3-3和定理和定理3-4即可得到。即可得到。 215. FA是正則語言的識別器是正則語言的識別器FA與左線性文法與左線性文法對于左線性文法來說，按照推導來說，句子對于左線性文法來說，按照推導來說，句子a1a2an-1an中的字符被推導出的先后順序正好與它中的字符被推導出的先后順序正好與它們在句子中出現(xiàn)的順序相反；而按照歸約來看，它們在句子中出現(xiàn)的順序相反；而按照歸約來看，它們被

13、歸約成語法變量的順序則正好與它們在句子中們被歸約成語法變量的順序則正好與它們在句子中出現(xiàn)的順序相同：出現(xiàn)的順序相同：a1，a2，an-1，an。可見，歸約過程與可見，歸約過程與FA處理句子字符的順序是一致處理句子字符的順序是一致的，所以可考慮依照的，所以可考慮依照“歸約歸約”來研究來研究FA的構(gòu)造。的構(gòu)造。 225. FA是正則語言的識別器是正則語言的識別器對于形如對于形如Aa的產(chǎn)生式：在推導中，一旦使用了的產(chǎn)生式：在推導中，一旦使用了這樣的產(chǎn)生式，句型就變成了句子，而且這樣的產(chǎn)生式，句型就變成了句子，而且a是該句是該句子的第一個字符；按子的第一個字符；按“歸約歸約”理解，對句子的第理解，對句

14、子的第1個字符，根據(jù)形如個字符，根據(jù)形如Aa的產(chǎn)生式進行歸約。的產(chǎn)生式進行歸約。對應(yīng)到對應(yīng)到FA中，中，F(xiàn)A從開始狀態(tài)出發(fā)，讀到句子的第從開始狀態(tài)出發(fā)，讀到句子的第一個字符一個字符a，應(yīng)將它，應(yīng)將它“歸約歸約”為為A。我們?nèi)绻紤]。我們?nèi)绻紤]用語法變量對應(yīng)用語法變量對應(yīng)FA的狀態(tài)，那么，此時我們需要的狀態(tài)，那么，此時我們需要引入一個開始狀態(tài)，比如說：引入一個開始狀態(tài)，比如說：Z。這樣，對應(yīng)形如這樣，對應(yīng)形如Aa的產(chǎn)生式，可以定義的產(chǎn)生式，可以定義A(Z，a)。 235. FA是正則語言的識別器是正則語言的識別器按照上面的分析，對應(yīng)于形如按照上面的分析，對應(yīng)于形如ABa的產(chǎn)生式：的產(chǎn)生式：FA

15、應(yīng)該在狀態(tài)應(yīng)該在狀態(tài)B讀入讀入a時，將狀態(tài)轉(zhuǎn)換到時，將狀態(tài)轉(zhuǎn)換到A。也可。也可以理解為：在狀態(tài)以理解為：在狀態(tài)B，F(xiàn)A已經(jīng)將當前句子的、處理已經(jīng)將當前句子的、處理過的前綴過的前綴“歸約歸約”成了成了B，在此時它讀入，在此時它讀入a時，要時，要將將Ba歸約成歸約成A，因此，它進入狀態(tài)，因此，它進入狀態(tài)A。 按照按照“歸約歸約”的說法，如果一個句子是文法的說法，如果一個句子是文法G產(chǎn)生產(chǎn)生的語言的合法句子，它最終應(yīng)該被歸約成文法的語言的合法句子，它最終應(yīng)該被歸約成文法G的的開始符號。所以，開始符號。所以，G的開始符號對應(yīng)的狀態(tài)就是相的開始符號對應(yīng)的狀態(tài)就是相應(yīng)的應(yīng)的FA的終止狀態(tài)。的終止狀態(tài)。24

16、5. FA是正則語言的識別器是正則語言的識別器例如：對文法例如：對文法G2：EA0|B1A1|C1B0|C0CB0|A1 對應(yīng)對應(yīng)(A，0)=E(B，1)=E(Z，1)=A (C，1)=A (Z，0)=B (C，0)=B(B，0)=C(A，1)=C255. FA是正則語言的識別器是正則語言的識別器G2：EA0|B1A1|C1B0|C0CB0|A1 265. FA是正則語言的識別器是正則語言的識別器構(gòu)造與給定的構(gòu)造與給定的DFA等價的左線性文法：等價的左線性文法：DFA (的狀態(tài)轉(zhuǎn)移圖的狀態(tài)轉(zhuǎn)移圖)作如下作如下“預(yù)處理預(yù)處理”： 刪除刪除DFA的陷阱狀態(tài)的陷阱狀態(tài)(包括與之相關(guān)的弧包括與之相關(guān)的

17、弧)； 在圖中加一個識別狀態(tài)在圖中加一個識別狀態(tài)z； “復制復制”一條原來到達終止狀態(tài)的弧，使它從原一條原來到達終止狀態(tài)的弧，使它從原來的起點出發(fā)，到達新添加的識別狀態(tài)。來的起點出發(fā)，到達新添加的識別狀態(tài)。 (4)如果啟動狀態(tài)是終止狀態(tài)，則增加產(chǎn)生式如果啟動狀態(tài)是終止狀態(tài)，則增加產(chǎn)生式z275. FA是正則語言的識別器是正則語言的識別器左線性文法構(gòu)造依照以下兩條進行左線性文法構(gòu)造依照以下兩條進行 如果如果(A，a)=B，則有產(chǎn)生式，則有產(chǎn)生式BAa； 如果如果(A，a)=B，且，且A是開始狀態(tài)，則有產(chǎn)生式是開始狀態(tài)，則有產(chǎn)生式Ba。 定理定理3-5 左線性文法與左線性文法與FA等價。等價。 2

18、85. FA是正則語言的識別器是正則語言的識別器構(gòu)造與上面構(gòu)造與上面FA等價的左線性文法等價的左線性文法6. FA的一些變形的一些變形 6.1 雙向有窮狀態(tài)自動機雙向有窮狀態(tài)自動機 定義定義3-11：確定的雙向有窮狀態(tài)自動機：確定的雙向有窮狀態(tài)自動機(two-way deterministic finite automaton，2DFA)M=(Q，q0，F(xiàn)) Q、q0、F的意義同的意義同DFA。 306.1 雙向有窮狀態(tài)自動機雙向有窮狀態(tài)自動機：QQL，R，S，對，對 (q，a)Q 如果如果(q，a)= p，L，它表示，它表示M在狀態(tài)在狀態(tài)q讀入字符讀入字符a，將，將狀態(tài)變成狀態(tài)變成p，并將讀

19、頭向左移動一個帶方格而指向輸入字，并將讀頭向左移動一個帶方格而指向輸入字符串的前一個字符。符串的前一個字符。 如果如果(q，a)= p，R，它表示，它表示M在狀態(tài)在狀態(tài)q讀入字符讀入字符a，將，將狀態(tài)變成狀態(tài)變成p，并將讀頭向右移動一個帶方格而指向輸入字，并將讀頭向右移動一個帶方格而指向輸入字符串中下一個字符。符串中下一個字符。 如果如果(q，a)= p，S，它表示，它表示M在狀態(tài)在狀態(tài)q讀入字符讀入字符a，將，將狀態(tài)變成狀態(tài)變成p，讀頭保持在原位不動。，讀頭保持在原位不動。 316.1 雙向有窮狀態(tài)自動機雙向有窮狀態(tài)自動機定義定義3-12：M接受的語言接受的語言 L(M)=x| q0 x*x

20、p且且pF 是是2DFA接受的語言。接受的語言。定理定理3-6 2DFA與與FA等價。等價。326.1 雙向有窮狀態(tài)自動機雙向有窮狀態(tài)自動機定義定義3-13：不確定的雙向有窮狀態(tài)自動機：不確定的雙向有窮狀態(tài)自動機(two-way nondeterministic finite automaton，2NFA)M=(Q，q0，F(xiàn)) Q、q0、F的意義同的意義同DFA。 ：Q2QL，R，S 。336.1 雙向有窮狀態(tài)自動機雙向有窮狀態(tài)自動機(q，a)= ( p1，D1)( p2，D2) ，(pm,Dm) 表示表示M在狀態(tài)在狀態(tài)q讀入字符讀入字符a，可以選擇地將狀態(tài)變成，可以選擇地將狀態(tài)變成p1同時同

21、時按按D1實現(xiàn)對讀頭的移動、或者將狀態(tài)變成實現(xiàn)對讀頭的移動、或者將狀態(tài)變成p2同時按同時按D2實現(xiàn)對讀頭的移動、實現(xiàn)對讀頭的移動、或者將狀態(tài)變成或者將狀態(tài)變成pm同同時按時按Dm實現(xiàn)對讀頭的移動。其中實現(xiàn)對讀頭的移動。其中D1，D2，DmL，R，S，表示的意義與，表示的意義與2DFA2DFA的定義表示的的定義表示的意義相同意義相同。定理定理3-7 2NFA與與FA等價。等價。 346.2 帶輸出的帶輸出的FA 定義定義3-14：Moore機機 ，六元組：，六元組：M=(Q，q0) Q、q0、的意義同的意義同DFA。 輸出字母表輸出字母表(output alphabet)(output alph

22、abet)。 ：Q為輸出函數(shù)。對為輸出函數(shù)。對 qQ，(q)=a表示表示M在狀態(tài)在狀態(tài)q時輸出時輸出a。 356.2 帶輸出的帶輸出的FA 對于對于 a1a2an-1an*，如果，如果(q0，a1)=q1，(q1，a2)=q2，(qn-2，an-1)=qn-1，(qn-1，an)=qn，則則M的輸出為的輸出為 (q0)(q1) (qn-1) (qn) 是一個長度為是一個長度為n+1的串的串366.2 帶輸出的帶輸出的FA 定義定義3-15：Mealy機機 ，六元組，六元組M=(Q，q0) 輸出字母表。輸出字母表。 ：Q為輸出函數(shù)。對為輸出函數(shù)。對 (q，a)Q，(q，a)=d表示表示M在狀態(tài)在

23、狀態(tài)q讀入字符讀入字符a時輸出時輸出d。376.2 帶輸出的帶輸出的FA 對于對于 a1a2an-1an*，M的輸出串為：的輸出串為：(q0, ,a1)(q0, ,a1), ,a2) (q0，a1), ,a2), ,an)設(shè)設(shè)(q0，a1)=q1，(q1，a2)=q2，(qn-2，an-1)=qn-1，(qn-1，an)=qn，則則M的輸出可以表示成：的輸出可以表示成： (q0，a1)(q1，a2) (qn-1，an) 是一個長度為是一個長度為n的串的串386.2 帶輸出的帶輸出的FA Moore機處理該串時每經(jīng)過一個狀態(tài)，就輸出一個機處理該串時每經(jīng)過一個狀態(tài)，就輸出一個字符：輸出字符和狀態(tài)一

24、一對應(yīng)；字符：輸出字符和狀態(tài)一一對應(yīng)；Mealy機處理該串時的每一個移動輸出一個字符：機處理該串時的每一個移動輸出一個字符：輸出字符和移動一一對應(yīng)。輸出字符和移動一一對應(yīng)。 396.2 帶輸出的帶輸出的FA 定義定義3-163-16：設(shè)：設(shè)Moore機機M1=(Q1，1，1，q01)Mealy機機M2=(Q2，2，2，q02)對于對于 x*，當，當T1(x)=1(q0)T2(x)成立成立，則它們是等，則它們是等價的價的其中，其中， T1(x)和和T2(x)分別表示分別表示M1和和M2關(guān)于關(guān)于x的輸出。的輸出。 定理定理3-8 Moore機與機與Mealy機等價機等價。407. 小結(jié)小結(jié) 本章討論正則語言的識別器本章討論正則語言的識別器FA。包括。包括DFA、NFA、-NFA。RG與與FA的等價性。簡單介紹帶輸出的的等價性。簡單介紹帶輸出的FA和和雙向雙向FA。 FA M是一個五元組，是一個五元組，M=(Q，q0，F(xiàn))，它，它可以用狀態(tài)轉(zhuǎn)移圖表示?？梢杂脿顟B(tài)轉(zhuǎn)移圖表示。 M接受的語言為接受的語言為x| x*且且(q，x)F。如果。如果L(M1)=L(M2)，則稱，則稱M1與與M2等價。等價。 FA的狀態(tài)具有有窮的存儲功能。這一特性可以用的狀態(tài)具有有窮的