自動(dòng)機(jī)與形式語(yǔ)言第三章 epsilon_NFA

1、2022-4-171RGRE-NFA NFADFA 正則語(yǔ)言正則語(yǔ)言 (RL)2022-4-1723.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī) 接受語(yǔ)言接受語(yǔ)言0n1m2k|n，m，k0的的NFA 3 允許帶允許帶 輸入輸入的狀態(tài)跳轉(zhuǎn)的狀態(tài)跳轉(zhuǎn) 這些狀態(tài)跳轉(zhuǎn)可以同時(shí)進(jìn)行，無(wú)需輸入字這些狀態(tài)跳轉(zhuǎn)可以同時(shí)進(jìn)行，無(wú)需輸入字符符 方便構(gòu)造，更加方便構(gòu)造，更加“智能智能”，但也，但也只接收只接收RL3.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī) 2022-4-1743.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī) 接受語(yǔ)言接受語(yǔ)言0n1m2k|n，m，k0的的NFA是否可是

2、否可以構(gòu)造成下圖所示的以構(gòu)造成下圖所示的“-NFA ”？ 其構(gòu)造顯然比圖其構(gòu)造顯然比圖1-13所示的所示的NFA更容易。更容易。當(dāng)然還希望它們是等價(jià)的。當(dāng)然還希望它們是等價(jià)的。5例子例子: -NFACEFABD111000 0 1 A E B B C DC D D E F B, CF D *2022-4-1763.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī) 帶空移動(dòng)的不確定的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)的不確定的有窮狀態(tài)自動(dòng)機(jī)(non-deterministic finite automaton with -moves,-NFA)M=(Q，q0，F(xiàn))，Q、q0、F的意義同的意義同DFA。

3、：Q()2Q 2022-4-1773.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī) 非空移動(dòng)非空移動(dòng) (q，a)Q (q，a)= p1，p2，pm 表示表示M在狀態(tài)在狀態(tài)q讀入字符讀入字符a，可以選擇地，可以選擇地將狀態(tài)變成將狀態(tài)變成p1、p2、或者或者pm ，并將讀，并將讀頭向右移動(dòng)一個(gè)帶方格而指向輸入字符頭向右移動(dòng)一個(gè)帶方格而指向輸入字符串的下一個(gè)字符。串的下一個(gè)字符。2022-4-1783.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī) 空移動(dòng)空移動(dòng) qQ (q，)= p1，p2，pm 表示表示M在狀態(tài)在狀態(tài)q不讀入任何字符，可以選不讀入任何字符，可以選擇地將狀態(tài)變成擇地將

4、狀態(tài)變成p1、p2、或者或者pm 。也。也可以叫做可以叫做M在狀態(tài)在狀態(tài)q做一個(gè)空移動(dòng)做一個(gè)空移動(dòng)(又可以又可以稱(chēng)為稱(chēng)為移動(dòng)移動(dòng))，并且選擇地將狀態(tài)變成，并且選擇地將狀態(tài)變成p1、p2、或者或者pm。9-NFA狀態(tài)的閉包 -CLOSURE(q)= 從狀態(tài)q出發(fā)，跟隨標(biāo)記的弧所能到達(dá)的狀態(tài)的集合。 例: -CLOSURE(A)= A; -CLOSURE(E)= B, C, D, E. 狀態(tài)集合的閉包-CLOSURE(P) = 集合P中所有元素的閉包的集合 例: -CLOSURE(A,E)= A,B,C,D,E;CEFABD1110002022-4-17103.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)

