形式語言與自動(dòng)機(jī) 第三章 有窮狀態(tài)自動(dòng)機(jī)2

形式語言與自動(dòng)機(jī)FormalLanguagesandAutomataTheory第三章有窮自動(dòng)機(jī)第三章有窮狀態(tài)自動(dòng)機(jī)一、有窮狀態(tài)自動(dòng)機(jī)FA定義與表示二、確定的有窮自動(dòng)機(jī)DFA三、非確定的有窮自動(dòng)機(jī)NFA四、DFA和NFA的等價(jià)性五、帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA六、FA是正則語言的識(shí)別器七、FA的變形-帶輸出的FA第一次課第二次課例3：求接受語言L（M）={x|x∈

{0,1}*，且 x含有子串00或11}的FA。三、非確定有窮自動(dòng)機(jī)NFA例3：求接受語言L（M）={x|x∈

{0,1}*，且 x含有子串00或11}的FA。狀態(tài)表狀態(tài)圖三、非確定有窮自動(dòng)機(jī)NFA

3、此時(shí)的NFA程序應(yīng)視為擁有“智能”，亦即，在一給定狀態(tài)下，它可根據(jù)當(dāng)前從輸入字符串讀入的字符自動(dòng)到δ(q,a)的轉(zhuǎn)移狀態(tài)集合中選擇進(jìn)入一個(gè)正確的狀態(tài)。非確定有窮自動(dòng)機(jī)NFA非確定有窮自動(dòng)機(jī)NFA

幾個(gè)相關(guān)的基本概念：1、引入基于字符串的狀態(tài)轉(zhuǎn)移函數(shù)δ’；2、

NFA接受句子及語言的條件3、兩個(gè)NFA的等價(jià)非確定有窮自動(dòng)機(jī)NFA

非確定有窮自動(dòng)機(jī)NFA

非確定有窮自動(dòng)機(jī)NFA定義3-8的補(bǔ)充：狀態(tài)轉(zhuǎn)移函數(shù)δ擴(kuò)展為δ

對(duì)于任意的q

∈Q,w∈∑

,a

∈∑，有：

δ’(q,wa)=δ(δ’(q,w),a) =δ(δ’(q,a1a2a3…an），

a) =δ(…δ(δ(q,a1),a2),…,an),a)

非確定有窮自動(dòng)機(jī)NFA說明1：NFA從狀態(tài)q出發(fā)處理字符串wa

狀態(tài)轉(zhuǎn)移過程：說明2：由于Q×∑是Q×∑*

的真子集；對(duì)于任意的q∈Q，a∈∑

，有δ(q，a)=δ’(q，εa) ε是單位元素

={p｜ヨr∈δ(q，ε)，使得p∈δ(r,a)}由定義第2條 ={p｜ヨr∈{q}，使得p∈δ(r,a)}

由定義第1條 ={p｜p∈

δ(q，a)}

q是r的唯一值 =δ(q，a)

非確定有窮自動(dòng)機(jī)NFA可見，狀態(tài)轉(zhuǎn)移函數(shù)δ’可涵蓋δ描述函數(shù)，故應(yīng)用中不必區(qū)分δ和δ

，通常一般性地用δ代替δ

。函數(shù)δ:ρ(

Q）×∑*→ρ(Q)=2Q定義如下:

(1)δ(q,ε)={q} (2)δ(q,wa)={p｜ヨr∈δ(q，w)，使得

p∈δ(r,a)}

q

∈Q 3)δ(P，w)=δ(q，w)PQ

4)

δ({q},w)=δ(q,w)

=δ(q,w)

非確定有窮自動(dòng)機(jī)NFA狀態(tài)轉(zhuǎn)移函數(shù)δ定義內(nèi)涵小結(jié)：幾個(gè)相關(guān)的基本概念：1、基于字符串的狀態(tài)轉(zhuǎn)移函數(shù)δ’；2、

NFA

