自動(dòng)機(jī)與形式語(yǔ)言第三章epsilon-NFA概要

2024/8/131RGREε-NFA

NFADFA

正則語(yǔ)言(RL)2024/8/1323.4帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)

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

3允許帶ε

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

3.4帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)

2024/8/1343.4帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)

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

”？

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

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

δ：Q×(∑∪{ε})

2Q

2024/8/1373.4帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)

非空移動(dòng)

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

，并將讀頭向右移動(dòng)一個(gè)帶方格而指向輸入字符串的下一個(gè)字符。2024/8/1383.4帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)

空移動(dòng)

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

。也可以叫做M在狀態(tài)q做一個(gè)空移動(dòng)(又可以稱(chēng)為ε移動(dòng))，并且選擇地將狀態(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};CEFABD111000εεε2024/8/13103.4帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)

⑴

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

11拓展的基礎(chǔ):(q,ε)=ε-CLOSURE(q).歸納:(q,wa)計(jì)算為：從(q,w)=S出發(fā)；對(duì)于S中所有元素p，計(jì)算

ε-CLOSURE

(δ(p,a))的并集。結(jié)論:(q,w)是從q出發(fā)，沿著標(biāo)記為w的路徑所有能到達(dá)的狀態(tài)的集合。2024/8/13123.4帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)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)。CEFABD111000εεε2024/8/1314

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

2024/8/13153.4帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)在ε-NFA中，對(duì)任意a∈∑，q∈Q，需要嚴(yán)格區(qū)分。2024/8/1316狀態(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}2024/8/13173.4帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)M接受(識(shí)別)的語(yǔ)言

對(duì)于

x∈∑*，僅當(dāng)

時(shí)，稱(chēng)x被M接受。

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

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

取NFA

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

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

2024/8/13213.4帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)與上圖ε-NFA等價(jià)的NFA。

2024/8/13223.5FA是正則語(yǔ)言的識(shí)別器

3.5.1FA與右線(xiàn)性文法

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

⑴

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

2024/8/13233.5.1FA與右線(xiàn)性文法⑵

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

⑶

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

當(dāng)δ(q，a)=p∈F，且a是輸入串的最后一個(gè)字符時(shí)，M完成對(duì)此輸入串的處理。

2024/8/13243.5.1FA與右線(xiàn)性文法A0

a1A1

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

a1A1

a1a2A2

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

a2A2

…

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

an-1An-1

a1a2…an-1an

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

an2024/8/13253.5.1FA與右線(xiàn)性文法q0a1a2…an-1an├a1q1a2…an-1an 對(duì)應(yīng)δ(q0，a1)=q1├a1a2q2…an-1an 對(duì)應(yīng)δ(q1，a2)=q2

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

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

2024/8/13273.5.1FA與右線(xiàn)性文法定理3-3FA接受的語(yǔ)言是正則語(yǔ)言。證明：(1)構(gòu)造?；舅枷胧亲孯G的派生對(duì)應(yīng)DFA的移動(dòng)。

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

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

a|δ(q，a)=p∈F}2024/8/13283.5.1FA與右線(xiàn)性文法（2）證明L(G)=L(M)-{ε}。對(duì)于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)

2024/8/13293.5.1FA與右線(xiàn)性文法（3）關(guān)于ε句子。

如果q0

F，則ε

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

2024/8/13303.5.1FA與右線(xiàn)性文法例：與下圖所給DFA等價(jià)的正則文法qs

0|0q0|1q1q0

0|0q0|1q1q1

0q2|1|1q0q2

0q1|1q22024/8/13313.5.1FA與右線(xiàn)性文法例：與下圖所給的DFA等價(jià)的正則文法

q0

0q1|1qt|2qt q1

0q1|1q2|2qt q2

0qt|1q2|2q3|2q3

0qt|1qt|2q3|2 qt

0qt|1qt|2qt

2024/8/13323.5.1FA與右線(xiàn)性文法定理3-4

正則語(yǔ)言可以由FA接受。

證明：（1）構(gòu)造?；舅枷耄鹤孎A模擬RG的派生。設(shè)G=(V，T，P，S)，且ε

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

V。2024/8/13333.5.1FA與右線(xiàn)性文法對(duì)

(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對(duì)應(yīng)用Z∈δ(A，a)與產(chǎn)生式A

a對(duì)應(yīng)。2024/8/13343.5.1FA與右線(xiàn)性文法（2）證明L(M)=L(G)對(duì)于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∈P2024/8/13353.5.1FA與右線(xiàn)性文法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)對(duì)于

ε，按照定理2-5和定理2-6處理。2024/8/13363.5.1FA與右線(xiàn)性文法例3-10

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

G1：E

0A|1B A

1|1C B

0|0C C

0B|1A

2024/8/13373.5.1FA與右線(xiàn)性文法δ(E，0)={A} 對(duì)應(yīng)E

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

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

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

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

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

1A2024/8/13383.5.1FA與右線(xiàn)性文法2024/8/13393.5.1FA與右線(xiàn)性文法推論3-1FA與正則文法等價(jià)。證明：根據(jù)定理3-3和定理3-4即可得到。

2024/8/13403.5.1FA與左線(xiàn)性文法按照推導(dǎo)來(lái)說(shuō)，句子a1a2…an-1an中的字符被推導(dǎo)出的先后順序正好與它們?cè)诰渥又谐霈F(xiàn)的順序相反；而按照歸約來(lái)看，它們被歸約成語(yǔ)法變量的順序則正好與它們?cè)诰渥又谐霈F(xiàn)的順序相同：a1，a2，…，an-1，an。可見(jiàn)，歸約過(guò)程與FA處理句子字符的順序是一致的，所以可考慮依照“歸約”來(lái)研究FA的構(gòu)造。