5、的有窮狀態(tài)自動(dòng)機(jī) -CLOSURE(q)=p|從從q到到p有一條標(biāo)記為有一條標(biāo)記為的路的路。 PppCLOSUREPCLOSURE)()()2(11拓展的拓展的基礎(chǔ): (q, ) = -CLOSURE(q).歸納: (q, wa)計(jì)算為：1. 從 (q, w) = S出發(fā)；2. 對(duì)于S中所有元素p，計(jì)算 -CLOSURE (p, a) 的并集。結(jié)論: (q, w) 是從q出發(fā)，沿著標(biāo)記為w的路徑所有能到達(dá)的狀態(tài)的集合。2022-4-17123.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī))(),() 3(qCLOSUREq),(),(),(),(|)(),()4(wrrararpwqr

6、pPPCLOSUREwaq使得13例子:拓展的 (A, ) = -CLOSURE(A) = A. (A, 0) = -CLOSURE(E) = B, C, D, E. (A, 01) = -CLOSURE(C, D) = C, D. -NFA 的語(yǔ)言是所有w的集合， (q0, w) 包含接受狀態(tài)。CEFABD1110002022-4-1714 3.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī) 對(duì)任意對(duì)任意(P，a)2 Q。 PqaqaP),(),()5(PqwqwP),(),()6(2022-4-17153.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī) 在在-NFA中，對(duì)任意中

7、，對(duì)任意a，qQ，),(),(aqaq需要嚴(yán)格區(qū)分。需要嚴(yán)格區(qū)分。2022-4-1716狀狀態(tài)態(tài) 012012q0 q1 q0q0,q1,q2q2q1 q2 q1q1,q2q2q2 q2q2q2q0,q1,q2q1,q2q1,q22022-4-17173.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī) M接受接受(識(shí)別識(shí)別)的語(yǔ)言的語(yǔ)言 對(duì)于對(duì)于 x*，僅當(dāng)，僅當(dāng) Fxq),(0時(shí)，稱(chēng)時(shí)，稱(chēng)x被被M接受。接受。 ),(|)(0*FxqxxML并且18NFA, -NFA等價(jià) 所有 NFA 都是-NFA. 僅僅不包含帶的狀態(tài)轉(zhuǎn)換 要證明等價(jià)性，需證明對(duì)于任意的-NFA，能構(gòu)建一個(gè)接收相同語(yǔ)言

8、的NFA 方法：把transition跟“真實(shí)”的狀態(tài)轉(zhuǎn)換結(jié)合起來(lái)19消除-Transition接受接受w后后aaa 跳轉(zhuǎn)跳轉(zhuǎn)狀態(tài)q(q, wa) = -CLOSURE( ) P),(rarp1p2pnPa2022-4-17203.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)定理定理 3-2-NFA與與NFA等價(jià)。等價(jià)。證明：設(shè)有證明：設(shè)有-NFA M1=(Q，1，q0，F(xiàn))(1) 構(gòu)造與之等價(jià)的構(gòu)造與之等價(jià)的NFA M2 。 取取NFA M2=(Q，2，q0，F(xiàn)2) Fq0如果如果F-CLOSURE(q0)F2=F如果如果F-CLOSURE(q0)= ),(),(12aqaq2022

9、-4-17213.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī) 與上圖與上圖-NFA等價(jià)的等價(jià)的NFA。 2022-4-17223.5 FA是正則語(yǔ)言的識(shí)別器是正則語(yǔ)言的識(shí)別器 3.5.1 FA與右線性文法與右線性文法 DFA M=(Q，q0，F(xiàn))，處理句子，處理句子a1a2an的特性。的特性。 M按照句子按照句子a1a2an中字符的出現(xiàn)順序，中字符的出現(xiàn)順序，從開(kāi)始狀態(tài)從開(kāi)始狀態(tài)q0開(kāi)始，依次處理字符開(kāi)始，依次處理字符a1、a2、an，在這個(gè)處理過(guò)程中，每處理一，在這個(gè)處理過(guò)程中，每處理一的字符進(jìn)入一個(gè)狀態(tài)，最后停止在某個(gè)終的字符進(jìn)入一個(gè)狀態(tài)，最后停止在某個(gè)終止?fàn)顟B(tài)。止?fàn)顟B(tài)。 202