接受句子及語言的條件3、兩個(gè)NFA的等價(jià)非確定有窮自動(dòng)機(jī)NFA

非確定有窮自動(dòng)機(jī)NFA幾個(gè)相關(guān)的基本概念：1、基于字符串的狀態(tài)轉(zhuǎn)移函數(shù)δ’；2、

NFA接受句子及語言條件3、兩個(gè)NFA的等價(jià)非確定有窮自動(dòng)機(jī)NFA定義3-10：設(shè)M1，M2是FA。如果L（M1）=L（M2），則稱M1與M2等價(jià)。非確定有窮自動(dòng)機(jī)NFA

非確定有窮自動(dòng)機(jī)NFA文法、自動(dòng)機(jī)部分作業(yè)1、DFA、NFA、ε-NFA：教材第三章習(xí)題

2（3,5,7,11），10（2,5），11(2),14(5),15(2)（

第二版P126–P128，第三版P101-107）教材第三章習(xí)題20,22(2)（

P129）下周內(nèi)交課代表，交新主樓G1119DFA與NFA等價(jià)：1、二者均是正則語言識(shí)別模型，用于識(shí)別正則語言。2、對(duì)于任意給定的DFA，肯定存在一個(gè)NFA與之等價(jià)。3、需證：對(duì)于任意給定的NFA，存在一個(gè)DFA與之等價(jià)。四、DFA與NFA

的等價(jià)性證明思路：

1、構(gòu)造與NFAM1=<Q1,∑,δ1,q0,F1>

相應(yīng)的 DFAM2=<Q2,∑,δ2,q0’,F2>

2、證明對(duì)任意輸入字符串x，有δ2(q0’,x)=

δ1(q0,x);

3、證明L（M1）=L（M2）成立。DFA與NFA

的等價(jià)性定理3-1：

對(duì)任一NFA，都存在一個(gè)DFA與其等價(jià)。

1、M1的初始狀態(tài){q0}對(duì)應(yīng)到M2

的q0’=[q0]；2、如果NFAM1

當(dāng)前的一個(gè)狀態(tài)組{q1,q2,…,qn}，讀入字符a后，

進(jìn)入狀態(tài)組{p1,p2,…,pm

}，則相應(yīng)的DFA在綜合狀態(tài)[q1,q2,…,qn

]下，讀入字符a后，進(jìn)入新的綜合狀態(tài)[p1,p2,…,pm

]。3、如果NFA接受某輸入串x，滿足(δ1(q0,x)∩F1≠Φ)，則NFAM1終止?fàn)顟B(tài)組{p1,p2,…,pn

}相應(yīng)的狀態(tài)[p1,p2,…,pn

]應(yīng)為DFA的終止?fàn)顟B(tài)，即有，[p1,p2,…,pn

]

∈F2。

NFA/DFA

模型區(qū)別：

2：給定NFAM1=<Q1,∑,δ1,q0,F1>，構(gòu)造DFAM2

=<Q2,∑,δ2,q0’,F2>，并在二者之間建立對(duì)應(yīng)關(guān)系如下。DFA與NFA

的等價(jià)性1：對(duì)于NFA任一時(shí)刻同時(shí)轉(zhuǎn)向多個(gè)狀態(tài){p1,p2,…,pm

}；DFA可將這些狀態(tài)匯集在一起，將其“總效果”視為自己的一個(gè)“綜合狀態(tài)”[p1,p2,…,pm

]

形式化證明-步驟1：構(gòu)造設(shè)NFAM1=<Q1,∑,δ1,q0,F1>，取DFAM2=<Q2,∑,δ2,[q0],F2>，其中，1）Q2=ρ(Q1)

；2）F2={[p1,p2,…,pm]|{p1,p2,…,pm}Q1

且{p1,p2,…,pm}∩F1≠Φ}； 3）對(duì)

{q1,q2,…,qn}Q1，a∈∑，

δ2（[q1,q2,…,qn]）,a）=[p1,p2,…,pm]

