詞法分析程序詞法分析程序

1、第四章第四章 詞法分析詞法分析 詞法分析程序的設(shè)計(jì)詞法分析程序的設(shè)計(jì) 單詞的描述工具單詞的描述工具 有限自動(dòng)機(jī)有限自動(dòng)機(jī) 正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性 正規(guī)文法和有窮自動(dòng)機(jī)間的轉(zhuǎn)換正規(guī)文法和有窮自動(dòng)機(jī)間的轉(zhuǎn)換 詞法分析程序的自動(dòng)構(gòu)造工具詞法分析程序的自動(dòng)構(gòu)造工具4.1 詞法分析程序的設(shè)計(jì)詞法分析程序的設(shè)計(jì) 詞法分析（詞法分析（lexical analysis）源程序字符并按照構(gòu)詞規(guī)則切分成源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。一系列單詞。單詞單詞是語言中具有獨(dú)立意義的是語言中具有獨(dú)立意義的最小單位最小單位，包，包括保留字、標(biāo)識(shí)符、運(yùn)算符、標(biāo)點(diǎn)符號(hào)和常括保留字、標(biāo)識(shí)符

2、、運(yùn)算符、標(biāo)點(diǎn)符號(hào)和常量等。量等。詞法分析是編譯過程中的一個(gè)階段，在語法詞法分析是編譯過程中的一個(gè)階段，在語法分析前進(jìn)行。也可以和語法分析結(jié)合在一起分析前進(jìn)行。也可以和語法分析結(jié)合在一起作為一遍，由語法分析程序調(diào)用詞法分析程作為一遍，由語法分析程序調(diào)用詞法分析程序來獲得當(dāng)前單詞供語法分析使用。序來獲得當(dāng)前單詞供語法分析使用。詞法分析程序詞法分析程序源程序源程序詞法分析程序詞法分析程序語法分析程序語法分析程序Tokenget token.主要任務(wù)：主要任務(wù)：讀源程序，產(chǎn)生單詞符號(hào)讀源程序，產(chǎn)生單詞符號(hào)其他任務(wù)：其他任務(wù)：濾掉空格，跳過注釋、換行符濾掉空格，跳過注釋、換行符追蹤換行標(biāo)志，復(fù)制出錯(cuò)源

