自動機與形式語言第三章epsilon-NFA課件

2023/9/171RGREε-NFA

NFADFA

正則語言(RL)2023/8/61RGREε-NFANFADFA2023/9/1723.4帶空移動的有窮狀態(tài)自動機

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

2023/8/623.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)自動機2023/9/1743.4帶空移動的有窮狀態(tài)自動機

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

”？

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

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

δ：Q×(∑∪{ε})

2Q

2023/8/663.4帶空移動的有窮狀態(tài)自動機帶空移動2023/9/1773.4帶空移動的有窮狀態(tài)自動機

非空移動

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

，并將讀頭向右移動一個帶方格而指向輸入字符串的下一個字符。2023/8/673.4帶空移動的有窮狀態(tài)自動機非空移動2023/9/1783.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。2023/8/683.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出2023/9/17103.4帶空移動的有窮狀態(tài)自動機

⑴

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

2023/8/6103.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(2023/9/17123.4帶空移動的有窮狀態(tài)自動機2023/8/6123.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(2023/9/1714

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

2023/8/6143.4帶空移動的有窮狀態(tài)自動機對任意2023/9/17153.4帶空移動的有窮狀態(tài)自動機在ε-NFA中，對任意a∈∑，q∈Q，需要嚴格區(qū)分。2023/8/6153.4帶空移動的有窮狀態(tài)自動機在ε-N2023/9/1716狀態(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}2023/8/616狀態(tài)δ

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

對于

x∈∑*，僅當

時，稱x被M接受。

2023/8/6173.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(2023/9/17203.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)=Φ

2023/8/6203.4帶空移動的有窮狀態(tài)自動機定理32023/9/17213.4帶空移動的有窮狀態(tài)自動機與上圖ε-NFA等價的NFA。

2023/8/6213.4帶空移動的有窮狀態(tài)自動機與上圖ε2023/9/17223.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)。

2023/8/6223.5FA是正則語言的識別器

3.52023/9/17233.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完成對此輸入串的處理。

2023/8/6233.5.1FA與右線性文法⑵它每次處2023/9/17243.5.1FA與右線性文法A0

a1A1

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

a1A1

a1a2A2

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

a2A2

…

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

an-1An-1

a1a2…an-1an

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

an2023/8/6243.5.1FA與右線性文法A0a12023/9/17253.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

2023/8/6253.5.1FA與右線性文法q0a1a2023/9/17263.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的互相模擬的方式。

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

設(shè)DFAM=(Q，∑，δ，q0，F(xiàn))，取右線性文法G=(Q，∑，P，q0)，P={q

ap|δ(q，a)=p}∪{q

a|δ(q，a)=p∈F}2023/8/6273.5.1FA與右線性文法定理3-32023/9/17283.5.1FA與右線性文法（2）證明L(G)=L(M)-{ε}。對于a1a2…an-1an∈∑+，q0

+a1a2…an-1an

q0

a1q1，q1

a2q2，…，

qn-2

an-1qn-1，qn-1

an∈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)

2023/8/6283.5.1FA與右線性文法（2）證明2023/9/17293.5.1FA與右線性文法（3）關(guān)于ε句子。

如果q0

F，則ε

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)。定理得證。

2023/8/6293.5.1FA與右線性文法（3）關(guān)于ε2023/9/17303.5.1FA與右線性文法例：與下圖所給DFA等價的正則文法qs

0|0q0|1q1q0

0|0q0|1q1q1

0q2|1|1q0q2

0q1|1q22023/8/6303.5.1FA與右線性文法例：與下圖所2023/9/17313.5.1FA與右線性文法例：與下圖所給的DFA等價的正則文法

q0

0q1|1qt|2qt q1

0q1|1q2|2qt q2

0qt|1q2|2q3|2q3

0qt|1qt|2q3|2 qt

0qt|1qt|2qt

2023/8/6313.5.1FA與右線性文法例：與下圖所2023/9/17323.5.1FA與右線性文法定理3-4

正則語言可以由FA接受。

證明：（1）構(gòu)造。基本思想：讓FA模擬RG的派生。設(shè)G=(V，T，P，S)，且ε

L(G)，取FAM=(V∪{Z}，T，δ，S，{Z})，Z

V。2023/8/6323.5.1FA與右線性文法定理3-42023/9/17333.5.1FA與右線性文法對

(a，A)∈T×V

{B|A

aB∈P}∪{Z} 如果A

a∈Pδ(A，a)= {B|A

aB∈P} 如果A

a

P

用B∈δ(A，a)與產(chǎn)生式A

aB對應(yīng)用Z∈δ(A，a)與產(chǎn)生式A