δ1（{q1,q2,…,qn}）,a）={p1,p2,…,pm}DFA與NFA

的等價(jià)性2、設(shè)|x|=n時(shí)，結(jié)論成立，求證|x|=n+1時(shí)，結(jié)論也成立。設(shè)x=wa，其中，|w|=n，a∈∑。由NFA定義，δ1(q0,wa)=δ1(δ1(q0,w),a)=δ1（{q1,q2,…,qn}

,a） ={p1,p2,…,pm}由歸納假設(shè)δ1(q0,w)={q1,q2,…,qn}

δ2([q0],w)=[q1,q2,…,qn]由δ2構(gòu)造定義 δ2（[q1,q2,…,qn]

,a）=[p1,p2,…,pm]

δ1（{q1,q2,…,qn}

,a）={p1,p2,…,pm}所以有，δ2([q0],wa)=

δ2(δ2([q0],w),a)=δ2（[q1,q2,…,qn]，a）

=[p1,p2,…,pm]

結(jié)論成立；得證。

步驟2：判斷狀態(tài)轉(zhuǎn)移設(shè)x∈∑*，施歸納于|x|：1、當(dāng)x=ε,有δ1({q0},ε)={q0}，δ2([q0],ε)=[q0]，結(jié)論成立；DFA與NFA

的等價(jià)性步驟3：判斷對(duì)字符串的接受條件設(shè)x

∈L（M1），有δ1(q0,x)

={p1,p2,…,pm}并且 δ1(q0,x)∩F1≠Φ

亦即， {p1,p2,…,pm}∩F1≠Φ由M2

中F2定義： [p1,p2,…,pm]∈F2證明步驟2可知:δ2([q0],x)=

[p1,p2,…,pm]，故有x∈L(M2)所以，有： L（M1）

L（M2）反之可推得：L（M2）

L（M1）從而，有L（M1）=L（M2）

綜上1)2)3),

定理得證DFA與NFA

的等價(jià)性DFA與NFA

的等價(jià)性構(gòu)造與NFA等價(jià)的DFA算法：a）將NFA的始態(tài)集{q0}作為DFA的始態(tài)[q0]加入到狀態(tài)表的狀態(tài)列b）如果狀態(tài)表的狀態(tài)列中還有未被處理的狀態(tài)，則任選其中的一個(gè)狀態(tài)[q1,q2,…,qn]，對(duì)所有輸入字符a∈∑，計(jì)算δ2（[q1,q2,…,qn],a）的轉(zhuǎn)移狀態(tài)[p1,p2,…,pm]

，并將其填入狀態(tài)表輸入字符列對(duì)應(yīng)的表項(xiàng)中c）如果計(jì)算δ2（[q1,q2,…,qn],a）新獲得的轉(zhuǎn)移狀態(tài)[p1,p2,…,pm]從未在狀態(tài)列中出現(xiàn)過，則將其填入狀態(tài)列中；d）重復(fù)執(zhí)行b)和c)，直到狀態(tài)表的狀態(tài)列中狀態(tài)全部處理完畢為止。狀態(tài)表例狀態(tài)列輸入字符列01[q0][q0,q1][q0,q2]DFA與NFA

的等價(jià)性例：構(gòu)造如圖所示的NFA

等價(jià)的DFA。狀態(tài)說明DFA狀態(tài)列輸入字符01開始狀態(tài)P[q0][q0,q1][q0,q2]中間狀態(tài)P[q0,q1][q0,q1,q3][q0,q2]中間狀態(tài)P[q0,q2][q0,q1][q0,q2,q3]終止?fàn)顟B(tài)P[q0,q1,q3][q0,q1,q3][q0,q2,q3]終止?fàn)顟B(tài)P[q0,q2,q3][q0,q1,q3][q0,q2,q3]按算法建立狀態(tài)表：DFA與NFA