3、程序，追蹤換行標(biāo)志，復(fù)制出錯(cuò)源程序，宏展開，宏展開，單詞符號(hào)單詞符號(hào) 單詞符號(hào)一般可分為下列五種：?jiǎn)卧~符號(hào)一般可分為下列五種：（）：）：begin, end, if, while, var等等：各種名稱，如常量名、變量名、過：各種名稱，如常量名、變量名、過程名等程名等（量）：（量）：25, 3.1415, TRUE, “ABC”等等：如：如 + - * / =等等：逗號(hào)，分號(hào)，括號(hào)等：逗號(hào)，分號(hào)，括號(hào)等 輸出表示輸出表示（單詞種別，單詞自身的值）（單詞種別，單詞自身的值）。 A:=B+2 (Id,指向指向A的符號(hào)表的入口指針）的符號(hào)表的入口指針）(Becomes,) (Id,指向指向B的符號(hào)表

4、的入口指針的符號(hào)表的入口指針) (Num, 2) 詞法分析工作獨(dú)立的原因：詞法分析工作獨(dú)立的原因： 簡(jiǎn)化設(shè)計(jì)簡(jiǎn)化設(shè)計(jì) 改進(jìn)編譯效率改進(jìn)編譯效率 增加編譯系統(tǒng)的可移植性增加編譯系統(tǒng)的可移植性 單詞的描述工具單詞的描述工具 正規(guī)文法：正規(guī)文法：文法文法G=（VN，VT，P，S），），P中每一產(chǎn)生中每一產(chǎn)生式的式的形式都為：形式都為：或或，其中其中AVAVN N ，BVBVN N ，aVaVT T幾類單詞的描述幾類單詞的描述：標(biāo)識(shí)符標(biāo)識(shí)符l | l字母數(shù)字字母數(shù)字字母數(shù)字字母數(shù)字l | d | l字母數(shù)字字母數(shù)字| d 字母數(shù)字字母數(shù)字：無符號(hào)整數(shù)無符號(hào)整數(shù)d | d無符號(hào)整數(shù)無符號(hào)整數(shù)：運(yùn)算符運(yùn)算

5、符 + | - | * | / | = | 等號(hào)等號(hào)等號(hào)等號(hào) =：界符界符 , | ; | ( | ) |：無符號(hào)實(shí)數(shù)無符號(hào)實(shí)數(shù) d 余留無符號(hào)數(shù)余留無符號(hào)數(shù)| . 十進(jìn)小數(shù)十進(jìn)小數(shù)| e指數(shù)部分指數(shù)部分余留無符號(hào)數(shù)余留無符號(hào)數(shù) d 余留無符號(hào)數(shù)余留無符號(hào)數(shù)| . 十進(jìn)小數(shù)十進(jìn)小數(shù)| e指數(shù)部分指數(shù)部分|十進(jìn)小數(shù)十進(jìn)小數(shù) d 余留十進(jìn)小數(shù)余留十進(jìn)小數(shù)余留十進(jìn)小數(shù)余留十進(jìn)小數(shù) e指數(shù)部分指數(shù)部分| d 余留十進(jìn)小數(shù)余留十進(jìn)小數(shù)| 指數(shù)部分指數(shù)部分 d 余留整指數(shù)余留整指數(shù)| s整指數(shù)整指數(shù)整指數(shù)整指數(shù) d 余留整指數(shù)余留整指數(shù)余留整指數(shù)余留整指數(shù) d 余留整指數(shù)余留整指數(shù) |其中其中s表示正或負(fù)

6、號(hào)。表示正或負(fù)號(hào)。如如 25.55e+5 和和 2.1正規(guī)式正規(guī)式(regular expression) 定義（定義（正規(guī)式正規(guī)式和它所表示的和它所表示的正規(guī)集正規(guī)集）：）：設(shè)字母標(biāo)為設(shè)字母標(biāo)為 ，輔助字母表，輔助字母表 = ， ， ， ， ， ， 。v1。 和和 都是都是 上的正規(guī)式，它們所表示的正規(guī)集分別上的正規(guī)式，它們所表示的正規(guī)集分別為為 和和 ；v2。任何。任何a ，a是是 上的一個(gè)正規(guī)式，它所表示的正規(guī)上的一個(gè)正規(guī)式，它所表示的正規(guī)集為集為a；v3。假定假定e1和和e2都是都是 上的正規(guī)式，它們所表示的正規(guī)集上的正規(guī)式，它們所表示的正規(guī)集分別為分別為L(zhǎng)(e1)和和L(e2)，那么

7、，那么，(e1), e1 e2, e1 e2, e1 也都是正也都是正規(guī)式規(guī)式,它們所表示的正規(guī)集分別為它們所表示的正規(guī)集分別為L(zhǎng)(e1), L(e1)L(e2), L(e1)L(e2)和和(L(e1) 。v4。僅由有限次使用上述三步驟而定義的表達(dá)式才是。僅由有限次使用上述三步驟而定義的表達(dá)式才是 上上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是的正規(guī)式，僅由這些正規(guī)式所表示的字集才是 上的正上的正規(guī)集。規(guī)集。 (e1), e1 e2, e1 e2, e1 L(e1), L(e1)L(e2), L(e1)L(e2)和和(L(e1) 。 其中的其中的“ ”讀為讀為“或或”（也有使用（也有使用“+”代

8、替代替 “ ” 的）；的）；“ ”讀為讀為“連接連接”；“ ”讀為讀為“閉包閉包”（即，任意有限次（即，任意有限次的自重復(fù)連接）。在不致混淆時(shí)，括號(hào)可省去，但規(guī)定算符的自重復(fù)連接）。在不致混淆時(shí)，括號(hào)可省去，但規(guī)定算符的優(yōu)先順序?yàn)榈膬?yōu)先順序?yàn)椤?”、“ ”、“ ” 。連接符。連接符“ ”一般可一般可省略不寫。省略不寫?！?”、“ ”和和“ ” 都是左結(jié)合的。都是左結(jié)合的。 例例4.2 令令 =a，b， 上的正規(guī)式和相應(yīng)的正上的正規(guī)式和相應(yīng)的正規(guī)集的例子有：規(guī)集的例子有：正規(guī)式正規(guī)式 正規(guī)集正規(guī)集a aa ba,bab ab(a b)(a b)aa,ab,ba,bba ,a,a, 任意個(gè)任意個(gè)a

