編譯原理第2章自動(dòng)機(jī)理論

1、莆田學(xué)院網(wǎng)絡(luò)中心許振和1 本章本章將介紹正規(guī)文法和有窮自動(dòng)將介紹正規(guī)文法和有窮自動(dòng)機(jī)之間的關(guān)系，所涉及的內(nèi)容是編譯機(jī)之間的關(guān)系，所涉及的內(nèi)容是編譯中詞法分析技術(shù)和自動(dòng)生成詞法分析中詞法分析技術(shù)和自動(dòng)生成詞法分析程序的理論。程序的理論。第第2 2章章 自動(dòng)機(jī)理論基礎(chǔ)自動(dòng)機(jī)理論基礎(chǔ)莆田學(xué)院網(wǎng)絡(luò)中心許振和2教學(xué)要求教學(xué)要求掌握：掌握：正規(guī)式，正規(guī)式，DFADFA的概念，的概念，NFANFA的概念的概念理解理解：將：將DFA DFA 轉(zhuǎn)換為轉(zhuǎn)換為NFANFA，正規(guī)文法與有窮，正規(guī)文法與有窮自動(dòng)機(jī)間的轉(zhuǎn)換自動(dòng)機(jī)間的轉(zhuǎn)換重點(diǎn)：重點(diǎn)：正規(guī)式構(gòu)造正規(guī)式構(gòu)造DFADFA，DFADFA最小化最小化難點(diǎn)難點(diǎn)：正規(guī)表

2、達(dá)式構(gòu)造：正規(guī)表達(dá)式構(gòu)造DFADFA莆田學(xué)院網(wǎng)絡(luò)中心許振和3一、正規(guī)式一、正規(guī)式二、二、正規(guī)文法到正規(guī)式正規(guī)文法到正規(guī)式*三、三、確定有窮自動(dòng)機(jī)確定有窮自動(dòng)機(jī)四、四、不確定有窮自動(dòng)機(jī)不確定有窮自動(dòng)機(jī)五、五、 NFA轉(zhuǎn)換為等價(jià)的轉(zhuǎn)換為等價(jià)的DFA六、六、 DFA的化簡(jiǎn)的化簡(jiǎn)七、七、正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)八、正規(guī)文法和有窮自動(dòng)機(jī)的等價(jià)性八、正規(guī)文法和有窮自動(dòng)機(jī)的等價(jià)性*典型例題及解答典型例題及解答 教學(xué)大綱教學(xué)大綱莆田學(xué)院網(wǎng)絡(luò)中心許振和4知識(shí)結(jié)構(gòu)知識(shí)結(jié)構(gòu)詞法分析詞法分析自動(dòng)構(gòu)造工具自動(dòng)構(gòu)造工具正規(guī)集正規(guī)集正規(guī)式正規(guī)式有窮自動(dòng)機(jī)（有窮自動(dòng)機(jī)（NFA DFA)正規(guī)文法正規(guī)文法

3、莆田學(xué)院網(wǎng)絡(luò)中心許振和51、正規(guī)文法 文法G=(VN,VT,P,S)，P中每一規(guī)則有AaB或Aa ，A,BVN，aVT*，稱G(S)是正規(guī)文法。 多數(shù)程序設(shè)計(jì)語言的單詞的語法能用正規(guī)文法來描述多數(shù)程序設(shè)計(jì)語言的單詞的語法能用正規(guī)文法來描述下面定義的標(biāo)識(shí)符和無符號(hào)整數(shù)都是正規(guī)文法：letter | letter字母數(shù)字letter | digit | letter字母數(shù)字 | digit字母數(shù)字digit | digit無符號(hào)整數(shù)一、正規(guī)式與正規(guī)集一、正規(guī)式與正規(guī)集莆田學(xué)院網(wǎng)絡(luò)中心許振和62、正規(guī)式（正規(guī)表達(dá)式） 是表示正規(guī)集的工具，也是用以描述單詞符號(hào)的方便工具。正規(guī)式也稱正則表達(dá)式正規(guī)式也稱

4、正則表達(dá)式, ,是說明單是說明單詞的模式的一種重要的表示法（記號(hào)），是定義詞的模式的一種重要的表示法（記號(hào)），是定義正規(guī)集的數(shù)學(xué)工具。正規(guī)集的數(shù)學(xué)工具。 正規(guī)式中包括3種操作符：連接()，或(|)和閉包(*)，其中或運(yùn)算也常用“+”表示。 優(yōu)先級(jí)：優(yōu)先級(jí)：“閉包閉包”運(yùn)算的優(yōu)先級(jí)最高，運(yùn)算的優(yōu)先級(jí)最高，“連接連接”運(yùn)算次之，運(yùn)算次之，“或或”運(yùn)算最低。運(yùn)算最低。莆田學(xué)院網(wǎng)絡(luò)中心許振和7正規(guī)式與正規(guī)集的正規(guī)式與正規(guī)集的遞歸遞歸定義：定義：設(shè)字母表為，輔助字母表=，|，*，（，） ； 和都是上的正規(guī)式，表示的正規(guī)集分別為和；任何a,a是上的一個(gè)正規(guī)式，表示的正規(guī)集為a;莆田學(xué)院網(wǎng)絡(luò)中心許振和8假定

5、e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1)和L(e2),則(e1),e1|e2,e1e2和e 1*也 都 是 正 規(guī) 式 ， 所 表 示 的 正 規(guī) 集 分 別 為L(zhǎng)(e1),L(e1)L(e2), L(e1)L(e2)和(L(e1)*。 僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的子集才是上的正規(guī)集。例：例： a,ba,b， 上的正規(guī)式和相應(yīng)的正規(guī)集為：上的正規(guī)式和相應(yīng)的正規(guī)集為：莆田學(xué)院網(wǎng)絡(luò)中心許振和9正規(guī)式正規(guī)集aaa|ba,babab(a|b)(a|b)aa，bb,ab,baa*，a,aa, ，aaaa(a|b)* ，a,b,aa,ab

6、,aab,abab, (a|b)*(aa|bb) (a|b)*上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串莆田學(xué)院網(wǎng)絡(luò)中心許振和10 正規(guī)式正規(guī)式: : ( (a a b)b) 正規(guī)集正規(guī)集: : ,a,b,aa,ab ,a,b,aa,ab 所有由所有由a a和和b b組成的組成的串串 正規(guī)式正規(guī)式: :( (a a b)b) (aa(aa bb)(abb)(a b b) ) 正規(guī)集正規(guī)集: : 上所有含有兩個(gè)相繼的上所有含有兩個(gè)相繼的a a或兩個(gè)相繼的或兩個(gè)相繼的b b組成的串組成的串 1. 1. 正規(guī)式與相應(yīng)的正規(guī)集是等價(jià)的，正規(guī)集給出了正規(guī)式與相應(yīng)的正規(guī)集是等價(jià)的，正規(guī)集給出了相應(yīng)正規(guī)式

7、所描述的全部單詞（句子）；相應(yīng)正規(guī)式所描述的全部單詞（句子）； 2. 2. 正規(guī)式的運(yùn)算結(jié)果是正規(guī)集；正規(guī)式的運(yùn)算結(jié)果是正規(guī)集； 3. 3. 正規(guī)式不是集合，其運(yùn)算結(jié)果正規(guī)集是集合。正規(guī)式不是集合，其運(yùn)算結(jié)果正規(guī)集是集合。莆田學(xué)院網(wǎng)絡(luò)中心許振和11 討論下面兩個(gè)例子討論下面兩個(gè)例子例例1 1 令令 =l l，dd，則，則 上的正規(guī)式上的正規(guī)式 r=l(lr=l(l d d) ) 定義定義的正規(guī)集為的正規(guī)集為: l,ll,ld,ldd: l,ll,ld,ldd, ,其中其中l(wèi) l代表字母代表字母,d,d代表數(shù)字代表數(shù)字, ,正規(guī)式正規(guī)式 即是即是 字母字母( (字母字母| |數(shù)字?jǐn)?shù)字) ) ,