10、2-4-17233.5.1 FA與右線性文法與右線性文法 它每次處理且僅處理一個(gè)字符：第它每次處理且僅處理一個(gè)字符：第i步處理步處理輸入字符輸入字符ai。 對(duì)應(yīng)于使用對(duì)應(yīng)于使用(q，a)=p的狀態(tài)轉(zhuǎn)移函數(shù)的的狀態(tài)轉(zhuǎn)移函數(shù)的處理，相當(dāng)于是在狀態(tài)處理，相當(dāng)于是在狀態(tài)q完成對(duì)完成對(duì)a的處理，的處理，然后由然后由p接下去實(shí)現(xiàn)對(duì)后續(xù)字符的處理。接下去實(shí)現(xiàn)對(duì)后續(xù)字符的處理。 當(dāng)當(dāng)(q，a)=pF，且，且a是輸入串的最后一是輸入串的最后一個(gè)字符時(shí)，個(gè)字符時(shí)，M完成對(duì)此輸入串的處理。完成對(duì)此輸入串的處理。 2022-4-17243.5.1 FA與右線性文法與右線性文法A0 a1A1對(duì)應(yīng)產(chǎn)生式對(duì)應(yīng)產(chǎn)生式A0 a

11、1A1 a1a2A2對(duì)應(yīng)產(chǎn)生式對(duì)應(yīng)產(chǎn)生式A1 a2A2 a1a2an-1An-1對(duì)應(yīng)產(chǎn)生式對(duì)應(yīng)產(chǎn)生式An-2 an-1An-1 a1a2an-1an對(duì)應(yīng)產(chǎn)生式對(duì)應(yīng)產(chǎn)生式An-1 an2022-4-17253.5.1 FA與右線性文法與右線性文法q0 a1a2an-1ana1q1 a2an-1an對(duì)應(yīng)對(duì)應(yīng)(q0，a1)=q1a1a2q2an-1an對(duì)應(yīng)對(duì)應(yīng)(q1，a2)=q2a1a2an-1qn-1an對(duì)應(yīng)對(duì)應(yīng)(qn-2，an-1)=qn-1a1a2an-1anqn對(duì)應(yīng)對(duì)應(yīng)(qn-1，an)=qn 2022-4-17263.5.1 FA與右線性文法與右線性文法 其中其中qn為為M的終止?fàn)顟B(tài)?？紤]

12、根據(jù)的終止?fàn)顟B(tài)?？紤]根據(jù)a1、a2、an，讓?zhuān)孉0與與q0對(duì)應(yīng)、對(duì)應(yīng)、A1與與q1對(duì)應(yīng)、對(duì)應(yīng)、A2與與q2對(duì)應(yīng)、對(duì)應(yīng)、An-2與與qn-2對(duì)應(yīng)、對(duì)應(yīng)、An-1與與qn-1對(duì)應(yīng)。這樣，就有希望得到滿(mǎn)足定理對(duì)應(yīng)。這樣，就有希望得到滿(mǎn)足定理2-4-1的正則文法的推導(dǎo)與的正則文法的推導(dǎo)與DFA的互相模擬的方的互相模擬的方式。式。 2022-4-17273.5.1 FA與右線性文法與右線性文法定理定理 3-3 FA接受的語(yǔ)言是正則語(yǔ)言。接受的語(yǔ)言是正則語(yǔ)言。證明：證明：(1) 構(gòu)造。構(gòu)造。基本思想是讓基本思想是讓RG的派生對(duì)應(yīng)的派生對(duì)應(yīng)DFA的移動(dòng)。的移動(dòng)。 設(shè)設(shè)DFA M=(Q，q0，F(xiàn))，取右線性

13、文法取右線性文法 G=(Q，P，q0)， P=qap|(q，a)=pqa|(q，a)=pF2022-4-17283.5.1 FA與右線性文法與右線性文法（2）證明證明 L(G)=L(M)-。對(duì)于對(duì)于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) 2022-4-17293.5.1 FA與右線性文法與右線性文法（3）關(guān)于關(guān)于句子