9、的串的串(a b) ,a,b,aa,ab 所有由所有由a 和和b組成的串組成的串(a b) (aa bb)(a b) 上所有含有兩個(gè)相繼上所有含有兩個(gè)相繼 的的a或兩個(gè)相繼的或兩個(gè)相繼的b組成組成 的串的串 例例 =l，d，r=l(l d) 定義的正規(guī)集定義的正規(guī)集: l,ll,ld,ldd,（標(biāo)識(shí)符）標(biāo)識(shí)符） 例例4.3 =d，.，e，+，-,則則 上的正規(guī)上的正規(guī)式式 表示的是表示的是無符號(hào)數(shù)的集合。其中無符號(hào)數(shù)的集合。其中d為為09的數(shù)字。的數(shù)字。兩個(gè)正規(guī)式兩個(gè)正規(guī)式等價(jià)等價(jià) 若兩個(gè)正規(guī)式若兩個(gè)正規(guī)式e1和和e2所表示的所表示的,則說則說e1和和e2等價(jià)等價(jià),寫作寫作e1=e2。 例如：

10、例如： e1= (a b)， e2 = b a 又如：又如： b(ab) = (ba) b(a b) = (a b ) 正規(guī)式的運(yùn)算律正規(guī)式的運(yùn)算律 設(shè)設(shè)r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有： 1。r s=s r“或或”服從交換律服從交換律 2。r (s t)=(r s) t“或或”的可結(jié)合律的可結(jié)合律 3。(rs)t=r(st)“連接連接”的可結(jié)合律的可結(jié)合律 4。r(s t)=rs rt (s t)r=sr tr分配律分配律 5。 r=r, r =r 是是“連接連接”的恒等元素的恒等元素 6。 r r=r r = r rr “或或”的抽取律的抽取律

11、正規(guī)文法到正規(guī)式正規(guī)文法到正規(guī)式 對(duì)對(duì) 上的正規(guī)式上的正規(guī)式r ,存在一個(gè)存在一個(gè)G=(VN,VT,P,S)使得使得L(G)=L(r) ，反之亦然。反之亦然。 VT= ,S VN ，生成正規(guī)產(chǎn)生式生成正規(guī)產(chǎn)生式 Sr (1) 對(duì)形如對(duì)形如 Axy的的正規(guī)產(chǎn)生式：正規(guī)產(chǎn)生式：AxB By B VN(2)對(duì)形如對(duì)形如Ax y的的正規(guī)產(chǎn)生式：正規(guī)產(chǎn)生式： AxB Ay BxB By B VN (3)對(duì)形如對(duì)形如Ax y的的正規(guī)產(chǎn)生式正規(guī)產(chǎn)生式: A x A y 不斷應(yīng)用上述規(guī)則做變換，直到每個(gè)產(chǎn)生式右端只不斷應(yīng)用上述規(guī)則做變換，直到每個(gè)產(chǎn)生式右端只含一個(gè)含一個(gè)VN 例例 r = a(a d) VT=