8、,它表示的正規(guī)集中的每個(gè)它表示的正規(guī)集中的每個(gè)元素的模式是元素的模式是“字母打頭的字母數(shù)字串字母打頭的字母數(shù)字串”, ,就是就是PascalPascal和多數(shù)程序設(shè)計(jì)語言允許的標(biāo)和多數(shù)程序設(shè)計(jì)語言允許的標(biāo)識(shí)符的詞法規(guī)則識(shí)符的詞法規(guī)則. .莆田學(xué)院網(wǎng)絡(luò)中心許振和12例例2 2：令：令 d d， ，e e，則，則 上的正上的正規(guī)式為：規(guī)式為：d d* *(.dd(.dd* *| | )(e(+|-|)(e(+|-| )dd)dd* *| | ) )表示的是無符號(hào)數(shù)。表示的是無符號(hào)數(shù)。 其中其中d d為為0 09 9中的數(shù)字。中的數(shù)字。 比如：比如：2,12.59,3.6e2,471.88e-12,

9、12.59,3.6e2,471.88e-1等都是正規(guī)等都是正規(guī)式表示集合中的元素。式表示集合中的元素。莆田學(xué)院網(wǎng)絡(luò)中心許振和13若兩個(gè)正規(guī)式若兩個(gè)正規(guī)式e e1 1和和e e2 2所表示的所表示的正規(guī)集相同，正規(guī)集相同，則說則說e e1 1和和e e2 2等價(jià)等價(jià), ,寫作寫作e e1 1=e=e2 2。例如：例如： e e1 1= (a= (a b)b)， e e2 2 = b = b a a又如：又如： e e1 1= b(ab= b(ab) ) , e , e2 2 =(ba) =(ba) b b e e1 1= (a= (a b)b) , e, e2 2 =(a=(a b b ) )

10、正規(guī)式的等價(jià)正規(guī)式的等價(jià)莆田學(xué)院網(wǎng)絡(luò)中心許振和14設(shè)設(shè)e e1 1、e e2 2、e e3 3為正規(guī)式，有如下運(yùn)算規(guī)則：為正規(guī)式，有如下運(yùn)算規(guī)則： 莆田學(xué)院網(wǎng)絡(luò)中心許振和15對(duì)于任意一個(gè)正規(guī)文法，存在一個(gè)同一語言的正規(guī)式。對(duì)每一個(gè)正規(guī)式，存在一個(gè)正規(guī)文法。即正規(guī)式正規(guī)文法 正規(guī)式正規(guī)式正規(guī)文法正規(guī)文法文法G=（VN，VT，P，S）令VT=，對(duì)正規(guī)式r，選擇一個(gè)非終結(jié)符S生成Sr，S為G的開始符號(hào)。 若x，y都是正規(guī)式，對(duì)形如Axy的產(chǎn)生式，寫成AxB，By。其中B VN二、正規(guī)文法與正規(guī)式轉(zhuǎn)換二、正規(guī)文法與正規(guī)式轉(zhuǎn)換* *莆田學(xué)院網(wǎng)絡(luò)中心許振和16 對(duì)形如Ax*y的產(chǎn)生式，重寫為： AxB A

11、y BxB By B為新的非終結(jié)符，B VN對(duì)形如Ax|y的產(chǎn)生式，重寫為： Ax Ay 不斷利用上述規(guī)則進(jìn)行變換即可。莆田學(xué)院網(wǎng)絡(luò)中心許振和17例：將Ra(a|d)*變換成正規(guī)文法。令S是文法開始符號(hào)。解：S a(a|d)*SaAA(a|d)*A(a|d)BA B(a|d)BB 根據(jù)上述規(guī)則1xa，y(a|d)*根據(jù)上述規(guī)則2x(a|d)y莆田學(xué)院網(wǎng)絡(luò)中心許振和18最后得到：SaAAaBAdBA BaBBdBB 莆田學(xué)院網(wǎng)絡(luò)中心許振和19 正規(guī)文法正規(guī)文法正規(guī)式正規(guī)式轉(zhuǎn)換規(guī)則：轉(zhuǎn)換規(guī)則： AxB，By 正規(guī)式為： A=xy AxA|y 正規(guī)式為： A=x*y Ax，Ay 正規(guī)式為： A=x|

12、y 例：文法GS：S aAS aA aAA dAA aA d轉(zhuǎn)換為正規(guī)式莆田學(xué)院網(wǎng)絡(luò)中心許振和20S aAS aA aAA dAA aA dSaA|aAaA|dAAa|dA(aA|dA)|(a|d) A(a|d)A|(a|d) A(a|d)*(a|d)根據(jù)上述規(guī)則3Ax，Ay推出A=x|y將它化為正規(guī)文法變成A (a|d)A|(a|d) 再根據(jù)上述規(guī)則2轉(zhuǎn)換xy (a|d)莆田學(xué)院網(wǎng)絡(luò)中心許振和21Sa( (a|d)*(a|d) |a =a(a|d)+|a =a(a|d)+|)= a(a|d)+將A代入SaA|a得到如下：莆田學(xué)院網(wǎng)絡(luò)中心許振和22 三、三、確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)DF

13、A 有窮自動(dòng)機(jī)( (也稱有限自動(dòng)機(jī)也稱有限自動(dòng)機(jī)) )作為一種識(shí)作為一種識(shí)別裝置別裝置，是詞法分析程序的工具和方法，能自動(dòng)識(shí)別（且是正確識(shí)別正確識(shí)別）正規(guī)集。即識(shí)別正規(guī)即識(shí)別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具。的自動(dòng)構(gòu)造尋找特殊的方法和工具。分為確定的有窮自動(dòng)機(jī)（確定的有窮自動(dòng)機(jī)（DFA）不確定的有窮自動(dòng)機(jī)（不確定的有窮自動(dòng)機(jī)（NFA） 莆田學(xué)院網(wǎng)絡(luò)中心許振和23一個(gè)確定的有窮自動(dòng)機(jī)M是一個(gè)五元組： M=（K，f，S，Z），其中： K是