14、。句子。 如果如果q0 F，則，則 L(M)，L(G)=L(M)。如果如果q0F，則由定理，則由定理2-6和定理和定理2-7，存在正，存在正則文法則文法G，使得，使得L(G)=L(G) =L(M)。綜上所述，對(duì)于任意綜上所述，對(duì)于任意DFA M，存在正則文法，存在正則文法G，使得，使得L(G)=L(M)。定理得證。定理得證。 2022-4-17303.5.1 FA與右線性文法與右線性文法 例：例：與下圖所給與下圖所給DFA等價(jià)的正則文法等價(jià)的正則文法qs0|0q0|1q1q00|0q0|1q1q10q2|1|1q0q20q1|1q22022-4-17313.5.1 FA與右線性文法與右線性文法

15、 例：例：與下圖所給的與下圖所給的DFA等價(jià)的正則文法等價(jià)的正則文法 q00q1|1qt|2qtq10q1|1q2|2qtq20qt|1q2|2q3|2 q30qt|1qt|2q3|2qt 0qt|1qt|2qt 2022-4-17323.5.1 FA與右線性文法與右線性文法定理定理3-4 正則語(yǔ)言可以由正則語(yǔ)言可以由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。2022-4-17333.5.1 FA與右線性文法與右線性文法 對(duì)對(duì) (a，A)T

16、V B|AaBPZ如果如果AaP(A，a)= B|AaBP如果如果Aa P 用用B(A，a)與產(chǎn)生式與產(chǎn)生式AaB對(duì)應(yīng)對(duì)應(yīng) 用用Z(A，a)與產(chǎn)生式與產(chǎn)生式Aa對(duì)應(yīng)。對(duì)應(yīng)。2022-4-17343.5.1 FA與右線性文法與右線性文法（2）證明證明L(M)=L(G)對(duì)于對(duì)于a1a2an-1anT+， a1a2an-1anL(G) S+ a1a2an-1an Sa1A1 a1a2A2 a1a2an-1An-1 a1a2an-1an Sa1A1，A1a2A2，An-2an-1An-1，An-1anP2022-4-17353.5.1 FA與右線性文法與右線性文法A1(S，a1)，A2(A1，a2)，

17、An-1(An-2，an-1)，Z(An-1，an) Z(S，a1a2an-1an ) a1a2an-1anL(M)對(duì)于對(duì)于 ，按照定理，按照定理2-5和定理和定理2-6處理。處理。2022-4-17363.5.1 FA與右線性文法與右線性文法 例例 3-10 構(gòu)造與所給正則文法等價(jià)的構(gòu)造與所給正則文法等價(jià)的FA： G1：E0A|1B A1|1C B0|0C C0B|1A 2022-4-17373.5.1 FA與右線性文法與右線性文法(E，0)=A對(duì)應(yīng)對(duì)應(yīng)E0A(E，1)=B對(duì)應(yīng)對(duì)應(yīng)E1B(A，1)=Z,C對(duì)應(yīng)對(duì)應(yīng)A1|1C(B，0)=Z,C對(duì)應(yīng)對(duì)應(yīng)B0|0C(C，0)=B對(duì)應(yīng)對(duì)應(yīng)C0B(C，

18、1)=A對(duì)應(yīng)對(duì)應(yīng)C1A2022-4-17383.5.1 FA與右線性文法與右線性文法2022-4-17393.5.1 FA與右線性文法與右線性文法推論推論3-1 FA與正則文法等價(jià)。與正則文法等價(jià)。證明：根據(jù)定理證明：根據(jù)定理3-3和定理和定理3-4即可得到。即可得到。 2022-4-17403.5.1 FA與左線性文法與左線性文法 按照推導(dǎo)來(lái)說(shuō)，句子按照推導(dǎo)來(lái)說(shuō)，句子a1a2an-1an中的字符中的字符被推導(dǎo)出的先后順序正好與它們?cè)诰渥又斜煌茖?dǎo)出的先后順序正好與它們?cè)诰渥又谐霈F(xiàn)的順序相反；而按照歸約來(lái)看，它們出現(xiàn)的順序相反；而按照歸約來(lái)看，它們被歸約成語(yǔ)法變量的順序則正好與它們?cè)诒粴w約成語(yǔ)法

