2022/12/21RGREε-NFA

NFADFA

正則語言(RL)2022/12/11RGREε-NFANFADFA2022/12/223.4帶空移動的有窮狀態(tài)自動機

接受語言{0n1m2k|n，m，k≥0}的NFA

2022/12/123.4帶空移動的有窮狀態(tài)自動機接受語3允許帶ε

輸入的狀態(tài)跳轉(zhuǎn)這些狀態(tài)跳轉(zhuǎn)可以同時進行，無需輸入字符方便構(gòu)造，更加“智能”，但也只接收RL

3.4帶空移動的有窮狀態(tài)自動機

3允許帶ε輸入的狀態(tài)跳轉(zhuǎn)3.4帶空移動的有窮狀態(tài)自動機2022/12/243.4帶空移動的有窮狀態(tài)自動機

接受語言{0n1m2k|n，m，k≥0}的NFA是否可以構(gòu)造成下圖所示的“ε-NFA

”？

其構(gòu)造顯然比圖1-13所示的NFA更容易。當然還希望它們是等價的。2022/12/143.4帶空移動的有窮狀態(tài)自動機接受語5例子:ε-NFACEFABD111000εεε01εA{E}{B}?B?{C}{D}C?{D}?D???E{F}?{B,C}F{D}??*5例子:ε-NFACEFABD111000εεε2022/12/263.4帶空移動的有窮狀態(tài)自動機

帶空移動的不確定的有窮狀態(tài)自動機(non-deterministicfiniteautomatonwithε-moves,ε-NFA)M=(Q，∑，δ，q0，F(xiàn))，Q、∑、q0、F的意義同DFA。

δ：Q×(∑∪{ε})2Q

2022/12/163.4帶空移動的有窮狀態(tài)自動機帶空移2022/12/273.4帶空移動的有窮狀態(tài)自動機

非空移動(q，a)∈Q×∑δ(q，a)={p1，p2，…，pm}表示M在狀態(tài)q讀入字符a，可以選擇地將狀態(tài)變成p1、p2、…或者pm

，并將讀頭向右移動一個帶方格而指向輸入字符串的下一個字符。2022/12/173.4帶空移動的有窮狀態(tài)自動機非空移2022/12/283.4帶空移動的有窮狀態(tài)自動機

空移動q∈Qδ(q，ε)={p1，p2，…，pm}表示M在狀態(tài)q不讀入任何字符，可以選擇地將狀態(tài)變成p1、p2、…或者pm

。也可以叫做M在狀態(tài)q做一個空移動(又可以稱為ε移動)，并且選擇地將狀態(tài)變成p1、p2、…或者pm。2022/12/183.4帶空移動的有窮狀態(tài)自動機空移動9ε-NFA狀態(tài)的閉包ε-CLOSURE(q)=

從狀態(tài)q出發(fā)，跟隨ε標記的弧所能到達的狀態(tài)的集合。例:ε-CLOSURE(A)={A}; ε-CLOSURE(E)={B,C,D,E}.狀態(tài)集合的閉包ε-CLOSURE(P)=集合P中所有元素的ε閉包的集合

例:ε-CLOSURE({A,E})={A,B,C,D,E};CEFABD111000εεε9ε-NFA狀態(tài)的閉包ε-CLOSURE(q)=從狀態(tài)q出2022/12/2103.4帶空移動的有窮狀態(tài)自動機

⑴

ε-CLOSURE(q)={p|從q到p有一條標記為ε的路}。

2022/12/1103.4帶空移動的有窮狀態(tài)自動機⑴11拓展的基礎(chǔ):(q,ε)=ε-CLOSURE(q).歸納:(q,wa)計算為：從(q,w)=S出發(fā)；對于S中所有元素p，計算

ε-CLOSURE