14、一個(gè)有窮集，每個(gè)元素表示一個(gè)狀態(tài)；是一個(gè)有窮字母表，每個(gè)元素是一個(gè)輸入字符； f是轉(zhuǎn)換函數(shù)，是在KK上的映象上的映象，如： f(Ki ，a)= Kj (Ki, KjK)； S是初態(tài)，S K； ZK，是終態(tài)集。 含義：當(dāng)前狀態(tài)為Ki，輸入字符a，轉(zhuǎn)換為Kj狀態(tài)DFADFA映射的唯一性和初態(tài)的唯一性映射的唯一性和初態(tài)的唯一性莆田學(xué)院網(wǎng)絡(luò)中心許振和24 方法如下： 初始態(tài)用 “”或“”表示； 終態(tài)點(diǎn)用 “” 或“” 表示； 若f(Ki ，a)= Kj ，則從狀態(tài)點(diǎn)Ki 到Kj畫弧，標(biāo)記為a。1 1、單詞的構(gòu)成規(guī)則用狀態(tài)轉(zhuǎn)換圖表示、單詞的構(gòu)成規(guī)則用狀態(tài)轉(zhuǎn)換圖表示DFADFA等價(jià)表示法：等價(jià)表示法：DF

15、ADFA形式定義形式定義= =狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖= =狀態(tài)矩陣狀態(tài)矩陣莆田學(xué)院網(wǎng)絡(luò)中心許振和25狀態(tài)轉(zhuǎn)換圖(也稱狀態(tài)變遷圖狀態(tài)變遷圖)是一張有限方向圖。有限個(gè)狀態(tài)，用結(jié)點(diǎn)表示狀態(tài)，其中有一個(gè)初態(tài)有一個(gè)初態(tài)(初態(tài)用箭頭指出)，至少有一個(gè)終態(tài)至少有一個(gè)終態(tài)(終態(tài)用雙圈表示)。狀態(tài)之間用帶箭頭的弧線連結(jié)，弧線上標(biāo)記的字符表示在射出狀態(tài)下可能出現(xiàn)的輸入字符或字符類。識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖012字母字母或數(shù)字其它*莆田學(xué)院網(wǎng)絡(luò)中心許振和26一個(gè)狀態(tài)圖可用于識(shí)別一定的字符串，大多數(shù)程序設(shè)計(jì)語言的單詞符號(hào)都可以用轉(zhuǎn)換圖來識(shí)別。識(shí)別過程是識(shí)別過程是：從初始狀態(tài)0開始，若讀入一個(gè)字母，轉(zhuǎn)入1狀態(tài)，若再讀入字母或數(shù)

16、字，仍處于1狀態(tài)，否則轉(zhuǎn)向2狀態(tài)，結(jié)束一個(gè)標(biāo)識(shí)符的識(shí)別過程。狀態(tài)上的*表示多讀入一個(gè)符號(hào)。012字母字母或數(shù)字其它*莆田學(xué)院網(wǎng)絡(luò)中心許振和27例：DFA的M(S,U,V,Q,a,b,f,S,Q)其中f為：f(S,a)=U, f(S,b)=V, f(U,a)=Qf(U,b)=V, f(V,a)=U, f(V,b)=Qf(Q,a)=Q, f(Q,b)=Q狀態(tài)圖如下：a,baaabbbSUVQa,b莆田學(xué)院網(wǎng)絡(luò)中心許振和28Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.1 確定的FA（DFA）例2.21: 一個(gè)單部電梯對(duì)3層樓進(jìn)行控制的電梯控制系統(tǒng)的DFA描述。問題分析：用戶請(qǐng)求（輸入）上

17、1、上2、上3下1、下2、下3狀態(tài)設(shè)置（所處樓層）1層2層3層S1S2S3莆田學(xué)院網(wǎng)絡(luò)中心許振和29Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.1 確定的FA（DFA）S2S3S1上2/下2上3/下3上1/下1下1下2上3上2下1上3莆田學(xué)院網(wǎng)絡(luò)中心許振和302、用矩陣表示、用矩陣表示DFA :方法： 行表示狀態(tài) 列表示輸入字符 元素表示相應(yīng)狀態(tài)行和輸入字符下的新狀態(tài)。 “” 標(biāo)明初態(tài)，默認(rèn)第一行是初態(tài)。 終態(tài)行在表右端標(biāo)1，非終態(tài)標(biāo)0莆田學(xué)院網(wǎng)絡(luò)中心許振和31上例矩陣表示如下：abSUVUQVVUQQQQ字符狀態(tài)0001莆田學(xué)院網(wǎng)絡(luò)中心許振和32例：baSZa,b表示：f(S,a

18、)=Z f(S,b)=Z f(Z,a)=Z f(Z,b)=ZabSZZZZZ01寫成正規(guī)式是： (a+b)(a+b)*莆田學(xué)院網(wǎng)絡(luò)中心許振和33Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.1 確定的FA（DFA）電梯控制的狀態(tài)矩陣表示上1下1上2 下2上3下3S1* S1S2*S3*S1S1S1S2S2 S2S2S3S3S3 S3莆田學(xué)院網(wǎng)絡(luò)中心許振和343、DFA接接受（識(shí)別）的概念受（識(shí)別）的概念： 對(duì)于對(duì)于*中的任何字符串中的任何字符串t，若存在一條初態(tài)到若存在一條初態(tài)到某一終態(tài)的路，且這條路上所有弧的標(biāo)記符連接成某一終態(tài)的路，且這條路上所有弧的標(biāo)記符連接成的字符串等于的字符

19、串等于t，則稱，則稱t可為可為DFA M所接受。所接受。 若若M的初態(tài)同時(shí)又是終態(tài)，則空字可為的初態(tài)同時(shí)又是終態(tài)，則空字可為M所接所接受。受。莆田學(xué)院網(wǎng)絡(luò)中心許振和35 輸入字符串輸入字符串t（t表示成表示成Tt1形式，形式，T ，t1 *），在），在DFA M上運(yùn)行的定義為：上運(yùn)行的定義為：f（Q，Tt1）=f(f(Q,T),t1)，其中，其中Q K。4、接受（識(shí)別）的理解：接受（識(shí)別）的理解： 設(shè)設(shè)Q K，函數(shù)，函數(shù)f(Q, )=Q，則輸入字符串是，則輸入字符串是空串，并停留在原狀態(tài)上?？沾⑼Ａ粼谠瓲顟B(tài)上。 莆田學(xué)院網(wǎng)絡(luò)中心許振和36例：證明例：證明t t= =baabbaab被下圖的