的等價(jià)性狀態(tài)說明DFA狀態(tài)列輸入字符01開始狀態(tài)P[q0][q0,q1][q0,q2]中間狀態(tài)P[q0,q1][q0,q1,q3][q0,q2]中間狀態(tài)P[q0,q2][q0,q1][q0,q2,q3]終止?fàn)顟B(tài)P[q0,q1,q3][q0,q1,q3][q0,q2,q3]終止?fàn)顟B(tài)P[q0,q2,q3][q0,q1,q3][q0,q2,q3]DFA與NFA

的等價(jià)性習(xí)題：p.128.11給定NFA構(gòu)造等價(jià)的DFA小結(jié)：1、非確定型有窮自動(dòng)機(jī)NFA的一般概念：

自動(dòng)機(jī)定義–五元組：M=<Q,∑,δ,q0,F>

；

NFA的狀態(tài)轉(zhuǎn)移函數(shù)

δ可以不唯一；NFA接受語言條件；NFA的等價(jià)性。2、NFA與DFA等價(jià)性的構(gòu)造性證明方法：

1）、給定NFA，構(gòu)造與其相關(guān)的DFAM2=<Q2,∑,δ2,[q0],F2>

2）、證明對(duì)于同一輸入字符串，二者狀態(tài)轉(zhuǎn)移相同；

3）、證明二者識(shí)別的語言相同。3、由NFA構(gòu)造DFA算法及其應(yīng)用第三章有窮狀態(tài)自動(dòng)機(jī)一、有窮狀態(tài)自動(dòng)機(jī)FA定義與表示二、確定的有窮自動(dòng)機(jī)DFA三、非確定的有窮自動(dòng)機(jī)NFA四、DFA和NFA的等價(jià)性五、帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA六、FA是正則語言的識(shí)別器七、FA的變形-帶輸出的FA五、帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA

五、帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA定義3-10：

帶空移動(dòng)的不確定有窮狀態(tài)自動(dòng)機(jī)ε-NFAM

是一個(gè)五元組：

M=（Q，∑，δ，q0，F(xiàn)），其中，Q，∑，q0，F(xiàn)意義同F(xiàn)A；轉(zhuǎn)移函數(shù)δ：Q×(∑∪{ε})2Q

：于q∈Q,a∈∑，1、δ(q,a)

={p1,p2,…,pm}表示M在狀態(tài)q下，讀入字符a,選擇地將狀態(tài)變?yōu)閜1,p2,…,或pm，并將讀頭向右移動(dòng)一個(gè)方格，指向下一個(gè)輸入字符，稱M在狀態(tài)q做一個(gè)非空移動(dòng)。2、δ(q,ε)

={p1,p2,…,pm}表示M在狀態(tài)q下，不讀入任何字符,可選擇地將狀態(tài)變?yōu)閜1,p2,…或pm，稱M在狀態(tài)q做一個(gè)空移動(dòng)。幾個(gè)相關(guān)的基本概念：1、引入基于字符串的狀態(tài)轉(zhuǎn)移函數(shù)δ’2、

NFA接受句子及語言條件帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA狀態(tài)轉(zhuǎn)移函數(shù)δ的推廣：

δ(q,a)

δ’(q,w)

定義ε-

NFM的目的是為了用來識(shí)別語言的句子；因此，需要將狀態(tài)轉(zhuǎn)移函數(shù)δ的定義域從Q×∑推廣到Q×∑*。帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA定義3-10的補(bǔ)充：對(duì)于任意PQ,q∈Q,a∈∑,w

∈∑*,定義概念：

（1）ε-CLOSURE(q)={p|q到p有標(biāo)記為ε的通路}；（2）ε-CLOSURE(P)=

PQ:擴(kuò)展的定義域這里，ε-CLOSURE(q)

是滿足以下條件的最小集合，滿足，1）δ(q,ε)ε-CLOSURE(q)；2）若q’∈ε-CLOSURE(q),則δ(q’,ε)