2024/8/13413.5.1FA與左線(xiàn)性文法對(duì)于形如A

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

a的產(chǎn)生式進(jìn)行歸約。對(duì)應(yīng)到FA中，F(xiàn)A從開(kāi)始狀態(tài)出發(fā)，讀到句子的第一個(gè)字符a，應(yīng)將它“歸約”為A。我們?nèi)绻紤]用語(yǔ)法變量對(duì)應(yīng)FA的狀態(tài)，那么，此時(shí)我們需要引入一個(gè)開(kāi)始狀態(tài)，比如說(shuō)：Z。這樣，對(duì)應(yīng)形如A

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

2024/8/13423.5.1FA與左線(xiàn)性文法按照上面的分析，對(duì)應(yīng)于形如A

Ba的產(chǎn)生式：FA應(yīng)該在狀態(tài)B讀入a時(shí)，將狀態(tài)轉(zhuǎn)換到A。也可以理解為：在狀態(tài)B，F(xiàn)A已經(jīng)將當(dāng)前句子的、處理過(guò)的前綴“歸約”成了B，在此時(shí)它讀入a時(shí)，要將Ba歸約成A，因此，它進(jìn)入狀態(tài)A。

2024/8/13433.5.1FA與左線(xiàn)性文法按照“歸約”的說(shuō)法，如果一個(gè)句子是文法G產(chǎn)生的語(yǔ)言的合法句子，它最終應(yīng)該被歸約成文法G的開(kāi)始符號(hào)。所以，G的開(kāi)始符號(hào)對(duì)應(yīng)的狀態(tài)就是相應(yīng)的FA的終止?fàn)顟B(tài)。如何解決好開(kāi)始符號(hào)只有一個(gè)，而DFA的終止?fàn)顟B(tài)可以有多個(gè)的問(wèn)題。

2024/8/13443.5.1FA與左線(xiàn)性文法例如：對(duì)文法G2：E

A0|B1 A

1|C1 B

0|C0 C

B0|A1

對(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)={C} 2024/8/13453.5.1FA與左線(xiàn)性文法G2：E

A0|B1 A

1|C1 B

0|C0 C

B0|A1

2024/8/13463.5.1FA與左線(xiàn)性文法

定理3-5左線(xiàn)性文法與FA等價(jià)。

2024/8/13473.6FA的一些變形3.6.1雙向有窮狀態(tài)自動(dòng)機(jī)

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

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

2024/8/13483.6.1雙向有窮狀態(tài)自動(dòng)機(jī)δ：Q×∑

Q×{L，R，S}，對(duì)

(q，a)∈Q×∑

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

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

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

2024/8/13493.6.1雙向有窮狀態(tài)自動(dòng)機(jī)M接受的語(yǔ)言

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

是2DFA接受的語(yǔ)言。定理3-62DFA與FA等價(jià)。2024/8/13503.6.1雙向有窮狀態(tài)自動(dòng)機(jī)不確定的雙向有窮狀態(tài)自動(dòng)機(jī)(two-waynondeterministicfiniteautomaton，2NFA)M=(Q，∑，δ，q0，F(xiàn))

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

δ：Q×∑

2Q×{L，R，S}

。2024/8/13513.6.1雙向有窮狀態(tài)自動(dòng)機(jī)δ(q，a)={(p1，D1)(p2，D2)…，(pm,Dm)}表示M在狀態(tài)q讀入字符a，可以選擇地將狀態(tài)變成p1同時(shí)按D1實(shí)現(xiàn)對(duì)讀頭的移動(dòng)、或者將狀態(tài)變成p2同時(shí)按D2實(shí)現(xiàn)對(duì)讀頭的移動(dòng)、……或者將狀態(tài)變成pm同時(shí)按Dm實(shí)現(xiàn)對(duì)讀頭的移動(dòng)。其中D1，D2，…，Dm∈{L，R，S}，表示的意義與2DFA的定義表示的意義相同。2024/8/13523.6.1雙向有窮狀態(tài)自動(dòng)機(jī)定理3-72NFA與FA等價(jià)。

2024/8/13533.6.2帶輸出的FAMoore機(jī)

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

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

λ：Q

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

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

2024/8/13543.6.2帶輸出的FA對(duì)于

a1a2…an-1an∈∑*，如果δ(q0，a1)=q1，δ(q1，a2)=q2，…，δ(qn-2，an-1)=qn-1，δ(qn-1，an)=qn，則M的輸出為

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

2024/8/13553.6.2帶輸出的FAMealy機(jī)

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

Δ——輸出字母表。

λ：Q×∑

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

(q，a)∈Q×∑，λ(q，a)=d表示M在狀態(tài)q讀入字符a時(shí)輸出d。2024/8/13563.6.2帶輸出的FA對(duì)于

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)

2024/8/13573.6.2帶輸出的FAMoore機(jī)處理該串時(shí)每經(jīng)過(guò)一個(gè)狀態(tài)，就輸出一個(gè)字符：輸出字符和狀態(tài)一一對(duì)應(yīng)；Mealy機(jī)處理該串時(shí)的每一個(gè)移動(dòng)輸出一個(gè)字符：輸出字符和移動(dòng)一一對(duì)應(yīng)。

2024/8/13583.6.2帶輸出的F