12、a,d Sa(a d) SaAA(a d) A(a d)B A B(a d)B BGs: SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB B（1）AxB, ByA=xy （2）AxAyA=xy（3）AxyA=xy S=aAa A =aAdA a d =(ad)A(ad) =(ad)(ad) S=a(ad)(ad)a =a(ad)(ad) =a(ad) R=a(ad)Gs:SaAAaAAdASaAaAd4.3有窮自動(dòng)機(jī) 確定的有窮自動(dòng)機(jī)（確定的有窮自動(dòng)機(jī)（DFA） 不確定的有窮自動(dòng)機(jī)（不確定的有窮自動(dòng)機(jī)（NFA） NFA DFA 的轉(zhuǎn)換的轉(zhuǎn)換 DFA的化簡(jiǎn)的化簡(jiǎn)： 一個(gè)

13、確定的有窮自動(dòng)機(jī)（DFA）M是一個(gè)五元組：M=（K，f，S，Z）其中1。 是一個(gè)有窮集，它稱一個(gè)；2。一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱為；3。，是在KK上的映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把kj稱作ki的一個(gè)后繼狀態(tài)；4。 K的一個(gè)；5。 K一個(gè)，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。DFA 例：例：DFA M=（S,U,V,Q, a,b, f, S, Q）其中其中 f 定定義為：義為：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b

14、）=Vf（Q，b）=QDFA 的狀態(tài)圖表示的狀態(tài)圖表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bbDFA 的矩陣表示的矩陣表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QabSUVUQVVUQQQQ字符狀態(tài)0100 一個(gè)輸入符一個(gè)輸入符號(hào)號(hào)串串t，（，（我們將它表示成我們將它表示成Tt1的形的形式，其中式，其中T，t1 *）在）在DFA M上上的的定義為：定義為： 其中其中QK 擴(kuò)充轉(zhuǎn)換函數(shù)擴(kuò)充轉(zhuǎn)換函數(shù)

15、f f，是是K*K上的映射，且：上的映射，且： f（Q， ）= Q*上的符上的符號(hào)號(hào)串串 t 被被 M 接受接受 對(duì)于對(duì)于*中的任何字符串中的任何字符串t，若存在一條從初態(tài)若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條路上所有弧的結(jié)到某一終態(tài)結(jié)的道路，且這條路上所有弧的的標(biāo)記符連接成的字符串等于的標(biāo)記符連接成的字符串等于t，則稱則稱t可為可為DFA M所接受，若所接受，若M的初態(tài)結(jié)同時(shí)又是終態(tài)的初態(tài)結(jié)同時(shí)又是終態(tài)結(jié)，則空字可為結(jié)，則空字可為M所所（）。）。 若若t *，f(S，t)=P，其中其中S為為DFA M的開始的開始狀態(tài)，狀態(tài)，P Z，Z為終態(tài)集。為終態(tài)集。則稱則稱t為為DFA M所所（）

16、。）。例：證明例：證明t=baab被如下的被如下的DFA所接受。所接受。DFA M=（S,U,V,Q, a,b, f, S, Q）其中其中 f 定義為：定義為：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb證明：證明： f（S，baab）=f（f（S，b），），aab）=f（V，aab）=f（f（V，a），），ab）=f（U，ab）=f（f（U，a），），b）=f（Q，b）=QQ屬于終態(tài)。得證。屬于終態(tài)。得證。 DFA M所能接受的符所能接受的符號(hào)號(hào)串的全體記為串的全體記為L(zhǎng)(M) 結(jié)論

17、：結(jié)論： 上一個(gè)字符串集上一個(gè)字符串集V 是正規(guī)的，當(dāng)且僅當(dāng)存是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)在一個(gè) 上的確定有窮自動(dòng)機(jī)上的確定有窮自動(dòng)機(jī)M，使得使得 V=L(M)。不確定的有窮自動(dòng)機(jī)不確定的有窮自動(dòng)機(jī)NFA 定義定義 N= K， ，f，S，Z ，其中其中的有窮非的有窮非空空， 有窮輸入有窮輸入，K * 到到K的子集的的子集的， K始狀始狀， K止?fàn)钪範(fàn)?。例子例子NFA N=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=PSPZ00,1111狀態(tài)圖表示狀態(tài)圖表示表格表示表格表示01SPS,Z0PZ0ZPP1簡(jiǎn)化為01