ε-CLOSURE(q)。帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA定義3-10的補(bǔ)充：轉(zhuǎn)移函數(shù)δ擴(kuò)展為δ’的遞歸定義：(1)δ(q,ε)=ε-CLOSURE(q)；

q通過ε可達(dá)的狀態(tài)集合(2)δ(q,wa)=ε-CLOSURE(P)

，其中， P={p｜ヨr∈δ(q，w)，使得p∈δ(r,a)}

= =一個(gè)移動(dòng)）多個(gè)移動(dòng)）（基于字符的（基于字符串的帶空移動(dòng)的ε-NFA注：在ε-NFA中，δ(q,ε)≠δ(q,ε)；δ(q,a)≠δ(q,a)。δ’幾個(gè)相關(guān)的基本概念：1、基于字符串的狀態(tài)轉(zhuǎn)移函數(shù)δ’2、ε-

NFA

接受句子及語言條件帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA定義3-11：

設(shè)M=<Q,∑,δ,q0,F>是一ε-

NFA。對(duì)于

x

∈∑*，如果δ’(q0,x)∩F≠Φ，則稱x被M識(shí)別(或接受，或表現(xiàn))；如果δ(q0,x)∩F=Φ，則稱M不接受x

。 L（M）={x|x∈∑*且δ’(q0,x)∩F≠Φ

}

稱為由M接受（識(shí)別）的語言。帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA定理3-2：ε-NFAM1

與NFAM2

等價(jià)。

證明思路分析：1、由于NFA

M2是ε-NFAM1的特例，顯然有：L(M2)=L(M1)2、對(duì)于ε-NFAM1，需構(gòu)造NFA

M2，并證明：

L(M1)=L(M2)

構(gòu)造NFA的關(guān)鍵：給定ε-NFAM1，構(gòu)造NFA

M2模擬M1，亦即，用NFA的非空移動(dòng)去代替ε-NFA中包含若干空移動(dòng)以及一個(gè)相應(yīng)的非空的移動(dòng)組合。帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA設(shè)二者的Q、∑、q0分別對(duì)應(yīng)相同，構(gòu)造不同于

M1

的NFAM2的終止?fàn)顟B(tài)F2和狀態(tài)轉(zhuǎn)移函數(shù)δ2

如下： F∪{q0}如果F∩ε-CLOSURE(q0)≠Φ

（1）F2= F如果F∩ε-CLOSURE(q0)=Φ

（2）對(duì)于

(q,a)∈Q×∑，定義δ2(q,a)

=δ’

1(q,a)1、構(gòu)造NFA：設(shè)有ε-NFA

M1

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

）如下。帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA2、構(gòu)造的正確性證明：1、對(duì)于輸入的任意非空字符串，NFA與ε-NFA識(shí)別的字符串相同，亦即，可證明在非空字符串中引入空移動(dòng)不會(huì)影響被識(shí)別句子本身： i)證NFA與ε-NFA轉(zhuǎn)移狀態(tài)相同：

x∈∑+,δ2(q0,x)

=δ’1(q0,x) ii)證NFA與ε-NFA

同時(shí)轉(zhuǎn)入終態(tài)（或非終態(tài)）-

x∈∑+,x∈L(M2)

x∈L(M1),亦即 δ2(q0,x)∩F2≠Φδ’1(q0,x)∩F≠Φ2、對(duì)于輸入的空字符串ε，二者識(shí)別相同：

ε∈L(M1)

ε∈L(M2)。帶空移動(dòng)ε-NFA證明1）：

1、當(dāng)|x|=1,由δ2

的構(gòu)造定義，結(jié)論成立；2、設(shè)|x|=n時(shí)，結(jié)論成立，求證|x|=n+1時(shí)，結(jié)論也成立。設(shè)x=wa，其中，|w|=n，a∈∑。由NFA定義，δ2(q0,x)=δ2(q0,wa)=δ2(δ2(q0,w),a)=δ2(δ’1(q0,w),a)ε-NFA讀串轉(zhuǎn)移歸納

=δ2構(gòu)造定義