20、被下圖的DFADFA所接受所接受。f f（S S，baabbaab）=f=f（f f（S S，b b），），aabaab） = f= f（V V，aabaab）= f= f（f f（V V，a a），），abab） =f=f（U U，abab）=f=f（f f（U U，a a），），b b） =f=f（Q Q，b b）= =Q QQ Q屬于終態(tài)。屬于終態(tài)。得證。得證。bSUVQabba, baa莆田學(xué)院網(wǎng)絡(luò)中心許振和37 DFA的確定性表現(xiàn)在：的確定性表現(xiàn)在： 對(duì)任何狀態(tài)s S，在讀入了輸入符號(hào)a 之后，能夠唯一地確定唯一地確定下一個(gè)狀態(tài) 映射函數(shù)：SS是一個(gè)單值單值函數(shù) 從狀態(tài)轉(zhuǎn)換圖來看，若

21、字母表含有n個(gè)輸入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有最多有n條弧條弧射出射出，而且每條弧以一個(gè)不同的輸入不同的輸入字符字符標(biāo)記。莆田學(xué)院網(wǎng)絡(luò)中心許振和38 DFA M所能接受的字符串的全體記為L(zhǎng)（M）稱為語言 （也即句子的集合）結(jié)論：結(jié)論： 上一個(gè)符上一個(gè)符號(hào)號(hào)串集串集V V 是正規(guī)的，當(dāng)且僅當(dāng)是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)存在一個(gè) 上的確定有窮自動(dòng)機(jī)上的確定有窮自動(dòng)機(jī)M M，使得，使得V=L(M)V=L(M) 文法是語言的生成系統(tǒng)，是從產(chǎn)生的觀點(diǎn)來描述語言的。 自動(dòng)機(jī)是語言的識(shí)別系統(tǒng)，是從識(shí)別的觀點(diǎn)來描述語言的文法和自動(dòng)機(jī)的對(duì)比文法和自動(dòng)機(jī)的對(duì)比莆田學(xué)院網(wǎng)絡(luò)中心許振和39四、四、 不確定的有窮自動(dòng)

22、機(jī)不確定的有窮自動(dòng)機(jī)NFA 一個(gè)不確定的有窮自動(dòng)機(jī)NFA M是一個(gè)五元組：M=（K，f，S，Z），其中： K是一個(gè)有窮集，每個(gè)元素表示一個(gè)狀態(tài)； 是一個(gè)有窮字母表，每個(gè)元素是一個(gè)輸入字符； f是一個(gè)從K*到到K上的子集上的子集的映象； S K，是一個(gè)非空初態(tài)集； Z K，是一個(gè)終態(tài)集。【要點(diǎn)】至少一個(gè)初態(tài)，若干個(gè)終態(tài)。莆田學(xué)院網(wǎng)絡(luò)中心許振和40映象映象映象 （1）DFA任何狀態(tài)都沒有沒有轉(zhuǎn)換，即沒有任何狀態(tài)可以不進(jìn)行輸入符號(hào)的匹配就直接進(jìn)入下一個(gè)狀態(tài)； （2）DFA對(duì)任何狀態(tài)S和任何輸入符號(hào)a，最多只有一條標(biāo)記為a的邊離開S，即轉(zhuǎn)換函數(shù)：S S是一個(gè)單值單值部分函數(shù)。 （3）DFA的初態(tài)唯一初

23、態(tài)唯一，NFA的初態(tài)為一集合。莆田學(xué)院網(wǎng)絡(luò)中心許振和41例子例子 NFA M=NFA M=（SS，P P，ZZ，00，11，f f，SS，PP，ZZ）其中其中 f f（S S，0 0）=P=Pf f（Z Z，0 0）=P=Pf f（P P，1 1）=Z=Zf f（Z Z，1 1）=P=Pf f（S S，1 1）=S=S，ZZ狀態(tài)圖表示狀態(tài)圖表示SPZ00,1111 * *上的符號(hào)串上的符號(hào)串t t被被NFA MNFA M接受接受若若t t * *，f(Sf(S0 0，t)=Pt)=P，其中，其中S S0 0 S S，P P Z Z，則稱，則稱t t為為NFA MNFA M所接受（識(shí)別）所接受（

24、識(shí)別）莆田學(xué)院網(wǎng)絡(luò)中心許振和42Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.2 非確定的FA(NFA)例2.24: 給出一個(gè)接收字符串a(chǎn)a*|bb*的NFA M，如下圖所示。對(duì)字符串a(chǎn)aa的接受路徑為0，1，2，2，2，接受路徑中邊的標(biāo)記是，a，a，a，它們的連接為字符串a(chǎn)aa，在連接中消失。abastart04132a莆田學(xué)院網(wǎng)絡(luò)中心許振和43*上的符號(hào)串t被NFA M接受（識(shí)別）: 對(duì)于*中的任何一個(gè)串t，若存在一條從某一初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo)記為的弧)等于t，則稱t可為NFA M所識(shí)別(讀出或接受)。 若M的某些結(jié)

25、點(diǎn)既是初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)；或者存在一條從某個(gè)初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的道路,其上所有弧的標(biāo)記均為，那么空字可為M所接受。莆田學(xué)院網(wǎng)絡(luò)中心許振和44 使用NFA判定某個(gè)輸入符號(hào)串的時(shí)候，可能出現(xiàn)不確定的情況：不知道下面選擇那個(gè)狀態(tài)。如果選擇不好，該輸入符號(hào)串可能不能到達(dá)終止?fàn)顟B(tài)。但是，我們不能說該輸入符號(hào)串不能被該NFA接受。 如果通過嘗試的方法，不斷試探來確定輸入符號(hào)串是否可被接受，那么判定的效率將降低。解決的方法是將NFA轉(zhuǎn)換為等價(jià)的DFA。 NFA M所能接受的符號(hào)串的全體記為L(zhǎng)(M)結(jié)論：上一個(gè)符號(hào)串集V 是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)上的不確定的有窮自動(dòng)機(jī)M，使得V=L(M)。莆田學(xué)院網(wǎng)絡(luò)

26、中心許振和45定理：設(shè)定理：設(shè)L為一個(gè)由不確定的有窮自動(dòng)機(jī)接受的集合，則存為一個(gè)由不確定的有窮自動(dòng)機(jī)接受的集合，則存在一個(gè)接受在一個(gè)接受L的確定的有窮自動(dòng)機(jī)。的確定的有窮自動(dòng)機(jī)。將將NFA轉(zhuǎn)換成接受同樣語言的轉(zhuǎn)換成接受同樣語言的DFA，這種算法稱為，這種算法稱為子集法。子集法。NFA與與DFA的等價(jià)性：的等價(jià)性：對(duì)于每個(gè)對(duì)于每個(gè)NFA M存在一個(gè)存在一個(gè)DFA M，使使L(M)=L(M)。NFA可以利用可以利用子集法進(jìn)行確定化子集法進(jìn)行確定化，對(duì)于一個(gè)，對(duì)于一個(gè)NFA M總可以構(gòu)總可以構(gòu)造一個(gè)等價(jià)的造一個(gè)等價(jià)的DFA M。NFA到到DFA構(gòu)造基本思路構(gòu)造基本思路：DFA的每一個(gè)狀態(tài)對(duì)于的每一個(gè)