(δ(p,a))的并集。結(jié)論:(q,w)是從q出發(fā)，沿著標記為w的路徑所有能到達的狀態(tài)的集合。11拓展的基礎(chǔ):(q,ε)=ε-CLOSURE(2022/12/2123.4帶空移動的有窮狀態(tài)自動機2022/12/1123.4帶空移動的有窮狀態(tài)自動機13例子:拓展的(A,ε)=ε-CLOSURE(A)={A}.(A,0)=ε-CLOSURE({E})={B,C,D,E}.(A,01)=ε-CLOSURE({C,D})={C,D}.ε-NFA的語言是所有w的集合，(q0,w)包含接受狀態(tài)。CEFABD111000εεε13例子:拓展的(A,ε)=ε-CLOSURE(2022/12/214

3.4帶空移動的有窮狀態(tài)自動機對任意(P，a)∈2Q×∑。

2022/12/1143.4帶空移動的有窮狀態(tài)自動機對任2022/12/2153.4帶空移動的有窮狀態(tài)自動機在ε-NFA中，對任意a∈∑，q∈Q，需要嚴格區(qū)分。2022/12/1153.4帶空移動的有窮狀態(tài)自動機在ε-2022/12/216狀態(tài)δ

ε012ε012q0{q1}{q0}ΦΦ{q0,q1,q2}{q2}q1{q2}Φ{q1}Φ{q1,q2}Φ{q2}q2ΦΦΦ{q2}{q2}ΦΦ{q2}{q0,q1,q2}{q1,q2}{q1,q2}2022/12/116狀態(tài)δ

ε012ε012q0{q1}2022/12/2173.4帶空移動的有窮狀態(tài)自動機M接受(識別)的語言

對于x∈∑*，僅當

時，稱x被M接受。

2022/12/1173.4帶空移動的有窮狀態(tài)自動機M接受18NFA,ε-NFA等價所有NFA都是ε-NFA.僅僅不包含帶ε的狀態(tài)轉(zhuǎn)換要證明等價性，需證明對于任意的ε-NFA，能構(gòu)建一個接收相同語言的NFA方法：把ε–transition跟“真實”的狀態(tài)轉(zhuǎn)換結(jié)合起來18NFA,ε-NFA等價所有NFA都是ε-NFA.19消除ε-Transition接受w后aaaε跳轉(zhuǎn)狀態(tài)q(q,wa)=ε-CLOSURE()p1p2pnPa19消除ε-Transition接受w后aaaε跳轉(zhuǎn)狀態(tài)q(2022/12/2203.4帶空移動的有窮狀態(tài)自動機定理3-2ε-NFA與NFA等價。證明：設(shè)有ε-NFA

M1=(Q，∑，δ1，q0，F(xiàn))(1)構(gòu)造與之等價的NFAM2。

取NFA

M2=(Q，∑，δ2，q0，F(xiàn)2)

F∪{q0} 如果F∩ε-CLOSURE(q0)≠ΦF2= F 如果F∩ε-CLOSURE(q0)=Φ

2022/12/1203.4帶空移動的有窮狀態(tài)自動機定理2022/12/2213.4帶空移動的有窮狀態(tài)自動機與上圖ε-NFA等價的NFA。

2022/12/1213.4帶空移動的有窮狀態(tài)自動機與上圖2022/12/2223.5FA是正則語言的識別器

3.5.1FA與右線性文法

DFAM=(Q，∑，δ，q0，F(xiàn))，處理句子a1a2…an的特性。

⑴

M按照句子a1a2…an中字符的出現(xiàn)順序，從開始狀態(tài)q0開始，依次處理字符a1、a2、…、an，在這個處理過程中，每處理一的字符進入一個狀態(tài)，最后停止在某個終止狀態(tài)。

2022/12/1223.5FA是正則語言的識別器

3.2022/12/2233.5.1FA與右線性文法⑵

它每次處理且僅處理一個字符：第i步處理輸入字符ai。

⑶

對應(yīng)于使用δ(q，a)=p的狀態(tài)轉(zhuǎn)移函數(shù)的處理，相當于是在狀態(tài)q完成對a的處理，然后由p接下去實現(xiàn)對后續(xù)字符的處理。⑷

當δ(q，a)=p∈F，且a是輸入串的最后一個字符時，M完成對此輸入串的處理。

2022/12/1233.5.1FA與右線性文法⑵它每次2022/12/2243.5.1FA與右線性文法A0a1A1

對應(yīng)產(chǎn)生式A0a1A1

a1a2A2

對應(yīng)產(chǎn)生式A1a2A2

…

a1a2…an-1An-1 對應(yīng)產(chǎn)生式An-2an-1An-1a1a2…an-1an

對應(yīng)產(chǎn)生式An-1an2022/12/1243.5.1FA與右線性文法A0a2022/12/2253.5.1FA與右線性文法q0a1a2…an-1an├a1q1a2…an-1an 對應(yīng)δ(q0，a1)=q1├a1a2q2…an-1an 對應(yīng)δ(q1，a2)=q2

……├a1a2…an-1qn-1an 對應(yīng)δ(qn-2，an-1)=qn-1├a1a2…an-1anqn 對應(yīng)δ(qn-1，an)=qn

2022/12/1253.5.1FA與右線性文法q0a12022/12/2263.5.1FA與右線性文法其中qn為M的終止狀態(tài)。考慮根據(jù)a1、a2、…、an，讓A0與q0對應(yīng)、A1與q1對應(yīng)、A2與q2對應(yīng)、…、An-2與qn-2對應(yīng)、An-1與qn-1對應(yīng)。這樣，就有希望得到滿足定理2-4-1的正則文法的推導(dǎo)與DFA的互相模擬的方式。

2022/12/1263.5.1FA與右線性文法其中qn為2022/12/2273.5.1FA與右線性文法定理3-3FA接受的語言是正則語言。證明：(1)構(gòu)造?；舅枷胧亲孯G的派生對應(yīng)DFA的移動。

設(shè)DFAM=(Q，∑，δ，q0，F(xiàn))，取右線性文法G=(Q，∑，P，q0)，P={qap|δ(q，a)=p}∪{qa|δ(q，a)=p∈F}2022/12/1273.5.1FA與右線性文法定理3-2022/12/2283.5.1FA與右線性文法（2）證明L(G)=L(M)-{ε}。對于a1a2…an-1an∈∑+，q0+a1a2…an-1an

q0a1q1，q1a2q2，…，

qn-2an-1qn-1，qn-1an∈Pδ(q0，a1)=q1，δ(q1，a2)=q2，…， δ(qn-2，an-1)=qn-1，δ(qn-1，an)=qn，且qn∈F

δ(q0，a1a2…an-1an)=qn∈F

a1a2…an-1an∈L(M)

2022/12/1283.5.1FA與右線性文法（2）證明2022/12/2293.5.1FA與右線性文法（3）關(guān)于ε句子。

如果q0F，則εL(M)，L(G)=L(M)。如果q0∈F，則由定理2-6和定理2-7，存在正則文法G′，使得L(G′)=L(G)∪{ε}=L(M)。綜上所述，對于任意DFAM，存在正則文法G，使得L(G)=L(M)。定理得證。

2022/12/1293.5.1FA與右線性文法（3）關(guān)于2022/12/2303.5.1FA與右線性文法例：與下圖所給DFA等價的正則文法qs0|0q0|1q1q00|0q0|1q1q10q2|1|1q0q20q1|1q22022/12/1303.5.1FA與右線性文法例：與下圖2022/12/2313.5.1FA與右線性文法例：與下圖所給的DFA等價的正則文法

q00q1|1qt|2qt q10q1|1q2|2qt q20qt|1q2|2q3|2q30qt|1qt|2q3|2 qt0qt|1qt|2qt

2022/12/1313.5.1FA與右線性文法例：與下圖2022/12/2323.5.1FA與右線性文法定理3-4

正則語言可以由FA接受。

證明：（1）構(gòu)造。基本思想：讓FA模擬RG的派生。設(shè)G=(V，T，P，S)，且εL(G)，取FAM=(V∪{Z}，T，δ，S，{Z})，ZV。2022/12/1323.5.1FA與右線性文法定理3-42022/12/2333.5.1FA與右線性文法對(a，A)∈T×V

{B|AaB∈P}∪{Z} 如果Aa∈Pδ(A，a)= {B|AaB∈P} 如果AaP

用B∈δ(A，a)與產(chǎn)生式AaB對應(yīng)用Z∈δ(A，a)與產(chǎn)生式Aa對應(yīng)。2022/12/1333.5.1FA與右線性文法對(a，2022/12/2343.5.1FA與右線性文法（2）證明L(M)=L(G)對于a1a2…an-1an∈T+，

a1a2…an-1an∈L(G)S+a1a2…an-1an

Sa1A1

a1a2A2

…

a1a2…an-1An-1

a1a2…an-1an

Sa1A1，A1a2A2，…，

An-2an-1An-1，An-1an∈P2022/12/1343.5.1FA與右線性文法（2）證明2022/12/2353.5.1FA與右線性文法A1∈δ(S，a1)，A2∈δ(A1，a2)，…，

An-1∈δ(An-2，an-1)，Z∈δ(An-1，an)Z∈δ(S，a1a2…an-1an)a1a2…an-1an∈L(M)對于ε，按照定理2-5和定理2-6處理。2022/12/1353.5.1FA與右線性文法A1∈δ(2022/12/2363.5.1FA與右線性文法例3-10

構(gòu)造與所給正則文法等價的FA：

G1：E0A|1B A1|1C B0|0C C0B|1A

2022/12/1363.5.1FA與右線性文法例3-12022/12/2373.5.1FA與右線性文法δ(E，0)={A} 對應(yīng)E0Aδ(E，1)={B} 對應(yīng)E1Bδ(A，1)={Z,C} 對應(yīng)A1|1Cδ(B，0)={Z,C} 對應(yīng)B0|0Cδ(C，0)={B} 對應(yīng)C0Bδ(C，1)={A} 對應(yīng)C1A2022/12/1373.5.1FA與右線性文法δ(E，02022/12/2383.5.1FA與右線性文法2022/12/1383.5.1FA與右線性文法2022/12/2393.5.1FA與右線性文法推論3-1FA與正則文法等價。證明：根據(jù)定理3-3和定理3-4即可得到。

2022/12/1393.5.1FA與右線性文法推論3-12022/12/2403.5.1FA與左線性文法按照推導(dǎo)來說，句子a1a2…an-1an中的字符被推導(dǎo)出的先后順序正好與它們在句子中出現(xiàn)的順序相反；而按照歸約來看，它們被歸約成語法變量的順序則正好與它們在句子中出現(xiàn)的順序相同：a1，a2，…，an-1，an?？梢姡瑲w約過程與FA處理句子字符的順序是一致的，所以可考慮依照“歸約”來研究FA的構(gòu)造。

2022/12/1403.5.1FA與左線性文法按照推導(dǎo)來2022/12/2413.5.1FA與左線性文法對于形如Aa的產(chǎn)生式：在推導(dǎo)中，一旦使用了這樣的產(chǎn)生式，句型就變成了句子，而且a是該句子的第一個字符；按“歸約”理解，對句子的第1個字符，根據(jù)形如Aa的產(chǎn)生式進行歸約。對應(yīng)到FA中，F(xiàn)A從開始狀態(tài)出發(fā)，讀到句子的第一個字符a，應(yīng)將它“歸約”為A。我們?nèi)绻紤]用語法變量對應(yīng)FA的狀態(tài)，那么，此時我們需要引入一個開始狀態(tài)，比如說：Z。這樣，對應(yīng)形如Aa的產(chǎn)生式，可以定義A∈δ(Z，a)。

2022/12/1413.5.1FA與左線性文法對于形如A2022/12/2423.5.1FA與左線性文法按照上面的分析，對應(yīng)于形如ABa的產(chǎn)生式：FA應(yīng)該在狀態(tài)B讀入a時，將狀態(tài)轉(zhuǎn)換到A。也可以理解為：在狀態(tài)B，F(xiàn)A已經(jīng)將當前句子的、處理過的前綴“歸約”成了B，在此時它讀入a時，要將Ba歸約成A，因此，它進入狀態(tài)A。

2022/12/1423.5.1FA與左線性文法按照上面的2022/12/2433.5.1FA與左線性文法按照“歸約”的說法，如果一個句子是文法G產(chǎn)生的語言的合法句子，它最終應(yīng)該被歸約成文法G的開始符號。所以，G的開始符號對應(yīng)的狀態(tài)就是相應(yīng)的FA的終止狀態(tài)。如何解決好開始符號只有一個，而DFA的終止狀態(tài)可以有多個的問題。

2022/12/1433.5.1FA與左線性文法按照“歸約2022/12/2443.5.1FA與左線性文法例如：對文法G2：EA0|B1 A1|C1 B0|C0 CB0|A1

對應(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)={C} 2022/12/1443.5.1FA與左線性文法例如：對文2022/12/2453.5.1FA與左線性文法G2：EA0|B1 A1|C1 B0|C0 CB0|A1

2022/12/1453.5.1FA與左線性文法G2：E2022/12/2463.5.1FA與左線性文法

定理3-5左線性文法與FA等價。

2022/12/1463.5.1FA與左線性文法定理3-2022/12/2473.6FA的一些變形3.6.1雙向有窮狀態(tài)自動機

確定的雙向有窮狀態(tài)自動機(two-waydeterministicfiniteautomaton，2DFA)M=(Q，∑，δ，q0，F(xiàn))

Q、∑、q0、F的意義同DFA。

2022/12/1473.6FA的一些變形3.6.1雙2022/12/2483.6.1雙向有窮狀態(tài)自動機δ：Q×∑Q×{L，R，S}，對(q，a)∈Q×∑

如果δ(q，a)={p，L}，它表示M在狀態(tài)q讀入字符a，將狀態(tài)變成p，并將讀頭向左移動一個帶方格而指向輸入字符串的前一個字符。

如果δ(q，a)={p，R}，它表示M在狀態(tài)q讀入字符a，將狀態(tài)變成p，并將讀頭向右移動一個帶方格而指向輸入字符串中下一個字符。

如果δ(q，a)={p，S}，它表示M在狀態(tài)q讀入字符a，將狀態(tài)變成p，讀頭保持在原位不動。

2022/12/1483.6.1雙向有窮狀態(tài)自動機δ：Q×2022/12/2493.6.1雙向有窮狀態(tài)自動機M接受的語言

L(M)={x|q0x├*xp且p∈F}

是2DFA接受的語言。定理3-62DFA與FA等價。2022/12/1493.6.1雙向有窮狀態(tài)自動機M接受的2022/12/2503.6.1雙向有窮狀態(tài)自動機不確定的雙向有窮狀態(tài)自動機(two-waynondeterministicfiniteautomaton，2NFA)M=(Q，∑，δ，q0，F(xiàn))

Q、∑、q0、F的意義同DFA。

δ：Q×∑2Q×{L，R，S}

。2022/12/1503.6.1雙向有窮狀態(tài)自動機不確定的2022/12/2513.6.1雙向有窮狀態(tài)自動機δ(q，a)={(p1，D1)(p2，D2)…，(pm,Dm)}表示M在狀態(tài)q讀入字符a，可以選擇地將狀態(tài)變成p1同時按D1實現(xiàn)對讀頭的移動、或者將狀態(tài)變成p2同時按D2實現(xiàn)對讀頭的移動、……或者將狀態(tài)變成pm同時按Dm實現(xiàn)對讀頭的移動。其中D1，D2，…，Dm∈{L，R，S}，表示的意義與2DFA的定義表示的意義相同。2022/12/1513.6.1雙向有窮狀態(tài)自動機δ(q，2022/12/2523.6.1雙向有窮狀態(tài)自動機定理3-72NFA與FA等價。

2022/12/1523.6.1雙向有窮狀態(tài)自動機定理3-2022/12/2533.6.2帶輸出的FAMoore機

M=(Q，∑，Δ，δ，λ，q0)Q、∑、q0、δ的意義同DFA。

Δ——輸出字母表(outputalphabet)。

λ：QΔ為輸出函數(shù)。對q∈Q，λ(q)=a表示M在狀態(tài)q時輸出a。

2022/12/1533.6.2帶輸出的FAMoore機2022/12/2543.6.2帶輸出的FA對于a1a2…an-1an∈∑*，如果δ(q0，a1)=q1，δ(q1，a2)=q2，…，δ(qn-2，an-1)=qn-1，δ(qn-1，an)=qn，則M的輸出為

λ(q0)λ(q1)…λ(qn-1)

2022/12/1543.6.2帶輸出的FA對于a1a2022/12/2553.6.2帶輸出的FAMealy機

M=(Q，∑，Δ，δ，λ，q0)

Δ——輸出字母表。

λ：Q×∑Δ為輸出函數(shù)。對(q，a)∈Q×∑，λ(q，a)=d表示M在狀態(tài)q讀入字符a時輸出d。2022/12/1553.6.2帶輸出的FAMealy機2022/12/2563.6.2帶輸出的FA對于a1a2…an-1an∈∑*，M的輸出串為：λ(q0,a1)λ(δ(q0,a1),a2)…λ((…δ(δ(q0，a1),a2)…),an)設(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/12/1563.6.2帶輸出的FA對于a1a2022/12/2573.6.2帶輸出的FAMoore機處理該串時每經(jīng)過一個狀態(tài)，就輸出一個字符：輸出字符和狀態(tài)一一對應(yīng)；Mealy機處理該串時的每一個移動輸出一個字符：輸出字符和移動一一對應(yīng)。

2022/12/1573.6.2帶輸出的FAMoore機2022/12/2583.6.2帶輸出的FA定理3-8Moore機與Mealy機等價。2022/12/1583.6.2帶輸出的FA定理3-82022/12/2593.7小結(jié)

本章討論正則語言的識別器——FA。包括DFA、NFA、ε-NFA。RG與FA的等價性。簡單介紹帶輸出的FA和雙向FA。

⑴

FAM是一個五元組，M=(Q，∑，δ，q0，F(xiàn))，它可以用狀態(tài)轉(zhuǎn)移圖表示。⑵

M接受的語言為{x|x∈∑*且δ(q，x)∈F}。如果L(M1)=L(M2)，則稱M1與M2等價。⑶

FA的狀態(tài)具有有窮的存儲功能。這一特性可以用來構(gòu)造接受一個給定語言的FA。2022/12/1593.7小結(jié)本章討論正2022/12/2603.7小結(jié)⑷NFA允許M在一個狀態(tài)下讀入一個字符時選擇地進入某一個狀態(tài)，對于x∈∑*，如果δ(q0，x)∩F≠Φ，則稱x被M接受，如果δ(q0，x)∩F=Φ，則稱M不接受x。M接受的語言L(M)={x|x∈∑*且δ(q0，x)∩F≠Φ}。

2022/12/1603.7小結(jié)⑷NFA允許M在一2022/12/2613.7小結(jié)⑸ε-NFA是在NFA的基礎(chǔ)上，允許直接根據(jù)當前狀態(tài)變換到新的狀態(tài)而不考慮輸入帶上的符號。對q∈Q，δ(q，ε)={p1，p2，…，pm}表示M在狀態(tài)q不讀入任何字符，可以選擇地將狀態(tài)變成p1、p2、…或者pm。這叫做M在狀態(tài)q做一個空移動。⑹NFA與DFA等價，ε-NFA與NFA等價，統(tǒng)稱它們?yōu)镕A。

2022/12/1613.7小結(jié)⑸ε-NFA是在NFA的2022/12/2623.7小結(jié)⑺根據(jù)需要，可以在FA中設(shè)置一種特殊的狀態(tài)——陷阱狀態(tài)。但是，不可達狀態(tài)卻是應(yīng)該無條件地刪除的。⑻FA是正則語言的識別模型。分別按照對推導(dǎo)和歸約的模擬，可以證明FA和左線性文法、右線性文法等價。

2022/12/1623.7小結(jié)⑺根據(jù)需要，可以在FA2022/12/2633.7小結(jié)⑼2DFA是FA的又一種變形，它不僅允許讀頭向前移動，還允許讀頭向后移動。通過這種擴充，2DFA仍然與FA等價。⑽Moore機和Mealy機是兩種等價的帶輸出的FA，Moore機根據(jù)狀態(tài)決定輸出字符，Mealy機根據(jù)移動決定輸出字符。2022/12/1633.7小結(jié)⑼2DFA是FA的又一2022/12/264RGREε-NFA

NFADFA

正則語言(RL)2022/12/11RGREε-NFANFADFA2022/12/2653.4帶空移動的有窮狀態(tài)自動機

接受語言{0n1m2k|n，m，k≥0}的NFA

2022/12/123.4帶空移動的有窮狀態(tài)自動機接受語66允許帶ε

輸入的狀態(tài)跳轉(zhuǎn)這些狀態(tài)跳轉(zhuǎn)可以同時進行，無需輸入字符方便構(gòu)造，更加“智能”，但也只接收RL

3.4帶空移動的有窮狀態(tài)自動機

3允許帶ε輸入的狀態(tài)跳轉(zhuǎn)3.4帶空移動的有窮狀態(tài)自動機2022/12/2673.4帶空移動的有窮狀態(tài)自動機

接受語言{0n1m2k|n，m，k≥0}的NFA是否可以構(gòu)造成下圖所示的“ε-NFA

”？

其構(gòu)造顯然比圖1-13所示的NFA更容易。當然還希望它們是等價的。2022/12/143.4帶空移動的有窮狀態(tài)自動機接受語68例子:ε-NFACEFABD111000εεε01εA{E}{B}?B?{C}{D}C?{D}?D???E{F}?{B,C}F{D}??*5例子:ε-NFACEFABD111000εεε2022/12/2693.4帶空移動的有窮狀態(tài)自動機

帶空移動的不確定的有窮狀態(tài)自動機(non-deterministicfiniteautomatonwithε-moves,ε-NFA)M=(Q，∑，δ，q0，F(xiàn))，Q、∑、q0、F的意義同DFA。

δ：Q×(∑∪{ε})2Q

2022/12/163.4帶空移動的有窮狀態(tài)自動機帶空移2022/12/2703.4帶空移動的有窮狀態(tài)自動機

非空移動(q，a)∈Q×∑δ(q，a)={p1，p2，…，pm}表示M在狀態(tài)q讀入字符a，可以選擇地將狀態(tài)變成p1、p2、…或者pm

，并將讀頭向右移動一個帶方格而指向輸入字符串的下一個字符。2022/12/173.4帶空移動的有窮狀態(tài)自動機非空移2022/12/2713.4帶空移動的有窮狀態(tài)自動機

空移動q∈Qδ(q，ε)={p1，p2，…，pm}表示M在狀態(tài)q不讀入任何字符，可以選擇地將狀態(tài)變成p1、p2、…或者pm

。也可以叫做M在狀態(tài)q做一個空移動(又可以稱為ε移動)，并且選擇地將狀態(tài)變成p1、p2、…或者pm。2022/12/183.4帶空移動的有窮狀態(tài)自動機空移動72ε-NFA狀態(tài)的閉包ε-CLOSURE(q)=

從狀態(tài)q出發(fā)，跟隨ε標記的弧所能到達的狀態(tài)的集合。例:ε-CLOSURE(A)={A}; ε-CLOSURE(E)={B,C,D,E}.狀態(tài)集合的閉包ε-CLOSURE(P)=集合P中所有元素的ε閉包的集合

例:ε-CLOSURE({A,E})={A,B,C,D,E};CEFABD111000εεε9ε-NFA狀態(tài)的閉包ε-CLOSURE(q)=從狀態(tài)q出2022/12/2733.4帶空移動的有窮狀態(tài)自動機

⑴

ε-CLOSURE(q)={p|從q到p有一條標記為ε的路}。

2022/12/1103.4帶空移動的有窮狀態(tài)自動機⑴74拓展的基礎(chǔ):(q,ε)=ε-CLOSURE(q).歸納:(q,wa)計算為：從(q,w)=S出發(fā)；對于S中所有元素p，計算

ε-CLOSURE

(δ(p,a))的并集。結(jié)論:(q,w)是從q出發(fā)，沿著標記為w的路徑所有能到達的狀態(tài)的集合。11拓展的基礎(chǔ):(q,ε)=ε-CLOSURE(2022/12/2753.4帶空移動的有窮狀態(tài)自動機2022/12/1123.4帶空移動的有窮狀態(tài)自動機76例子:拓展的(A,ε)=ε-CLOSURE(A)={A}.(A,0)=ε-CLOSURE({E})={B,C,D,E}.(A,01)=ε-CLOSURE({C,D})={C,D}.ε-NFA的語言是所有w的集合，(q0,w)包含接受狀態(tài)。CEFABD111000εεε13例子:拓展的(A,ε)=ε-CLOSURE(2022/12/277

3.4帶空移動的有窮狀態(tài)自動機對任意(P，a)∈2Q×∑。

2022/12/1143.4帶空移動的有窮狀態(tài)自動機對任2022/12/2783.4帶空移動的有窮狀態(tài)自動機在ε-NFA中，對任意a∈∑，q∈Q，需要嚴格區(qū)分。2022/12/1153.4帶空移動的有窮狀態(tài)自動機在ε-2022/12/279狀態(tài)δ

ε012ε012q0{q1}{q0}ΦΦ{q0,q1,q2}{q2}q1{q2}Φ{q1}Φ{q1,q2}Φ{q2}q2ΦΦΦ{q2}{q2}ΦΦ{q2}{q0,q1,q2}{q1,q2}{q1,q2}2022/12/116狀態(tài)δ

ε012ε012q0{q1}2022/12/2803.4帶空移動的有窮狀態(tài)自動機M接受(識別)的語言

對于x∈∑*，僅當

時，稱x被M接受。

2022/12/1173.4帶空移動的有窮狀態(tài)自動機M接受81NFA,ε-NFA等價所有NFA都是ε-NFA.僅僅不包含帶ε的狀態(tài)轉(zhuǎn)換要證明等價性，需證明對于任意的ε-NFA，能構(gòu)建一個接收相同語言的NFA方法：把ε–transition跟“真實”的狀態(tài)轉(zhuǎn)換結(jié)合起來18NFA,ε-NFA等價所有NFA都是ε-NFA.82消除ε-Transition接受w后aaaε跳轉(zhuǎn)狀態(tài)q(q,wa)=ε-CLOSURE()p1p2pnPa19消除ε-Transition接受w后aaaε跳轉(zhuǎn)狀態(tài)q(2022/12/2833.4帶空移動的有窮狀態(tài)自動機定理3-2ε-NFA與NFA等價。證明：設(shè)有ε-NFA

M1=(Q，∑，δ1，q0，F(xiàn))(1)構(gòu)造與之等價的NFAM2。

取NFA

M2=(Q，∑，δ2，q0，F(xiàn)2)

F∪{q0} 如果F∩ε-CLOSURE(q0)≠ΦF2= F 如果F∩ε-CLOSURE(q0)=Φ

2022/12/1203.4帶空移動的有窮狀態(tài)自動機定理2022/12/2843.4帶空移動的有窮狀態(tài)自動機與上圖ε-NFA等價的NFA。

2022/12/1213.4帶空移動的有窮狀態(tài)自動機與上圖2022/12/2853.5FA是正則語言的識別器

3.5.1FA與右線性文法

DFAM=(Q，∑，δ，q0，F(xiàn))，處理句子a1a2…an的特性。

⑴

M按照句子a1a2…an中字符的出現(xiàn)順序，從開始狀態(tài)q0開始，依次處理字符a1、a2、…、an，在這個處理過程中，每處理一的字符進入一個狀態(tài)，最后停止在某個終止狀態(tài)。

2022/12/1223.5FA是正則語言的識別器

3.2022/12/2863.5.1FA與右線性文法⑵

它每次處理且僅處理一個字符：第i步處理輸入字符ai。

⑶

對應(yīng)于使用δ(q，a)=p的狀態(tài)轉(zhuǎn)移函數(shù)的處理，相當于是在狀態(tài)q完成對a的處理，然后由p接下去實現(xiàn)對后續(xù)字符的處理。⑷

當δ(q，a)=p∈F，且a是輸入串的最后一個字符時，M完成對此輸入串的處理。

2022/12/1233.5.1FA與右線性文法⑵它每次2022/12/2873.5.1FA與右線性文法A0a1A1

對應(yīng)產(chǎn)生式A0a1A1

a1a2A2

對應(yīng)產(chǎn)生式A1a2A2

…

a1a2…an-1An-1 對應(yīng)產(chǎn)生式An-2an-1An-1a1a2…an-1an

對應(yīng)產(chǎn)生式An-1an2022/12/1243.5.1FA與右線性文法A0a2022/12/2883.5.1FA與右線性文法q0a1a2…an-1an├a1q1a2…an-1an 對應(yīng)δ(q0，a1)=q1├a1a2q2…an-1an 對應(yīng)δ(q1，a2)=q2

……├a1a2…an-1qn-1an 對應(yīng)δ(qn-2，an-1)=qn-1├a1a2…an-1anqn 對應(yīng)δ(qn-1，an)=qn

2022/12/1253.5.1FA與右線性文法q0a12022/12/2893.5.1FA與右線性文法其中qn為M的終止狀態(tài)?？紤]根據(jù)a1、a2、…、an，讓A0與q0對應(yīng)、A1與q1對應(yīng)、A2與q2對應(yīng)、…、An-2與qn-2對應(yīng)、An-1與qn-1對應(yīng)。這樣，就有希望得到滿足定理2-4-1的正則文法的推導(dǎo)與DFA的互相模擬的方式。

2022/12/1263.5.1FA與右線性文法其中qn為2022/12/2903.5.1FA與右線性文法定理3-3FA接受的語言是正則語言。證明：(1)構(gòu)造?；舅枷胧亲孯G的派生對應(yīng)DFA的移動。

設(shè)DFAM=(Q，∑，δ，q0，F(xiàn))，取右線性文法G=(Q，∑，P，q0)，P={qap|δ(q，a)=p}∪{qa|δ(q，a)=p∈F}2022/12/1273.5.1FA與右線性文法定理3-2022/12/2913.5.1FA與右線性文法（2）證明L(G)=L(M)-{ε}。對于a1a2…an-1an∈∑+，q0+a1a2…an-1an

q0a1q1，q1a2q2，…，

qn-2an-1qn-1，qn-1an∈Pδ(q0，a1)=q1，δ(q1，a2)=q2，…， δ(qn-2，an-1)=qn-1，δ(qn-1，an)=qn，且qn∈F

δ(q0，a1a2…an-1an)=qn∈F

a1a2…an-1an∈L(M)

2022/12/1283.5.1FA與右線性文法（2）證明2022/12/2923.5.1FA與右線性文法（3）關(guān)于ε句子。

如果q0F，則εL(M)，L(G)=L(M)。如果q0∈F，則由定理2-6和定理2-7，存在正則文法G′，使得L(G′)=L(G)∪{ε}=L(M)。綜上所述，對于任意DFAM，存在正則文法G，使得L(G)=L(M)。定理得證。

2022/12/1293.5.1FA與右線性文法（3）關(guān)于2022/12/2933.5.1FA與右線性文法例：與下圖所給DFA等價的正則文法qs0|0q0|1q1q00|0q0|1q1q10q2|1|1q0q20q1|1q22022/12/1303.5.1FA與右線性文法例：與下圖2022/12/2943.5.1FA與右線性文法例：與下圖所給的DFA等價的正則文法

q00q1|1qt|2qt q10q1|1q2|2qt q20qt|1q2|2q3|2q30qt|1qt|2q3|2 qt0qt|1qt|2qt

2022/12/1313.5.1FA與右線性文法例：與下圖2022/12/2953.5.1FA與右線性文法定理3-4

正則語言可以由FA接受。

證明：（1）構(gòu)造?；舅枷耄鹤孎A模擬RG的派生。設(shè)G=(V，T，P，S)，且εL(G)，取FAM=(V∪{Z}，T，δ，S，{Z})，ZV。2022/12/1323.5.1FA與右線性文法定理3-42022/12/2963.5.1FA與右線性文法對(a，A)∈T×V

{B|AaB∈P}∪{Z} 如果Aa∈Pδ(A，a)= {B|AaB∈P} 如果AaP

用B∈δ(A，a)與產(chǎn)生式AaB對應(yīng)用Z∈δ(A，a)與產(chǎn)生式Aa對應(yīng)。2022/12/1333.5.1FA與右線性文法對(a，2022/12/2973.5.1FA與右線性文法（2）證明L(M)=L(G)對于a1a2…an-1an∈T+，

a1a2…an-1an∈L(G)S+a1a2…an-1an

Sa1A1

a1a2A2

…

a1a2…an-1An-1

a1a2…an-1an

Sa1A1，A1a2A2，…，

An-2an-1An-1，An-1an∈P2022/12/1343.5.1FA與右線性文法（2）證明2022/12/2983.5.1FA與右線性文法A1∈δ(S，a1)，A2∈δ(A1，a2)，…，

An-1∈δ(An-2，an-1)，Z∈δ(An-1，an)Z∈δ(S，a1a2…an-1an)a1a2…an-1an∈L(M)對于ε，按照定理2-5和定理2-6處理。2022/12/1353.5.1FA與右線性文法A1∈δ(2022/12/2993.5.1FA與右線性文法例3-10

構(gòu)造與所給正則文法等價的FA：

G1：E0A|1B A1|1C B0|0C C0B|1A

2022/12/1363.5.1FA與右線性文法例3-12022/12/21003.5.1FA與右線性文法δ(E，0)={A} 對應(yīng)E0Aδ(E，1)={B} 對應(yīng)E1Bδ(A，1)={Z,C} 對應(yīng)A1|1Cδ(B，0)={Z,C} 對應(yīng)B0|0Cδ(C，0)={B} 對應(yīng)C0Bδ(C，1)={A} 對應(yīng)C1A2022/12/1373.5.1FA與右線性文法δ(E，02022/12/21013.5.1FA與右線性文法2022/12/1383.5.1FA與右線性文法2022/12/21023.5.1FA與右線性文法推論3-1FA與正則文法等價。證明：根據(jù)定理3-3和定理3-4即可得到。

2022/12/1393.5.1FA與右線性文法推論3-12022/12/21033.5.1FA與左線性文法按照推導(dǎo)來說，句子a1a2…an-1an中的字符被推導(dǎo)出的先后順序正好與它們在句子中出現(xiàn)的順序相反；而按照歸約來看，它們被歸約成語法變量的順序則正好與它們在句子中出現(xiàn)的順序相同：a1，a2，…，an-1，an?？梢姡瑲w約過程與FA處理句子字符的順序是一致的，所以可考慮依照“歸約”來研究FA的構(gòu)造。

2022/12/1403.5.1FA與左線性文法按照推導(dǎo)來2022/12/21043.5.1FA與左線性文法對于形如Aa的產(chǎn)生式：在推導(dǎo)中，一旦使用了這樣的產(chǎn)生式，句型就變成了句子，而且a是該句子的第一個字符；按“歸約”理解，對句子的第1個字符，根據(jù)形如Aa的產(chǎn)生式進行歸約。對應(yīng)到FA中，F(xiàn)A從開始狀態(tài)出發(fā)，讀到句子的第一個字符a，應(yīng)將它“歸約”為A。我們?nèi)绻紤]用語法變量對應(yīng)FA的狀態(tài)，那么，此時我們需要引入一個開始狀態(tài)，比如說：Z。這樣，對應(yīng)形如Aa的產(chǎn)生式，可以定義A∈δ(Z，a)。

2022/12/1413.5.1FA與左線性文法對于形如A2022/12/21053.5.1FA與左線性文法按照上面的分析，對應(yīng)于形如ABa的產(chǎn)生式：FA應(yīng)該在狀態(tài)B讀入a時，將狀態(tài)轉(zhuǎn)換到A。也可以理解為：在狀態(tài)B，F(xiàn)A已經(jīng)將當前句子的、處理過的前綴“歸約”成了B，在此時它讀入a時，要將Ba歸約成A，因此，它進入狀態(tài)A。

2022/12/1423.5.1FA與左線性文法按照上面的2022/12/21063.5.1FA與左線性文法按照“歸約”的說法，如果一個句子是文法G產(chǎn)生的語言的合法句子，它最終應(yīng)該被歸約成文法G的開始符號。所以，G的開始符號對應(yīng)的狀態(tài)就是相應(yīng)的FA的終止狀態(tài)。如何解決好開始符號只有一個，而DFA的終止狀態(tài)可以有多個的問題。

2022/12/1433.5.1FA與左線性文法按照“歸約2022/12/21073.5.1FA與左線性文法例如：對文法G2：EA0|B1 A1|C1 B0|C0 CB0|A1

對應(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)={C} 2022/12/1443.5.1FA與左線性文法例如：對文2022/12/21083.5.1FA與左線性文法G2：EA0|B1 A1|C1 B0|C0 CB0|A1

2022/12/1453.5.1FA與左線性文法G2：E2022/12/21093.5.1FA與左線性文法

定理3-5左線性文法與FA等價。

2022/12/1463.5.1FA與左線性文法定理3-2022/12/21103.6FA的一些變形3.6.1雙向有窮狀態(tài)自動機

確定的雙向有窮狀態(tài)自動機(two-waydeterministicfiniteautomaton，2DFA)M=(Q，∑，δ，q0，F(xiàn))

Q、∑、q0、F的意義同DFA。

2022/12/1473.6FA的一些變形3.6.1雙2022/12/21113.6.1雙向有窮狀態(tài)自動機δ：Q×∑Q×{L，R，S}，對(q，a)∈Q×∑

如果δ(q，a)={p，L}，它表示M在狀態(tài)q讀入字符a，將狀態(tài)變成p，并將讀頭向左移動一個帶方格而指向輸入字符串的前一個字符。

如果δ(q，a)={p，R}，它表示M在狀態(tài)q讀入字符a，將狀態(tài)變成p，并將讀頭向右移動一個帶方格而指向輸入字符串中下一個字符。

如果δ(q，a)={p，S}，它表示M在狀態(tài)q讀入字符a，將狀態(tài)變成p，讀頭保持在原位不動。

2022/12/1483.6.1雙向有窮狀態(tài)自動機δ：Q×2022/12/21123.6.1雙向有窮狀態(tài)自動機M接受的語言

L(M)={x|q0x├*xp且p∈F}

是2DFA接受的語言。定理3-62DFA與FA等價。2022/12/1493.6.1雙向有窮狀態(tài)自動機M接受的2022/12/21133.6.1雙向有窮狀態(tài)自動機不確定的雙向有窮狀態(tài)自動機(two-waynondeterministicfiniteautomaton，2NFA)M=(Q，∑，δ，q0，F(xiàn))

Q、∑、q0、F的意義同DFA。

δ：Q×∑2Q×{L，R，S}

。2022/12/1503.6.1雙向有窮狀態(tài)自動機不確定的2022/12/21143.6.1雙向有窮狀態(tài)自動機δ(q，a)={(p1，D1)(p2，D2)…，(pm,Dm)}表示M在狀態(tài)q讀入字符a，可以選擇地將狀態(tài)變成p1同時按D1實現(xiàn)對讀頭的移動、或者將狀態(tài)變成p2同時按D2實現(xiàn)對讀頭的移動、……或者將狀態(tài)變成pm同時按Dm實現(xiàn)對讀頭的移動。其中D1，D2，…，Dm∈{L，R，S}，表示的意義與2DFA的定義表示的意義相同。2022/12/1513.6.1雙向有窮狀態(tài)自動機