=

ε-NFA讀串定義

=

= == 結(jié)論成立

帶空移動(dòng)ε-NFA證明2）：

x∈∑*，x

∈L(M2)

x∈L(M1)

i)設(shè)x=ε，由NFA的轉(zhuǎn)移函數(shù)擴(kuò)展定義δ2(q0,ε）=q0有：ε∈L(M2)δ2(q0,ε)∩F2≠Φ ε是語句

q0F2

q0F

∨

F∩ε-CLOSURE(q0)≠Φ

F2定義∨

q0狀態(tài)

F∩δ’1(q0,ε)≠Φ

ε-NFA

讀ε閉包定義

ε∈L(M1)

ε是ε-NFAM1語句帶空移動(dòng)ε-NFA證明2）：

x∈∑+，x

∈L(M2)

x∈L(M1)

ii)設(shè)|x|≥

1，由NFA的轉(zhuǎn)移函數(shù)擴(kuò)展定義δ2(q0,x

）有：x∈L(M2)

δ2(q0,x)∩F2≠Φ x是M2語句

δ2(q0,x)

∩(F2=F)≠Φ

F2定義

|x|≥

1

δ’1(q0,x)∩F≠Φ 由δ2的構(gòu)造證明1)

x∈L(M1)

x是M1語句帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFAδ’1δ例：給定識(shí)別L(M1)={0n1m2k|n,m,k≥0}的ε-NFA，求等價(jià)的NFAM2給定的M1：構(gòu)造的M2：帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA例：p.129,15.給定ε-NFA，構(gòu)造與之等價(jià)的NFA第三章有窮狀態(tài)自動(dòng)機(jī)一、有窮狀態(tài)自動(dòng)機(jī)FA定義與表示二、確定的有窮自動(dòng)機(jī)DFA三、非確定的有窮自動(dòng)機(jī)NFA四、DFA和NFA的等價(jià)性五、帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA六、FA是正則語言的識(shí)別器七、FA的變形-帶輸出的FA回顧：正則文法和正則語言定義2.6(喬姆斯基文法體系)：設(shè)G=(V,T,P,S)，P=

，(VT)+，

(VT)*1）G叫作0型文法，或短語結(jié)構(gòu)文法（PSG）；對(duì)應(yīng)地，L（G）叫0型語言或短語結(jié)構(gòu)語言（PSL）、遞歸可枚舉集。2）如果對(duì)于∈P，均有||≥||，則稱G為1型文法，或上下文有關(guān)文法（CSG）；對(duì)應(yīng)地，L（G）叫1型語言或上下文有關(guān)語言(CSL).3）如果對(duì)于∈P，均有||≥||，并且∈V，則稱G為2型文法，或上下文無關(guān)文法（CFG）；對(duì)應(yīng)地，L（G）叫2型語言或上下文無關(guān)語言（CFL）。4）如果對(duì)于∈P，均具有以下形式：Aω，AωB；其中，A,B∈V，ω∈T+，則稱G為3型文法，或正則文法（RG）；對(duì)應(yīng)地，L（G）叫3型語言或正則語言（RL）。其它：“空語句–ε”2、相關(guān)定理的兩點(diǎn)結(jié)論：（證明見P80-P82）

i)在語言中增加或者去掉空語句ε，不會(huì)影響原來語言的類型，如語言原來是RL，增加或減去ε后仍然是RL；

ii)需要時(shí)，語言中可增加ε語句，同時(shí)，產(chǎn)生式中增加Aε。1、正常情況下，各類語言均沒有空語句ε。由于引入空語句對(duì)語言本身沒有影響；并且，為了便于處理問題，有時(shí)需要在語言中引入空語句。例如，構(gòu)造帶空移動(dòng)的自動(dòng)機(jī)ε-NFA。六、FA是正則語言的識(shí)別器1、已知：任一正則語言L都存在一正則文法G=(V,T,P,S)，使得L=L（G）。2、已知：G為右線性文法，如果對(duì)于（