27、狀態(tài)對(duì)于NFA的一的一組狀態(tài)。組狀態(tài)。DFA利用它的一個(gè)狀態(tài)去記錄在利用它的一個(gè)狀態(tài)去記錄在NFA讀入一個(gè)輸入讀入一個(gè)輸入符號(hào)后可能到達(dá)的所有狀態(tài)。符號(hào)后可能到達(dá)的所有狀態(tài)。五、五、NFANFA轉(zhuǎn)換為等價(jià)的轉(zhuǎn)換為等價(jià)的DFADFA（NFANFA確定化）確定化）莆田學(xué)院網(wǎng)絡(luò)中心許振和46 例例2-10 2-10 試把試把 例例2-92-9中構(gòu)造出來的中構(gòu)造出來的NFANFA確定化的確定化的狀態(tài)轉(zhuǎn)換表。狀態(tài)轉(zhuǎn)換表。 表表2-32-3就是所求的就是所求的DFA MDFA M的狀的狀態(tài)變遷函數(shù)。態(tài)變遷函數(shù)。確定化確定化前前確定化確定化后后莆田學(xué)院網(wǎng)絡(luò)中心許振和47將將NFA M進(jìn)行確定化時(shí)應(yīng)注意考慮進(jìn)

28、行確定化時(shí)應(yīng)注意考慮 弧弧，方法是求，方法是求 閉包閉包( -closure),將此閉包將此閉包(狀態(tài)子集狀態(tài)子集)作為作為DFA的一個(gè)狀態(tài)使用，而的一個(gè)狀態(tài)使用，而將將NFA的狀態(tài)之間轉(zhuǎn)換為閉包之間的轉(zhuǎn)換。的狀態(tài)之間轉(zhuǎn)換為閉包之間的轉(zhuǎn)換。狀態(tài)集合狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算：的幾個(gè)有關(guān)運(yùn)算：1、狀態(tài)集合、狀態(tài)集合I的的 -閉包，表示為閉包，表示為 -closure(I)，定義為一狀，定義為一狀態(tài)集，是狀態(tài)集態(tài)集，是狀態(tài)集I中的任何狀態(tài)中的任何狀態(tài)S經(jīng)任意條經(jīng)任意條 弧而能到達(dá)的狀弧而能到達(dá)的狀態(tài)的集合。態(tài)的集合。狀態(tài)集合狀態(tài)集合I的任何狀態(tài)的任何狀態(tài)S都屬于都屬于 -closure(I)2、狀態(tài)

29、集合、狀態(tài)集合I的的a弧轉(zhuǎn)換，表示為弧轉(zhuǎn)換，表示為move(I,a)定義為狀態(tài)集定義為狀態(tài)集合合J，其中，其中J是所有那些可從是所有那些可從I的某一狀態(tài)經(jīng)過一條的某一狀態(tài)經(jīng)過一條a弧而到弧而到達(dá)的狀態(tài)的全體。達(dá)的狀態(tài)的全體。帶 弧的弧的NFA確定化方法：莆田學(xué)院網(wǎng)絡(luò)中心許振和48Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.3 NFA確定化例2.25: 有NFA M如下圖所示。12385467aaa莆田學(xué)院網(wǎng)絡(luò)中心許振和49Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.3 NFA確定化設(shè) I= 1,5則 -closure(1,5)=1,2,5,6設(shè) I=5則 -closur

30、e(I) = -closure(5)= 5, 6, 2設(shè) I=1則 -closure(1) = 1, 2-closure (5) -closure (1)莆田學(xué)院網(wǎng)絡(luò)中心許振和50則Ia =-closure（I）=-closure（3）= 3,8 Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.3 NFA確定化例2.26: 有NFA M如例2.25所示。設(shè)I=1則Ia =-closure（I）=-closure（3 , 4 , 5）= 2, 3, 4, 5, 6,7,8 設(shè)I=2,5莆田學(xué)院網(wǎng)絡(luò)中心許振和51Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.3 NFA確定化綜述

31、求Ia步驟：(1) 求-closure(I)；(2) 求J；(3) 求-closure(J)；NFA確定化關(guān)鍵：(1) 消去??；(2) 解決映射不唯一問題。-closure(I)求Ia莆田學(xué)院網(wǎng)絡(luò)中心許振和52Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.3 NFA確定化子集法對(duì)NFA M =（S, 1, 2, , n , f, S0, Z）設(shè)一矩陣形式的表：II 1I 2I n-closure(S0)Step1:初始化莆田學(xué)院網(wǎng)絡(luò)中心許振和53Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.3 NFA確定化II 1I 2I n-closure(S0)I11I12I1nI11

32、I12I1nStep2:求InI2nI3n莆田學(xué)院網(wǎng)絡(luò)中心許振和54Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.3 NFA確定化Step3: 重新命名對(duì)求得的矩陣（DFA M）的第一列各狀態(tài)子集重新命名，然后代入相應(yīng)的狀態(tài)矩陣元素；第一列第一行為DFA M 的惟一初態(tài)；含有原M終態(tài)的I為M終態(tài)。莆田學(xué)院網(wǎng)絡(luò)中心許振和55Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.3 NFA確定化例2.27: 有NFA M如下圖所示。12385467aaa莆田學(xué)院網(wǎng)絡(luò)中心許振和56Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.3 NFA確定化IIa2, 3, 4, 5, 6,