19、變量的順序則正好與它們?cè)诰渥又谐霈F(xiàn)的順序相同：句子中出現(xiàn)的順序相同：a1，a2，an-1，an?？梢?jiàn)，歸約過(guò)程與?？梢?jiàn)，歸約過(guò)程與FA處理句子字符的處理句子字符的順序是一致的，所以可考慮依照順序是一致的，所以可考慮依照“歸約歸約”來(lái)研究來(lái)研究FA的構(gòu)造。的構(gòu)造。 2022-4-17413.5.1 FA與左線性文法與左線性文法 對(duì)于形如對(duì)于形如Aa的產(chǎn)生式：在推導(dǎo)中，一旦的產(chǎn)生式：在推導(dǎo)中，一旦使用了這樣的產(chǎn)生式，句型就變成了句子，使用了這樣的產(chǎn)生式，句型就變成了句子，而且而且a是該句子的第一個(gè)字符；按是該句子的第一個(gè)字符；按“歸約歸約”理解，對(duì)句子的第理解，對(duì)句子的第1個(gè)字符，根據(jù)形如個(gè)字符，

20、根據(jù)形如Aa的產(chǎn)生式進(jìn)行歸約。對(duì)應(yīng)到的產(chǎn)生式進(jìn)行歸約。對(duì)應(yīng)到FA中，中，F(xiàn)A從開(kāi)從開(kāi)始狀態(tài)出發(fā)，讀到句子的第一個(gè)字符始狀態(tài)出發(fā)，讀到句子的第一個(gè)字符a，應(yīng)，應(yīng)將它將它“歸約歸約”為為A。我們?nèi)绻紤]用語(yǔ)法變。我們?nèi)绻紤]用語(yǔ)法變量對(duì)應(yīng)量對(duì)應(yīng)FA的狀態(tài)，那么，此時(shí)我們需要引的狀態(tài)，那么，此時(shí)我們需要引入一個(gè)開(kāi)始狀態(tài)，比如說(shuō)：入一個(gè)開(kāi)始狀態(tài)，比如說(shuō)：Z。這樣，對(duì)應(yīng)。這樣，對(duì)應(yīng)形如形如Aa的產(chǎn)生式，可以定義的產(chǎn)生式，可以定義A(Z，a)。 2022-4-17423.5.1 FA與左線性文法與左線性文法 按照上面的分析，對(duì)應(yīng)于形如按照上面的分析，對(duì)應(yīng)于形如ABa的產(chǎn)生的產(chǎn)生式：式：FA應(yīng)該在狀態(tài)應(yīng)該在

21、狀態(tài)B讀入讀入a時(shí)，將狀態(tài)轉(zhuǎn)換時(shí)，將狀態(tài)轉(zhuǎn)換到到A。也可以理解為：在狀態(tài)。也可以理解為：在狀態(tài)B，F(xiàn)A已經(jīng)將已經(jīng)將當(dāng)前句子的、處理過(guò)的前綴當(dāng)前句子的、處理過(guò)的前綴“歸約歸約”成了成了B，在此時(shí)它讀入在此時(shí)它讀入a時(shí)，要將時(shí)，要將Ba歸約成歸約成A，因此，因此，它進(jìn)入狀態(tài)它進(jìn)入狀態(tài)A。 2022-4-17433.5.1 FA與左線性文法與左線性文法 按照按照“歸約歸約”的說(shuō)法，如果一個(gè)句子是文的說(shuō)法，如果一個(gè)句子是文法法G產(chǎn)生的語(yǔ)言的合法句子，它最終應(yīng)該被產(chǎn)生的語(yǔ)言的合法句子，它最終應(yīng)該被歸約成文法歸約成文法G的開(kāi)始符號(hào)。所以，的開(kāi)始符號(hào)。所以，G的開(kāi)始的開(kāi)始符號(hào)對(duì)應(yīng)的狀態(tài)就是相應(yīng)的符號(hào)對(duì)應(yīng)的狀