）∈P均有以下形式： A

ω；A

ωB；其中，A，B∈V，ω∈T+。3、已知：G為左線性文法，如果對(duì)于（

）∈P均具有以下形式： A

ω；A

Bω；其中，A，B∈V，ω∈T+。4、證明FA可識(shí)別右(左)線性文法派生的正則語言，亦即，F(xiàn)A與正則文法RG等價(jià)。FA是正則語言的識(shí)別器定理3-3：FA接受的語言是正則語言。定理3-4：

正則語言都可以被FA接受。FA是正則語言的識(shí)別器求證方法：1、FA與右線性文法等價(jià)。2、FA與左線性文法等價(jià)。FA與G等價(jià)的證明思路：

1、給定FA，構(gòu)造相應(yīng)的正則文法G，證明二者處理的語言相同。2、

給定正則文法

G，構(gòu)造相應(yīng)的FA，證明二者處理的語言相同。FA是正則語言的識(shí)別器-

FA與右線性文法DFAM=(Q,∑,δ,q0,F

):q0a1a2…an-1an|-a1q1a2…an-1an |-a1a2q2…an-1an …. |-a1a2…an-1qn-1an |-a1a2…an-1anqn右線性文法G=(V,T,P,A0)：A0

a1A1a1a2A2….a1a2…an-1An-1a1a2…an-1an注：1、變量A0

對(duì)應(yīng)狀態(tài)q0；變量A1

對(duì)應(yīng)狀態(tài)q1；依次類推。二者對(duì)應(yīng)關(guān)系：2、FA移至狀態(tài)qn∈F結(jié)束，G中qa

推出終極符號(hào)串，結(jié)束FA是正則語言的識(shí)別器-FA與右線性文法證明步驟1：

設(shè)DFAM=（Q,∑,δ,q0,F）構(gòu)造M相應(yīng)的右線性文法G=(Q,∑,P,q0)，其中

P={q

ap|δ(q,a)=p}∪{qa|δ(q,a)=p∈F}使得L(G)=L(M)-{ε}。定理3-3：FA接受的語言是正則語言。FA是正則語言的識(shí)別器-FA與右線性文法證明步驟2：L（G）=L（M）-{ε

}

對(duì)于任意x=a1a2…an-1an∈∑+

，根據(jù)文法推導(dǎo)定義有:

q0

a1a2…an-1an

q0

a1q1,q1

a2q2，…,qn-1

an∈P

由文法G的構(gòu)造定義

δ(q0,a1)=q1,δ(q1,a2)=q2,…, δ(qn-1,an)=qn,且qn

∈F

δ(…δ(δ(q0,a1),a2),…,an)

qn

∈F

DFA接受字符串定義 δ(q0,a1a2…an-1an)=qn

∈F所以，x=a1a2…an-1an∈L(G)x=a1a2…an-1an∈L(M)

+FA是正則語言的識(shí)別器-FA與右線性文法證明步驟3：如果

q0

F，則εL（M），L(G)=L（M）-{ε}=L（M）已證如果q0

F，則εL（M），由以下已證定理可證：存在正則文法G’，使得L（G’）=L（G）∪{ε}=L（M）。第二章定理2-6，2-7（P81）

：以下命題成立。如果L是CSL，則L∪{ε}（L-{ε}

）仍然是CSL。如果L是CFL，則L∪{ε}（L-{ε}

）仍然是CFL。如果L是RL，則L∪{ε}（L-{ε}

）仍然是RL。FA是正則語言的識(shí)別器-FA與右線性文法例1：給定DFAM如圖，構(gòu)造求解與其等價(jià)的正則文法G。（1）（2）解：證明步驟1：設(shè)有右線性正則文法G=（V,T,P,S），構(gòu)造與G相應(yīng)的DFAM，使得L（M）=L（G）。取M=(V∪{Z},T,δ,S,{Z})，其中,對(duì)于(A,a)∈V×T，有