18、SPS,Z0P.Z0ZPP1NFA N=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=P *上的符上的符號(hào)號(hào)串串t在在NFA N上運(yùn)行上運(yùn)行 *上的符上的符號(hào)號(hào)串串t被被NFA N接受（讀出、識(shí)別）接受（讀出、識(shí)別） 具有具有 轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)NFAf為為 K （ ）到）到K的子集的映像的子集的映像 對(duì)任何一個(gè)具有對(duì)任何一個(gè)具有 轉(zhuǎn)移的不確定的有窮自動(dòng)轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)機(jī)NFA N，一定存在一個(gè)不具有一定存在一個(gè)不具有 轉(zhuǎn)移的轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)不確定的有窮自動(dòng)機(jī)NFA

19、 ，使得，使得L(M)=L(N)。DFA M=（K，f，S，Z）的行為的模擬的行為的模擬程序程序K:=S；c:=getchar;while ceof do K:=f(K,c); c:=getchar; ;if K is in Z then return (yes) else return (no) DFA是是NFA的特例的特例.對(duì)每個(gè)對(duì)每個(gè)NFA M一定存在一定存在一個(gè)一個(gè)DFA ，使得，使得 L(M)=L(M )。 對(duì)每個(gè)對(duì)每個(gè)NFA M存在著與之存在著與之的的DFA M 。與某一與某一NFA等價(jià)的等價(jià)的DFA不唯一。不唯一。定義對(duì)狀態(tài)集合定義對(duì)狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算：的幾個(gè)有關(guān)運(yùn)算： 1

20、 狀態(tài)集合狀態(tài)集合I的的 -閉包，表示為閉包，表示為，定義為一狀態(tài)集，是狀態(tài)集定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)中的任何狀態(tài)S經(jīng)任意條經(jīng)任意條 弧而能到達(dá)的狀態(tài)的集合?；《艿竭_(dá)的狀態(tài)的集合。狀狀態(tài)集合態(tài)集合I的任何狀態(tài)的任何狀態(tài)S都屬于都屬于 -closure(I)。 2 狀態(tài)集合狀態(tài)集合I的的a弧轉(zhuǎn)換，表示為弧轉(zhuǎn)換，表示為定義為狀態(tài)集合定義為狀態(tài)集合J，其中其中J是所有那些可從是所有那些可從I的某一狀態(tài)經(jīng)過一條的某一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀態(tài)的全弧而到達(dá)的狀態(tài)的全體。體。 定義定義Ia = -closure(J)例例I=1, -closure(I)=1,2；I=5, -closure

21、(I)=5,6,2；move(1,2,a)=5,3,4 -closure(5,3,4)=2,3,4,5,6,7,8；12534687aaaNFADFA 假設(shè)假設(shè)NFA N=(K, ,f,K0,Kt)按如下辦法構(gòu)造按如下辦法構(gòu)造一個(gè)一個(gè)DFA M=(S, ,d,S0,St)，使得使得L(M)=L(N)： 1. M的狀態(tài)集的狀態(tài)集S由由K的一些子集組成。用的一些子集組成。用S1 S2. Sj表示表示S的元素，其中的元素，其中S1, S2,. Sj是是K的狀的狀態(tài)。并且約定，狀態(tài)態(tài)。并且約定，狀態(tài)S1, S2,. Sj是按某種規(guī)則是按某種規(guī)則排列的，即對(duì)于子集排列的，即對(duì)于子集S1, S2= S2,