33、7, 8 3, 8120 -closure(S0)=1,21*2*2, 3, 4, 5, 6, 7, 8 3, 8莆田學(xué)院網(wǎng)絡(luò)中心許振和57例1、將下圖的NFA確定化為DFA。 T0= -closure(X)=x,1,2move(T0,a)=1 move(T0,b)=1,3T1= -closure(move(T0,a)= -closure(1)=1,2T2= -closure(move(T0,b)= -closure(1,3)=1,2,3move(T1,a)=1 同同T1 move(T1,b)=1,3 同同T2move(T2,a)=1,y move(T2,b)=1,3 同同T2T3= -clo

34、sure(move(T2,a)= -closure(1,y)=1,2,ymove(T3,a)=1 同同T1 move(T3,b)=1,3 同同T2莆田學(xué)院網(wǎng)絡(luò)中心許振和58I IIaIaIbIbX X1 12 23 31 11 13 31 12 22 22 22 2IIaIb狀態(tài)狀態(tài)X,1,21,2.1,2,31,2,Y1,2.1,2.1,2,Y1,2.1,2,31,2,31,2,31,2,3X123莆田學(xué)院網(wǎng)絡(luò)中心許振和59使用圖使用圖4.4的的NFAN的狀態(tài)集合來理解上述兩個(gè)運(yùn)算：的狀態(tài)集合來理解上述兩個(gè)運(yùn)算： -closure(0)=0,1,2,4,7令令A(yù)=0,1,2,4,7, mov

35、e(A,a)=3,8 -closure(3,8)=1,2,3,4,6,7,8圖圖4.4NFAN莆田學(xué)院網(wǎng)絡(luò)中心許振和60 ab0 00124701247T0=0124738385 53838123467812346785 5124567124567T1=1234678T1=123467838385959595912456791245679T2=124567T2=12456738385 5T3=1245679T3=124567938385105105105101245671012456710T4=12456710T4=1245671038385 5例例2 對(duì)圖對(duì)圖4.4的的NFA N構(gòu)構(gòu)造子集造

36、子集莆田學(xué)院網(wǎng)絡(luò)中心許振和61IaIbT0=012471234678 T1124567 T2T1=1234678T1=12346781234678 T11245679 T3T2=124567T2=1245671234678 T1124567 T2T3=1245679T3=12456791234678 T112456710 T4T4=124567T4=12456710101234678 T1124567 T2莆田學(xué)院網(wǎng)絡(luò)中心許振和62圖圖4.6DFAMabT0=012471234678 T1124567 T2T1=1234678T1=12346781234678 T11245679 T3T2=1

37、24567T2=1245671234678 T1124567 T2T3=1245679T3=12456791234678 T112456710 T4T4=12456710T4=124567101234678 T1124567 T2莆田學(xué)院網(wǎng)絡(luò)中心許振和63六、確定有窮自動(dòng)機(jī)六、確定有窮自動(dòng)機(jī)DFA的化簡(jiǎn)的化簡(jiǎn)（DFA最小化）最小化） 說一個(gè)有窮自動(dòng)機(jī)是化簡(jiǎn)了的，即是說，它說一個(gè)有窮自動(dòng)機(jī)是化簡(jiǎn)了的，即是說，它沒有多余狀態(tài)沒有多余狀態(tài)并且它的狀態(tài)中并且它的狀態(tài)中沒有兩個(gè)是互相等沒有兩個(gè)是互相等價(jià)的價(jià)的。一個(gè)有窮自動(dòng)機(jī)可以通過消除多余狀態(tài)和。一個(gè)有窮自動(dòng)機(jī)可以通過消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成

38、一個(gè)最小的與之等價(jià)的有合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī)。窮自動(dòng)機(jī)。 將多余狀態(tài)消除而形成一個(gè)最小的等價(jià)的DFA?；?jiǎn)不僅是去除死狀態(tài)，不可能到達(dá)狀態(tài)，還包括狀態(tài)的合并。 DFA的最小化就是尋求最小狀態(tài)的最小化就是尋求最小狀態(tài)DFA莆田學(xué)院網(wǎng)絡(luò)中心許振和641、多余狀態(tài)的概念： 所謂有窮自動(dòng)機(jī)的多余狀態(tài)，是指這樣的狀態(tài)：從自動(dòng)所謂有窮自動(dòng)機(jī)的多余狀態(tài)，是指這樣的狀態(tài)：從自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)；或機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)。者從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)。 如下圖中的S4狀態(tài)是多余的。在圖中，沒有一

39、個(gè)狀態(tài)能到達(dá)S4。當(dāng)S4是多余時(shí)，又可以推出S6是多余的。同樣也可以推出S8也是多余的。 最小狀態(tài)最小狀態(tài)DFA的含義的含義: 1.沒有多余狀態(tài)沒有多余狀態(tài)(死狀態(tài)死狀態(tài)) 2.沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）莆田學(xué)院網(wǎng)絡(luò)中心許振和6501S0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6S8S01S7S0S11S8S3S6001S0S1S50S1S2S71S2S2S51S3S5S70S5S3S10S7S0S11化簡(jiǎn)后的結(jié)果：左右等價(jià)莆田學(xué)院網(wǎng)絡(luò)中心許振和662、等價(jià)的條件（狀態(tài)、等價(jià)的條件（狀態(tài)S和和T） 兩個(gè)狀態(tài)兩個(gè)

40、狀態(tài)s s和和t t等價(jià)：滿足等價(jià)：滿足兼容性兼容性同是終態(tài)或同是非終態(tài)同是終態(tài)或同是非終態(tài)傳播性傳播性從從s s出發(fā)讀入某個(gè)出發(fā)讀入某個(gè)a a a a和從和從t t出發(fā)出發(fā)讀入某個(gè)讀入某個(gè)a a到達(dá)的狀態(tài)等價(jià)。到達(dá)的狀態(tài)等價(jià)。莆田學(xué)院網(wǎng)絡(luò)中心許振和673、等價(jià)的方法（分割法）等價(jià)的方法（分割法）方法：將DFA的狀態(tài)分割成一些互不相交的子集。把一個(gè)把一個(gè)DFADFA（不含多余狀態(tài)）的狀態(tài)分成一些不（不含多余狀態(tài)）的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的

41、。是等價(jià)的。分割法的核心 把DFA的全部狀態(tài)劃分成一些互不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的（不等價(jià)），而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的.莆田學(xué)院網(wǎng)絡(luò)中心許振和68DFA化簡(jiǎn)（最小化方法最小化方法） 算法算法： 所有狀態(tài)分成兩個(gè)子集終態(tài)集和非終態(tài)集； 運(yùn)用判定狀態(tài)等價(jià)的原則分別對(duì)兩個(gè)子集的狀態(tài)進(jìn)行分析和劃分，若發(fā)現(xiàn)某個(gè)狀態(tài)與其它狀態(tài)不等價(jià)，則將其作為一個(gè)新的狀態(tài)子集，如果無法區(qū)分，則放在同一子集中； 從每個(gè)子集中選出一個(gè)狀態(tài)做代表，即可構(gòu)成簡(jiǎn)化的DFA； 含有原來初態(tài)的子集仍為初態(tài)，各終態(tài)的子集仍為終態(tài)。莆田學(xué)院網(wǎng)絡(luò)中心許振和69Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)

42、基礎(chǔ)2.2.4 DFA的化簡(jiǎn)Step1: 形成基本劃分。劃分為終態(tài)集和非終態(tài)集。P0 = （ 0,1 , 2）考察 ： 0,1a =1 0,10,1b =2 2a例1： 設(shè)確定有限自動(dòng)機(jī)DFA M ，如圖所示。bbaa021Step2: 重新命名。令 0,1為0，令2為1?；緞澐植豢蓪?duì) 0,1 再分莆田學(xué)院網(wǎng)絡(luò)中心許振和70Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.4 DFA的化簡(jiǎn)baa10化簡(jiǎn)后的DFA M莆田學(xué)院網(wǎng)絡(luò)中心許振和71DBASaaabbbba,CDBAEFSbaaaaaabbbbbba例例2：化簡(jiǎn)下圖的：化簡(jiǎn)下圖的DFA莆田學(xué)院網(wǎng)絡(luò)中心許振和721643257a