{B|AaB∈P}∪{Z}如果有Aa∈P，添加Zδ(A,a)= {B|AaB∈P} 如果Aa∈PFA是正則語言的識(shí)別器-

FA與右線性文法定理3-4：正則語言都可以被DFA接受。FA是正則語言的識(shí)別器-FA與右線性文法

證明步驟2：

L（G）=L（M）對(duì)于字符串a(chǎn)1a2…an-1an∈T+

，根據(jù)文法推導(dǎo)產(chǎn)生語言定義：a1a2…an-1an∈L（G）

Sa1a2…an-1an

Sa1A1

a1a2A2

…a1a2…an-1an

有產(chǎn)生式集合

Sa1A1,A1a2A2,…,An-1an∈P由DFA構(gòu)造定義 δ(S,a1)=

A1,δ(A1,a2)=A2,..,δ(An-1,an)=Z

Z∈

δ(…δ(δ(S,a1),a2…),an)

Z∈

δ(S,a1a2…an-1an) a1a2…an-1an∈L（M）+FA是正則語言的識(shí)別器-FA與右線性文法

例：構(gòu)造與給定右正則文法等價(jià)的FA。FAM=({A,B,C,E,Z

},{0,1},δ,E,{Z})起始態(tài)E終止態(tài)Z解：FA是正則語言的識(shí)別器-FA與右線性文法由定理3-3，定理3-4獲推論3-1：FA與正則文法等價(jià)。關(guān)系對(duì)應(yīng)小結(jié)：1、右線性文法G產(chǎn)生式中的語法變量與FA狀態(tài)轉(zhuǎn)移函數(shù)中的狀態(tài)對(duì)應(yīng)，即， Aq；2、文法G的起始符S與FA的起始狀態(tài)q0

對(duì)應(yīng)，即，Sq0；3、右線性文法G的產(chǎn)生式與FA的狀態(tài)轉(zhuǎn)移函數(shù)對(duì)應(yīng)，即，

AaB

B=δ(A,a)；4、G獲終極字符串、FA的終止?fàn)顟B(tài)Z∈F決定推導(dǎo)過程結(jié)束。FA是正則語言的識(shí)別器-

FA與左線性文法DFAM=（Q,∑,δ,q0,F

）：1、從開始符q0

開始，按照句子a1a2…an中字符出現(xiàn)順序依次處理字符；每處理一個(gè)字符轉(zhuǎn)入一個(gè)狀態(tài)，最后停止在某個(gè)終止?fàn)顟B(tài);2、每次處理且僅處理一個(gè)字符，第i步處理輸入字符ai；3、根據(jù)狀態(tài)轉(zhuǎn)移函數(shù)δ(q，a)=p，在狀態(tài)q下處理字符a；然后，從狀態(tài)p開始繼續(xù)處理后續(xù)字符；4、當(dāng)δ(q，a)=p∈F且a是輸入串最后一個(gè)字符時(shí)，M處理完輸入字符串。DFA與左線性文法之間的對(duì)應(yīng)關(guān)系：

G=（V，T，P，S），

A

ω；A

Bω:1、起始符S開始，推導(dǎo)每個(gè)句型右部左側(cè)有且僅有一個(gè)語法變量；它們依次歸約出句子：S

Anan

An-1an-1an,

…,

Aa1…an-1an

aa1…an-1an

；2、產(chǎn)生式A

Ba表明：要使Ba成立，可歸約為求解A有解。3、產(chǎn)生式A

a

表明：要使字符a成立，可歸約為求解A有解；

DFA與左線性文法之間對(duì)應(yīng)關(guān)系：左線性文法運(yùn)用反向歸約法，可獲得與FA讀入字符順序一致的字符串處理過程。左線性文法：

GL=SL

AL6AL

BL5

BL

CL4CL

DL3

DL

EL2

EL

FL1FL

0左線性文法：反向歸約過程：FL123456<=0123456

EL23456<=

DL