22、 S1,來說，來說，S的狀態(tài)就是的狀態(tài)就是S1 S2； 2. M和和N的輸入字母表是相同的，即是的輸入字母表是相同的，即是 ； 3. 轉(zhuǎn)換函數(shù)是這樣定義的：轉(zhuǎn)換函數(shù)是這樣定義的： D(S1 ,S2 ,. , Sj,a)= R1 , R2 ,. , Rt其中其中 R1 , R2 ,. , Rt = 4. 為為M的開始狀態(tài)；的開始狀態(tài)； 5. St=Si ,Sk ,.,Se，其中，其中Si ,Sk ,. ,Se S且且Si , Sk,. Se Kt構(gòu)造構(gòu)造NFA N的狀態(tài)的狀態(tài)K的子集的算法：的子集的算法： 假定所構(gòu)造的子集族為假定所構(gòu)造的子集族為C，即即C= (T1, T2,. TI),其中其中

23、T1, T2,. TI為狀態(tài)為狀態(tài)K的子集。的子集。 1. 開始，令開始，令 -closure(K0)為為C中唯一成員，并中唯一成員，并且它是未被標(biāo)記的。且它是未被標(biāo)記的。 2.while （C中存在尚未被標(biāo)記的子集中存在尚未被標(biāo)記的子集T）do 標(biāo)標(biāo)記記T； for 每個(gè)輸入字母每個(gè)輸入字母a do U:= -closure(move(T,a)； if U不不在在C中中 then 將將U作為未標(biāo)記的子集加在作為未標(biāo)記的子集加在C中中例例4.8 將下圖的將下圖的NFA N轉(zhuǎn)換成轉(zhuǎn)換成DFA M023456789101bbbaaNFA N023456789101bbbaa -closure(mo

24、ve(Ti,a) -closure(move(Ti,b)T0= -closure(0) =0,1,2,4,71,2,3,4,6,7,8加入為加入為T11,2,4,5,6,7 加入為加入為T2T1= 1,2,3,4,6,7,81,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7,9 加入為加入為T3T2= 1,2,4,5,6,71,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7 已存在已存在T2T3= 1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在已存在T11,2,4,5,7,10 加入為加入為T4T4= 1,2,4,5,7,10 1,2,3,4,6

25、,7,8 已存在已存在T11,2,4,5,6,7 已存在已存在T2 -closure(move(Ti,a) -closure(move(Ti,b)T0= -closure(0) =0,1,2,4,71,2,3,4,6,7,8加入為加入為T11,2,4,5,6,7 加入為加入為T2T1= 1,2,3,4,6,7,81,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7,9 加入為加入為T3T2= 1,2,4,5,6,71,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7 已存在已存在T2T3= 1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在已存在T11,

26、2,4,5,7,10 加入為加入為T4T4= 1,2,4,5,7,10 1,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7 已存在已存在T2初態(tài)終態(tài)b02134abaaaabbbDFA MDFA的最小化（化簡(jiǎn)）的最小化（化簡(jiǎn)） 最小狀態(tài)最小狀態(tài)DFA 沒有多余狀態(tài)沒有多余狀態(tài)(死狀態(tài)死狀態(tài)) ) 沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別） 兩個(gè)狀態(tài)兩個(gè)狀態(tài)s和和t等價(jià)：滿足等價(jià)：滿足 一致性一致性同是終態(tài)或同是非終態(tài)同是終態(tài)或同是非終態(tài) 蔓延性蔓延性從從s出發(fā)讀入某個(gè)出發(fā)讀入某個(gè)a a和從和從 t出發(fā)出發(fā)讀入某個(gè)讀入某個(gè)a到達(dá)的狀態(tài)等價(jià)。到達(dá)的狀態(tài)等價(jià)

27、。消除多余狀態(tài)消除多余狀態(tài)s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7 如圖，狀態(tài)如圖，狀態(tài)0和和4是可區(qū)別的。是可區(qū)別的。 狀態(tài)狀態(tài)2和和3是可區(qū)別的，因?yàn)樽x入是可區(qū)別的，因?yàn)樽x入b后分別到后分別到達(dá)達(dá)2和和4，而，而2和和4不是等價(jià)的。不

28、是等價(jià)的。b02134abaaaabbbDFA M 對(duì)于一個(gè)對(duì)于一個(gè)DFA M =DFA M =（K,f,K,f, k k0 0, , ,k kt t) )，存在存在一個(gè)一個(gè)最小狀態(tài)最小狀態(tài)DFA M = =（K,f,K,f, k k0 0, , ,k kt t) )，,使使L(M)=L(M). 算法的核心：算法的核心：。 結(jié)論結(jié)論 接受接受L的最小狀態(tài)有窮自動(dòng)機(jī)不計(jì)同構(gòu)是唯一的最小狀態(tài)有窮自動(dòng)機(jī)不計(jì)同構(gòu)是唯一的。的。將下圖中的將下圖中的DFA M最小化最小化 1,2,3,4,5,6,7Ia: 6,7,1,4,7,4,4Ib: 3,3,5,6,3,1,21,2,3,4 5,6,71,2 3,4