a對應(yīng)。2023/8/6333.5.1FA與右線性文法對(a，A2023/9/17343.5.1FA與右線性文法（2）證明L(M)=L(G)對于a1a2…an-1an∈T+，

a1a2…an-1an∈L(G)

S

+a1a2…an-1an

S

a1A1

a1a2A2

…

a1a2…an-1An-1

a1a2…an-1an

S

a1A1，A1

a2A2，…，

An-2

an-1An-1，An-1

an∈P2023/8/6343.5.1FA與右線性文法（2）證明L2023/9/17353.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處理。2023/8/6353.5.1FA與右線性文法A1∈δ(S2023/9/17363.5.1FA與右線性文法例3-10

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

G1：E

0A|1B A

1|1C B

0|0C C

0B|1A

2023/8/6363.5.1FA與右線性文法例3-102023/9/17373.5.1FA與右線性文法δ(E，0)={A} 對應(yīng)E

0Aδ(E，1)={B} 對應(yīng)E

1Bδ(A，1)={Z,C} 對應(yīng)A

1|1Cδ(B，0)={Z,C} 對應(yīng)B

0|0Cδ(C，0)={B} 對應(yīng)C

0Bδ(C，1)={A} 對應(yīng)C

1A2023/8/6373.5.1FA與右線性文法δ(E，0)2023/9/17383.5.1FA與右線性文法2023/8/6383.5.1FA與右線性文法2023/9/17393.5.1FA與右線性文法推論3-1FA與正則文法等價。證明：根據(jù)定理3-3和定理3-4即可得到。

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

2023/8/6403.5.1FA與左線性文法按照推導(dǎo)來說2023/9/17413.5.1FA與左線性文法對于形如A

a的產(chǎn)生式：在推導(dǎo)中，一旦使用了這樣的產(chǎn)生式，句型就變成了句子，而且a是該句子的第一個字符；按“歸約”理解，對句子的第1個字符，根據(jù)形如A

a的產(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)形如A

a的產(chǎn)生式，可以定義A∈δ(Z，a)。

2023/8/6413.5.1FA與左線性文法對于形如A2023/9/17423.5.1FA與左線性文法按照上面的分析，對應(yīng)于形如A

Ba的產(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。

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

2023/8/6433.5.1FA與左線性文法按照“歸約”2023/9/17443.5.1FA與左線性文法例如：對文法G2：E

A0|B1 A

1|C1 B

0|C0 C

B0|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} 2023/8/6443.5.1FA與左線性文法例如：對文法2023/9/17453.5.1FA與左線性文法G2：E

A0|B1 A

1|C1 B

0|C0 C

B0|A1

2023/8/6453.5.1FA與左線性文法G2：EA2023/9/17463.5.1FA與左線性文法

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

2023/8/6463.5.1FA與左線性文法定理3-52023/9/17473.6FA的一些變形3.6.1雙向有窮狀態(tài)自動機

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

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

2023/8/6473.6FA的一些變形3.6.1雙向2023/9/17483.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，讀頭保持在原位不動。

2023/8/6483.6.1雙向有窮狀態(tài)自動機δ：Q×∑2023/9/17493.6.1雙向有窮狀態(tài)自動機M接受的語言

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

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

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

δ：Q×∑

2Q×{L，R，S}

。2023/8/6503.6.1雙向有窮狀態(tài)自動機不確定的雙2023/9/17513.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的定義表示的意義相同。2023/8/6513.6.1雙向有窮狀態(tài)自動機δ(q，a2023/9/17523.6.1雙向有窮狀態(tài)自動機定理3-72NFA與FA等價。

2023/8/6523.6.1雙向有窮狀態(tài)自動機定理3-72023/9/17533.6.2帶輸出的FAMoore機

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

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

λ：Q

Δ為輸出函數(shù)。對

q∈Q，λ(q)=a表示M在狀態(tài)q時輸出a。

2023/8/6533.6.2帶輸出的FAMoore機2023/9/17543.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)

2023/8/6543.6.2帶輸出的FA對于a1a22023/9/17553.6.2帶輸出的FAMealy機

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

Δ——輸出字母表。

λ：Q×∑

Δ為輸出函數(shù)。對

(q，a)∈Q×∑，λ(q，a)=d表示M在狀態(tài)q讀入字符a時輸出d。2023/8/6553.6.2帶輸出的FAMealy機2023/9/17563.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)

2023/8/6563.6.2帶輸出的FA對于a1a22023/9/17573.6.2帶輸出的FAMoore機處理該串時每經(jīng)過一個狀態(tài)，就輸出一個字符：輸出字符和狀態(tài)一一對應(yīng)；Mealy機處理該串時的每一個移動輸出一個字符：輸出字符和移動一一對應(yīng)。

2023/8/6573.6.2帶輸出的FAMoore機處2023/9/17583.6.2