22、態(tài)就是相應(yīng)的FA的終止?fàn)顟B(tài)。的終止?fàn)顟B(tài)。 如何解決好開(kāi)始符號(hào)只有一個(gè)，而如何解決好開(kāi)始符號(hào)只有一個(gè)，而DFADFA的終的終止?fàn)顟B(tài)可以有多個(gè)的問(wèn)題。止?fàn)顟B(tài)可以有多個(gè)的問(wèn)題。 2022-4-17443.5.1 FA與左線性文法與左線性文法 例如：對(duì)文法例如：對(duì)文法G2：EA0|B1A1|C1B0|C0CB0|A1 對(duì)應(yīng)對(duì)應(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)=C2022-4-17453.5.1 FA與左線性文法與左線性文法G2：EA0|B1A1|C1B0|C0CB0|A1 2022-4-17463.5.1 FA與左線性文

23、法與左線性文法 定理定理3-5 左線性文法與左線性文法與FA等價(jià)。等價(jià)。 2022-4-17473.6 FA的一些變形的一些變形 3.6.1 雙向有窮狀態(tài)自動(dòng)機(jī)雙向有窮狀態(tài)自動(dòng)機(jī) 確定的雙向有窮狀態(tài)自動(dòng)機(jī)確定的雙向有窮狀態(tài)自動(dòng)機(jī)(two-way deterministic finite automaton，2DFA)M=(Q，q0，F(xiàn)) Q、q0、F的意義同的意義同DFA。 2022-4-17483.6.1 雙向有窮狀態(tài)自動(dòng)機(jī)雙向有窮狀態(tài)自動(dòng)機(jī) ：QQL，R，S，對(duì)，對(duì) (q，a)Q 如果如果(q，a)= p，L，它表示，它表示M在狀態(tài)在狀態(tài)q讀入讀入字符字符a，將狀態(tài)變成，將狀態(tài)變成p，并將

24、讀頭向左移動(dòng)一個(gè)，并將讀頭向左移動(dòng)一個(gè)帶方格而指向輸入字符串的前一個(gè)字符。帶方格而指向輸入字符串的前一個(gè)字符。 如果如果(q，a)= p，R，它表示，它表示M在狀態(tài)在狀態(tài)q讀入讀入字符字符a，將狀態(tài)變成，將狀態(tài)變成p，并將讀頭向右移動(dòng)一個(gè)，并將讀頭向右移動(dòng)一個(gè)帶方格而指向輸入字符串中下一個(gè)字符。帶方格而指向輸入字符串中下一個(gè)字符。 如果如果(q，a)= p，S，它表示，它表示M在狀態(tài)在狀態(tài)q讀入讀入字符字符a，將狀態(tài)變成，將狀態(tài)變成p，讀頭保持在原位不動(dòng)。，讀頭保持在原位不動(dòng)。 2022-4-17493.6.1 雙向有窮狀態(tài)自動(dòng)機(jī)雙向有窮狀態(tài)自動(dòng)機(jī) M接受的語(yǔ)言接受的語(yǔ)言 L(M)=x| q0

25、 x*xp且且pF 是是2DFA接受的接受的語(yǔ)言。語(yǔ)言。定理定理3-6 2DFA與與FA等價(jià)。等價(jià)。2022-4-17503.6.1 雙向有窮狀態(tài)自動(dòng)機(jī)雙向有窮狀態(tài)自動(dòng)機(jī) 不確定的雙向有窮狀態(tài)自動(dòng)機(jī)不確定的雙向有窮狀態(tài)自動(dòng)機(jī)(two-way nondeterministic finite automaton，2NFA)M=(Q，q0，F(xiàn)) Q、q0、F的意義同的意義同DFA。 ：Q2QL，R，S 。2022-4-17513.6.1 雙向有窮狀態(tài)自動(dòng)機(jī)雙向有窮狀態(tài)自動(dòng)機(jī) (q，a)= ( p1，D1)( p2，D2) ，(pm,Dm) 表示表示M在狀態(tài)在狀態(tài)q讀入字符讀入字符a，可以選擇地將，可