43、aaaaaabbbbbbb例例3：將下圖中的：將下圖中的DFA M最小化。最小化。莆田學(xué)院網(wǎng)絡(luò)中心許振和73Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.4 DFA的化簡(jiǎn)第一步，對(duì)M的狀態(tài)形成基本劃分： 設(shè)p是基本劃分。將 p分成q , q2，即p=(1, 2, 3, 4 , 5, 6, 7 )= ( q1,q2 )第二步，對(duì)q , q2考察知：對(duì)p的q，I=1時(shí) Ia= 6I=2時(shí) Ia= 7I=3時(shí) Ia= 1I=4時(shí) Ia= 4Ib= 3Ib= 3Ib= 5Ib= 6莆田學(xué)院網(wǎng)絡(luò)中心許振和74Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.4 DFA的化簡(jiǎn)對(duì)q1形成新的

44、劃分：q1=(q3, q4)=（1, 2，3, 4）對(duì)p的q2， I=5時(shí) Ia=7 Ib=3I=6時(shí) Ia=4 Ib=1I=7時(shí) Ia=4 Ib=2在輸入a或b的情況下， q2中的狀態(tài)5與狀態(tài) 6,7 是不等價(jià)的，構(gòu)成q2新的劃分：莆田學(xué)院網(wǎng)絡(luò)中心許振和75Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2.4 DFA的化簡(jiǎn)q2新的劃分：q2 =( q5, q6 )=（5，6, 7）由此，對(duì)基本劃分p0 經(jīng)考察且劃分后，形成新的劃分p1：p1 =（q3，q4，q5，q6）= ( 1,2，3,4，5，6,7 )莆田學(xué)院網(wǎng)絡(luò)中心許振和76Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.2 自動(dòng)機(jī)基礎(chǔ)2.2

45、.4 DFA的化簡(jiǎn)第三步，對(duì)新形成的劃分p1重復(fù)上述第二步，則對(duì)p1 中q4的狀態(tài) 3,4 在輸入字符a的情況下考察其是不等價(jià)的，再劃分為q4=（q7, q8）=（3, 4）對(duì)劃分p1 經(jīng)考察且劃分后，形成新的劃分p2：p2 =（q3, q5, q6, q7, q8 ）= ( 1,2, 5, 6,7 , 3, 4 )莆田學(xué)院網(wǎng)絡(luò)中心許振和771643257aaaaaaabbbbbbb16435aaaaabbbbb至此所有狀態(tài)集中的狀態(tài)皆為等價(jià)狀態(tài)。莆田學(xué)院網(wǎng)絡(luò)中心許振和78 合并狀態(tài)注意：a、由于一個(gè)子集中，各狀態(tài)等價(jià)，故只需將原進(jìn)入該子集中各狀態(tài)的弧都改為進(jìn)入所選的狀態(tài)，子集中各狀態(tài)射出的弧

46、均改為從該狀態(tài)射出。b、含有原來初態(tài)的子集仍為初態(tài)，含原終態(tài)原終態(tài)的子集仍為終終態(tài)態(tài)莆田學(xué)院網(wǎng)絡(luò)中心許振和79例例4：將下圖中的：將下圖中的DFA M最小化。最小化。1402357600000000111111莆田學(xué)院網(wǎng)絡(luò)中心許振和801、一個(gè)終態(tài)（可接受態(tài)）組成，一個(gè)非終態(tài)組成。 P0(0,1,2,3,5,4,6,7)2、0,1狀態(tài)輸入1到2狀態(tài),2,5輸入1到4狀態(tài),3狀態(tài)輸入1為,2狀態(tài)和4狀態(tài)屬于不同的子集,P1=(0,1,2,5,3)3、4,7輸入1到狀態(tài)4,6輸入1到, P3=(4,7,6)0,1、2,5、 3、4,7、 6都不可再分了,分別用A,B,C,D,E表示,簡(jiǎn)化后圖如下:

47、莆田學(xué)院網(wǎng)絡(luò)中心許振和811402357600000000111111ADBCE00000111莆田學(xué)院網(wǎng)絡(luò)中心許振和82 正規(guī)式和FA之間也可以互相轉(zhuǎn)換，轉(zhuǎn)換的方法是從已知的正規(guī)式先構(gòu)造出等價(jià)的-NFA（本節(jié)），去掉-NFA中的空動(dòng)作變換為不含遷移的NFA，然后再把NFA轉(zhuǎn)化為DFA，最后再對(duì)DFA化簡(jiǎn)，求得最小DFA。 上述各種轉(zhuǎn)換關(guān)系可用圖2-8表示。七、七、正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性 莆田學(xué)院網(wǎng)絡(luò)中心許振和83正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性：正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性： 對(duì)于對(duì)于上的上的NFA MNFA M，可以構(gòu)造一個(gè)，可以構(gòu)造一個(gè)上的正規(guī)式上的正規(guī)式R R，使