29、 5 6,71,2 3 4 5 6,71352746aaaaaaabbbbbbb13546aaaaabbbbb 1. 對(duì)于對(duì)于上的上的NFA M，可以構(gòu)造一個(gè)，可以構(gòu)造一個(gè)上上的正規(guī)式的正規(guī)式R,R,使得使得L(R)=L(M)。 2 2. .對(duì)于對(duì)于上的一個(gè)正規(guī)式上的一個(gè)正規(guī)式R，可以構(gòu)造一，可以構(gòu)造一個(gè)個(gè)上的上的NFA M，使得，使得L(M)=L(R)。 1. 對(duì)于對(duì)于上的上的NFA M，可以構(gòu)造一個(gè)，可以構(gòu)造一個(gè)上上的正規(guī)式的正規(guī)式R,R,使得使得L(R)=L(M)。 第一步：在第一步：在M的狀態(tài)轉(zhuǎn)換圖上的狀態(tài)轉(zhuǎn)換圖上，一，一個(gè)為個(gè)為x結(jié)點(diǎn)，一個(gè)為結(jié)點(diǎn)，一個(gè)為y結(jié)點(diǎn)。從結(jié)點(diǎn)。從x結(jié)點(diǎn)用結(jié)點(diǎn)

30、用弧連接弧連接到到M的的，從，從M的的用用弧連接到弧連接到y(tǒng)結(jié)點(diǎn)。形成一個(gè)與結(jié)點(diǎn)。形成一個(gè)與M等價(jià)的等價(jià)的M,M只有只有和和。 第二步：逐步消去第二步：逐步消去M中的所有結(jié)點(diǎn)，直至只中的所有結(jié)點(diǎn)，直至只剩下剩下x和和y。（。（消去規(guī)則見下頁(yè)）消去規(guī)則見下頁(yè)） 最后最后x和和y結(jié)點(diǎn)間的弧上的標(biāo)記則為所求的正規(guī)結(jié)點(diǎn)間的弧上的標(biāo)記則為所求的正規(guī)式式R。123R1R213R1 R213R1R213R1| R2123R1R3R213R1 R2* R3例：例：03124a,baaa,ba,bbb求正規(guī)式求正規(guī)式R03124a,baaa,ba,bbbxy024a|baaa|ba|bbbxy024a|baaa|ba|bbbxy0a|baa(a|b)*bb(a|b)*xy0a|baa(a|b)*bb(a|b)*xy0a|bxyaa(a|b)* |bb(a|b)*xy(a|b)* (aa |bb)(a|b)*(aa |bb)(a|b)*R=(a|b)* (aa |bb)(a|b)* 2 2. .對(duì)于對(duì)于上的一個(gè)正規(guī)式上的一個(gè)正規(guī)式R，可以構(gòu)造一個(gè)，可以構(gòu)造一個(gè)上上的的NFA M，使得，使得L(M)=L(R)。 (1) R=, 任一具有空終態(tài)集的任一具有空終態(tài)集的NFA M (2) R= ，NFA M=(k0, ,f,k,f,k0 0.k.k0 0):): f f（k k