26、以選擇地將狀態(tài)變成狀態(tài)變成p1同時(shí)按同時(shí)按D1實(shí)現(xiàn)對(duì)讀頭的移動(dòng)、實(shí)現(xiàn)對(duì)讀頭的移動(dòng)、或者將狀態(tài)變成或者將狀態(tài)變成p2同時(shí)按同時(shí)按D2實(shí)現(xiàn)對(duì)讀頭的實(shí)現(xiàn)對(duì)讀頭的移動(dòng)、移動(dòng)、或者將狀態(tài)變成或者將狀態(tài)變成pm同時(shí)按同時(shí)按Dm實(shí)實(shí)現(xiàn)對(duì)讀頭的移動(dòng)。其中現(xiàn)對(duì)讀頭的移動(dòng)。其中D1，D2，DmL，R，S，表示的意義與，表示的意義與2DFA2DFA的定的定義表示的意義相同義表示的意義相同。 2022-4-17523.6.1 雙向有窮狀態(tài)自動(dòng)機(jī)雙向有窮狀態(tài)自動(dòng)機(jī)定理定理3-7 2NFA與與FA等價(jià)。等價(jià)。 2022-4-17533.6.2 帶輸出的帶輸出的FA Moore機(jī)機(jī) M=(Q，q0) Q、q0、的意義同的意

27、義同DFA。 輸出字母表輸出字母表(output alphabet)(output alphabet)。 ：Q為輸出函數(shù)。對(duì)為輸出函數(shù)。對(duì) qQ，(q)=a表示表示M在狀態(tài)在狀態(tài)q時(shí)輸出時(shí)輸出a。 2022-4-17543.6.2 帶輸出的帶輸出的FA 對(duì)于對(duì)于 a1a2an-1an*，如果，如果(q0，a1)=q1，(q1，a2)=q2，(qn-2，an-1)=qn-1，(qn-1，an)=qn，則則M的輸出為的輸出為 (q0)(q1) (qn-1) 2022-4-17553.6.2 帶輸出的帶輸出的FA Mealy機(jī)機(jī) M=(Q，q0) 輸出字母表。輸出字母表。 ：Q為輸出函數(shù)。對(duì)為輸出函

28、數(shù)。對(duì) (q，a)Q，(q，a)=d表示表示M在狀態(tài)在狀態(tài)q讀讀入字符入字符a時(shí)輸出時(shí)輸出d。2022-4-17563.6.2 帶輸出的帶輸出的FA 對(duì)于對(duì)于 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) 2022-4-17573.6.2 帶輸出的帶輸出的FA Moore機(jī)處理該串時(shí)每經(jīng)過(guò)一個(gè)狀態(tài)，就輸機(jī)

29、處理該串時(shí)每經(jīng)過(guò)一個(gè)狀態(tài)，就輸出一個(gè)字符：輸出字符和狀態(tài)一一對(duì)應(yīng)；出一個(gè)字符：輸出字符和狀態(tài)一一對(duì)應(yīng)； Mealy機(jī)處理該串時(shí)的每一個(gè)移動(dòng)輸出一個(gè)機(jī)處理該串時(shí)的每一個(gè)移動(dòng)輸出一個(gè)字符：輸出字符和移動(dòng)一一對(duì)應(yīng)。字符：輸出字符和移動(dòng)一一對(duì)應(yīng)。 2022-4-17583.6.2 帶輸出的帶輸出的FA 定理定理3-8 Moore機(jī)與機(jī)與Mealy機(jī)等價(jià)機(jī)等價(jià)。2022-4-17593.7 小結(jié)小結(jié) 本章討論正則語(yǔ)言的識(shí)別器本章討論正則語(yǔ)言的識(shí)別器FA。包括包括DFA、NFA、-NFA。RG與與FA的等的等價(jià)性。簡(jiǎn)單介紹帶輸出的價(jià)性。簡(jiǎn)單介紹帶輸出的FA和雙向和雙向FA。 FA M是一個(gè)五元組，是一個(gè)五元組，M=(Q，q0，F(xiàn))，它可以用狀態(tài)轉(zhuǎn)移圖表示。，它可以用狀態(tài)轉(zhuǎn)移圖表示。 M接受