48、得，使得L(R)=L(M)L(R)=L(M)。 對(duì)于對(duì)于上的每個(gè)正規(guī)式上的每個(gè)正規(guī)式R R，可以構(gòu)，可以構(gòu)造一個(gè)造一個(gè)上的上的NFA MNFA M，使得，使得L(M)=L(R)L(M)=L(R)。莆田學(xué)院網(wǎng)絡(luò)中心許振和84Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.3 正規(guī)式與自動(dòng)機(jī)2.3.2 正規(guī)式與FA(1) 增加結(jié)點(diǎn)X，并從 X引弧到達(dá)S0中的所有狀態(tài)；(2) 增加結(jié)點(diǎn) Y，并從Z中所有狀態(tài)引弧 到達(dá) Y；step1: 將NFA M進(jìn)行拓廣；1、在NFA M上構(gòu)照正規(guī)式R。即從L(M) L(R）方法：在每一條弧上用一個(gè)正規(guī)式作標(biāo)記。規(guī)則如下：莆田學(xué)院網(wǎng)絡(luò)中心許振和85Y3aXstep2: 利用利用

49、替換規(guī)則一替換規(guī)則一逐步消去逐步消去 M中的結(jié)和弧，并中的結(jié)和弧，并用正規(guī)式代替原來用正規(guī)式代替原來M 中的弧標(biāo)記，直至只剩下中的弧標(biāo)記，直至只剩下結(jié)為止。結(jié)為止。XY莆田學(xué)院網(wǎng)絡(luò)中心許振和86(1)123R1R213R1R2(2)12R1R221R1|R221R1+R2替換為或(3)321R1R2R331R1R2*R3替換為替換為替換規(guī)則一替換規(guī)則一莆田學(xué)院網(wǎng)絡(luò)中心許振和87Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.3 正規(guī)式與自動(dòng)機(jī)2.3.2 正規(guī)式與FAY1234bbaa0a,b例1: 有NFA M 如下圖所示。a,ba,b莆田學(xué)院網(wǎng)絡(luò)中心許振和88Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.3 正規(guī)式與

50、自動(dòng)機(jī)2.3.2 正規(guī)式與FAY1234bbaa0a,ba,ba,bX莆田學(xué)院網(wǎng)絡(luò)中心許振和89Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.3 正規(guī)式與自動(dòng)機(jī)2.3.2 正規(guī)式與FAY123baa,b4X(a|b)*b(a|b)*a用規(guī)則(3)消去0結(jié)和a,b弧a,b莆田學(xué)院網(wǎng)絡(luò)中心許振和90Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.3 正規(guī)式與自動(dòng)機(jī)2.3.2 正規(guī)式與FA用規(guī)則(3)消去2,4結(jié)和2個(gè)a|b弧Y13X(a|b)*b(a|b)*ab(a|b)*a(a|b)*莆田學(xué)院網(wǎng)絡(luò)中心許振和91Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.3 正規(guī)式與自動(dòng)機(jī)2.3.2 正規(guī)式與FA(a|b)*aa(a|b)*YX用規(guī)

51、則(1)消去1,3結(jié)(a|b)*b b(a|b)*莆田學(xué)院網(wǎng)絡(luò)中心許振和92Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.3 正規(guī)式與自動(dòng)機(jī)2.3.2 正規(guī)式與FA用規(guī)則(2)消去2個(gè)弧(a|b)*bb(a|b)*|(a|b)*aa(a|b)*YYX用分配率實(shí)施化簡(jiǎn)(a|b)*(aa|bb)(a|b)*X正規(guī)式正規(guī)式莆田學(xué)院網(wǎng)絡(luò)中心許振和93例2: L(M)如下圖：求正規(guī)式R，使L(R)=L(M).解：aba,baba,bxyya|bxa|byx(a|b)(a|b)*因此：L(R)= (a+b)(a+b)*莆田學(xué)院網(wǎng)絡(luò)中心許振和94 例4：L(M)如下圖，求L(R)-+abbaaba,b莆田學(xué)院網(wǎng)絡(luò)中心許

52、振和95解：-+abbaaba,b-abbaaba,bxy莆田學(xué)院網(wǎng)絡(luò)中心許振和96-abbaa|ba,bxy-a|bababbaxy(ababba)*(a+b)xy所以所以 L(R) = (ababba)*(a+b) =(a+b)*(a+b)=(a+b)+莆田學(xué)院網(wǎng)絡(luò)中心許振和97例例5：L(M) 如下圖，求如下圖，求L(R) .-+abbbbabbaa,ba解：-+abbbbabbaa,ba莆田學(xué)院網(wǎng)絡(luò)中心許振和98abba+abb+bb+a,b-aa*(abba+abb+bb)(a+b)*+-所以 L(R) = a*(abba+abb+bb)(a+b)* 注：注：abba+abb+bb

53、不能把不能把bb提取出來提取出來莆田學(xué)院網(wǎng)絡(luò)中心許振和992、L(R) NFA，從正規(guī)式，從正規(guī)式R構(gòu)造構(gòu)造NFA由正規(guī)式V直接形成拓廣的FA狀態(tài)圖。構(gòu)造上的NFA M，使得L(M)=L(V);方法如下：方法如下：莆田學(xué)院網(wǎng)絡(luò)中心許振和100Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.3 正規(guī)式與自動(dòng)機(jī)2.3.2 正規(guī)式與FAai1) 若V是或上的字符ai , 則2) 若1）不成立，則V具有V1|V2，V1V2，(V1)*形式，按照替換規(guī)則二分解V；3） 對(duì)新產(chǎn)生的弧標(biāo)記重復(fù)1）、2），直到?jīng)]有新的弧和結(jié)產(chǎn)生為止。得到V相應(yīng)的M，且L(M)=L(v).XYXY莆田學(xué)院網(wǎng)絡(luò)中心許振和101Ch2 形式語言

54、自動(dòng)機(jī)理論基礎(chǔ)2.3 正規(guī)式與自動(dòng)機(jī)2.3.2 正規(guī)式與FAR1R1|R2ABR2AB替換為R1*ABACB替換為R1ACR2BR1R2AB替換為R1替換規(guī)則二(1)莆田學(xué)院網(wǎng)絡(luò)中心許振和102例1：L(R) =(a+b)*abb，構(gòu)造NFA使L(N)=L(R)解：xy(a+b)*abbxyabba,bxyabbabxyababb莆田學(xué)院網(wǎng)絡(luò)中心許振和103yababb例2： L(R): b(a+b)* 求L(M)-+ba,baa,b莆田學(xué)院網(wǎng)絡(luò)中心許振和104例3：L(R) =(a+b)b(a+b)* 求L(M)。 ababa,ba,b例4： L(R) =(a+b)*(aa+bb)(a+b)

55、*構(gòu)造L(N)使與L(R) 等價(jià)。莆田學(xué)院網(wǎng)絡(luò)中心許振和105xy(a+b)*(aa+bb)(a+b)*xy(a+b)*aa+bb(a+b)*xyaabba,ba,b莆田學(xué)院網(wǎng)絡(luò)中心許振和106xya baaabbb-+a baaabbb莆田學(xué)院網(wǎng)絡(luò)中心許振和107八、正規(guī)文法和有窮自動(dòng)機(jī)的等價(jià)性八、正規(guī)文法和有窮自動(dòng)機(jī)的等價(jià)性采用下面的規(guī)則可以從正規(guī)文法采用下面的規(guī)則可以從正規(guī)文法G直接構(gòu)造一個(gè)有窮直接構(gòu)造一個(gè)有窮自動(dòng)機(jī)自動(dòng)機(jī)NFAM；使得；使得L（M）L（G）：）：M M的字母表與的字母表與G G的終結(jié)符集相同的終結(jié)符集相同為為G G中的每個(gè)非終結(jié)符生成中的每個(gè)非終結(jié)符生成M M的一個(gè)狀態(tài)

56、，的一個(gè)狀態(tài)，G G的開始符的開始符S S是開是開始狀態(tài)始狀態(tài)S S增加一個(gè)新狀態(tài)增加一個(gè)新狀態(tài)Z Z，作為，作為NFANFA的終態(tài)的終態(tài)對(duì)對(duì)G G中的形如中的形如A A tBtB的規(guī)則（其中的規(guī)則（其中t t為終結(jié)符或?yàn)榻K結(jié)符或 ，A A和和B B為為非終結(jié)符的產(chǎn)生式），構(gòu)造非終結(jié)符的產(chǎn)生式），構(gòu)造M M的一個(gè)轉(zhuǎn)換函數(shù)的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=Bf(A,t)=B對(duì)對(duì)G G中形如中形如A A t t的產(chǎn)生式，構(gòu)造的產(chǎn)生式，構(gòu)造M M的一個(gè)轉(zhuǎn)換函數(shù)的一個(gè)轉(zhuǎn)換函數(shù)f(A,tf(A,t)=Z)=Z莆田學(xué)院網(wǎng)絡(luò)中心許振和108 例例2-6 2-6 已知正規(guī)文法已知正規(guī)文法G3G3(S(S，A A，BB，aa，b b，c c，P P，S) S)，其中，其中P P內(nèi)包含以下產(chǎn)生式：內(nèi)包含以下產(chǎn)生式：根據(jù)上述轉(zhuǎn)換方法，與G3等價(jià)的FA M為：其中函數(shù)的定義式為：莆田學(xué)院網(wǎng)絡(luò)中心許振