第4章詞法分析編譯原理

第四章詞法分析正規(guī)式NFA正規(guī)文法DFA最小化DFA子集法語言消除多余狀態(tài)合并等價狀態(tài)4.1詞法分析程序的設計詞法分析（lexicalanalysis）功能：逐個讀入源程序字符，輸出“單詞符號”，供語法分析使用。主要任務：讀源程序，產(chǎn)生單詞符號其他任務：濾掉空格，跳過注釋、換行符追蹤換行標志，復制出錯源程序宏展開，……單詞符號一般可分為下列五種：基本字（關(guān)鍵字）：begin,end,if,while標識符：各種名稱，如常量名、變量名、過程名常數(shù)（量）：25,3.1415,TRUE,“ABC”等運算符：如+-*/<<=等界符：逗號，分號，括號等詞法分析程序與語法分析程序的接口方式方式一（常用）：詞法分析程序（掃描整個待編譯的源程序）中間文件輸出語法分析程序輸入：二元式（單詞種類，值）優(yōu)點：（1）整個編譯結(jié)構(gòu)簡潔、清晰、條理化（2）可移植性好=80;eniLLine=80;==;;輸入031字母字母數(shù)字數(shù)字數(shù)字=；4562001字母1字母1字母1字母200=52000=53數(shù)字3數(shù)字3數(shù)字3數(shù)字44；6輸出1字母1字母id,Line=,num,80;,有限控制器分析結(jié)束詞法分析程序與語法分析程序的接口方式方式二（PL/0采用）：語法分析程序詞法分析程序調(diào)用返回一個單詞4.2單詞的描述工具單詞的描述工具和識別工具：正規(guī)文法（正則文法、3型文法）正規(guī)式（正則式）有窮自動機（NFA、DFA）三者之間可以相互轉(zhuǎn)換下一節(jié)正規(guī)文法文法的每個產(chǎn)生式的形式都為：A→aB

或

A→a——右線性A→Ba

或

A→a——左線性其中A，B∈VN，a∈VT*例如：標識符的正規(guī)文法：（若i表示任一字母，d表示任一數(shù)字）

〈標識符〉→i|i〈字母數(shù)字〉

〈字母數(shù)字〉→i|d|i〈字母數(shù)字〉|d〈字母數(shù)字〉無符號整數(shù)的正規(guī)文法：

〈無符號整數(shù)〉→d|d〈無符號整數(shù)〉運算符的正規(guī)文法：

〈運算符〉→+|-|*|/|=|<〈等號〉|>〈等號〉……

〈等號〉→=界符的正規(guī)文法：

〈界符〉→,|;|(|)|……返回正規(guī)式(regularexpression)正規(guī)式：是描述單詞符號串規(guī)則的工具設字母表={a,…,z,A,…,Z,0,…,9}輔助字母表‘={，，，，，，}“”表示“閉包”，即任意有限次的自重復連接“”表示“連接”，有時可以省略“”表示“或”優(yōu)先順序為“()”、“”、“”、“”“”、“”和“”都是左結(jié)合的正規(guī)式為，，，(e)，e1|e2，e1

e2，e*

中的符號。（其中e表示任一正規(guī)式）例1：令={0，1}，上正規(guī)式和相應正規(guī)集的例子有：

正規(guī)式 正規(guī)集

0 {0} 01 {0,1} 01 {01} (01)(01)(中間省略連接號) {00,01,10,11} 0 {,0,00,……任意個0的串}

(01) {,0,1,00,01……所有由0 和1組成的串}

(01)(0011)(01) {上所有含有兩個相繼 的0或兩個相繼的1組成 的串}正規(guī)式舉例兩個正規(guī)式等價若兩個正規(guī)式e1和e2所表示的正規(guī)集相同, 則說e1和e2等價。 記作e1=e2例如：

01=10 1(01)=(10)1 (01)=(01)正規(guī)式的代數(shù)運算設r,s,t為正規(guī)式，則有：rs=sr “或”的交換律r(st)=(rs)t “或”的結(jié)合律(rs)t=r(st) “連接”的可結(jié)合律r(st)=rsrt

(st)r=srtr

分配律r=r r=r

是“連接”的恒等元素程序中的單詞符號都能用正規(guī)式表示：

e=<字母>(<字母>|<數(shù)字>)*返回有窮自動機(FA，F(xiàn)initeAutomata)有窮自動機FA： 是一個識別裝置，用于識別“所有句子”。引入FA的目的： 為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具類型：確定的有窮自動機DFA不確定的有窮自動機NFA返回如果我們能構(gòu)造一個DFAM，使得L(M)是編譯器處理的程序語言中的單詞，那么模擬DFAM的程序?qū)⒖梢杂米髟~法分析器的控制程序。正規(guī)式NFA正規(guī)文法DFA最小化DFA子集法語言消除多余狀態(tài)合并等價狀態(tài)轉(zhuǎn)換正規(guī)文法正規(guī)式①等價轉(zhuǎn)換的規(guī)則②不斷用上述規(guī)則進行變換，直到最后只剩一個開始符號為止。正規(guī)文法正規(guī)式AxBByAxyAxAAyAx*yAxAyAx|y正規(guī)文法正規(guī)式舉例例：正規(guī)文法G[S]: SaA，將正規(guī)文法正規(guī)式。 Sa AaA AdA Aa AdSaASaAaAAdAAaAdSaA|aAaA|dAAa|dSa(A|ε)A(a|d)AAa|dSa(A|ε)A(a|d)*(a|d)Sa((a|d)*(a|d)|ε)Sa(a|d)*正規(guī)式正規(guī)文法①任何正規(guī)式r：定義S為開始符號Sr②轉(zhuǎn)換規(guī)則③不斷用上述規(guī)則進行變換，直到每個產(chǎn)生式的右部只含一個VT為止。正規(guī)式正規(guī)文法AxyAxBByAx*yAxB或AxAAyAyBxBByAx|yAxAy正規(guī)式正規(guī)文法舉例例：正規(guī)式r=0(0|1)*，將正規(guī)式正規(guī)文法。S0

(0|1)*

S0AA(0|1)*

S0AA(0|1)AAεS0AA0A|1AAε

S0AA0AA1AAε

返回4.3有窮自動機（FA）FA(FiniteAutoMata)：

是一個識別裝置，用于識別“所有句子”。引入FA的目的：

為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具類型：確定的有窮自動機

DFA不確定的有窮自動機

NFANFADFA（子集法）DFA的化簡（最小化DFA）下一節(jié)確定的有窮自動機(DFA)1.定義：一個DFA是一個五元組M=(K,,f,S,Z)K：有窮的狀態(tài)集：有窮的字母表（即輸入字符的集合）f：轉(zhuǎn)換函數(shù)K×K上的映像S：初態(tài)（初態(tài)唯一）Z：終態(tài)集（終態(tài)不唯一）例：DFAM=({S,U,V,Q},{a,b},f,S,{Q}) f： f(S,a)=U f(S,b)=V f(U,a)=Q f(U,b)=V f(V,a)=U f(V,b)=Q f(Q,a)=Q f(Q,b)=Q確定的有窮自動機(DFA)2.DFA的“直觀”表示：狀態(tài)圖（狀態(tài)轉(zhuǎn)換圖）每個狀態(tài)用結(jié)點表示若f(Ki,a)=Kj，則初態(tài)用“=>”或“-”標出 終態(tài)用雙圈或“+”標出矩陣列標題：輸出符號（VT） 行標題：狀態(tài)若f(Ki,a)=Kj，則Ki和a的交匯處是Kj初態(tài)用“=>”標出或默認第一行（表格左端） 終態(tài)用“1”標出（表格右端） 非終態(tài)用“0”標出（表格右端）KiKja例：參見上例的DFA，分別用狀態(tài)圖和矩陣表示。字符狀態(tài)0001矩陣表示如下：1.用轉(zhuǎn)換函數(shù)例

設ＤＦＡＭ＝（｛ａ，ｂ｝，｛０，１，２，３｝，０，｛３｝，f）其中f:f（０，ａ）＝１，f（１，ａ）＝3f（２，ａ）＝１，f（３，ａ）＝３f（０，ｂ）＝２，f（１，ｂ）＝２f（２，ｂ）＝３，f（３，ｂ）＝３DFA的三種表示:2.轉(zhuǎn)移矩陣轉(zhuǎn)移矩陣易存儲0132aaaabbbb3狀態(tài)轉(zhuǎn)換圖3.狀態(tài)轉(zhuǎn)換圖確定的有窮自動機(DFA)3.DFA可以接受的句子（符號串）：若t∈*，且存在f(S,t)=…=P，P∈終態(tài)集，則t為該DFA可以接受的句子。即：從初態(tài)S到某終態(tài)結(jié)點P的道路上，所有弧上的標記符連接而成字符串t，t為該DFA可以接受的句子。例：參見上例的DFA狀態(tài)圖，判斷下列句子能否被接受： abba baab abb aa aDFAM能夠接受的句子的全體記為L(M)!!例：證明t=baab被下圖的DFA所接受。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)。得證。bSUVQabba,baaSUVZ111000例：從下圖結(jié)點S出發(fā)，最終到達結(jié)點Z，請判斷01101或1001可否被接受？問題：

設有DFAM=（{0，1，2，3}，{a，b}，f，0，3），其中：f(0,a)=1,f(0,b)=2,f(1,a)=3,f(1,b)=2,f(2,a)=1,f(2,b)=3,f(3,a)=3,f(3,b)=3

（1）畫出狀態(tài)圖和矩陣（2）abb是否為M所接受？例：DFA，接受

0和1的個數(shù)都是偶數(shù)的字符串312011110000開始偶0偶1奇0奇1奇0偶1偶0奇1確定的有窮自動機(DFA)4.DFA的確定性：f:K×K

是一個單值函數(shù)即對任何狀態(tài)K，當輸入字符a時，下一狀態(tài)唯一。上例的有窮狀態(tài)機就是DFADFAM=（K，Σ，f，S，Z）的行為模擬程序：K:=S；c:=getchar;while(c<>eof){ K:=f(K,c); c:=getchar;}if(KinZ){ return(‘yes’); }else{ return(‘no’); }DFA的行為模擬程序返回例：識別={0,1}上能被能5整除的二進制數(shù)0123開始40DFA應用的一個實例0123開始410DFA應用的一個實例（續(xù)）0123開始4100DFA應用的一個實例（續(xù)）0123開始41001DFA應用的一個實例（續(xù)）0123開始410010DFA應用的一個實例（續(xù)）0123開始4100101DFA應用的一個實例（續(xù)）0123開始41001010DFA應用的一個實例（續(xù)）0123開始410010101DFA應用的一個實例（續(xù)）0123開始4100101010DFA應用的一個實例（續(xù)）0123開始41001010101DFA應用的一個實例（續(xù)）0123開始4100101010110102=10101112=710DFA應用的一個實例（續(xù)）不確定的有窮自動機(NFA)1.定義：一個NFA是一個五元組M=(K,,f,S,Z)K：有窮的狀態(tài)集：有窮的字母表（即輸入字符的集合）f：轉(zhuǎn)換函數(shù)K×*K+

上的映像 （K+表示K的子集）S：初態(tài)集（初態(tài)不唯一）Z：終態(tài)集例：NFAM’=({0,1,2,3,4},{a,b},f,{0},{2,4})

f： f(0,a)={0,3} f(0,b)={0,1} f(1,b)={2} f(2,a)={2} f(2,b)={2} f(3,a)={4} f(4,a)={4} f(4,b)={4}2.NFA的“直觀”表示：狀態(tài)圖（狀態(tài)轉(zhuǎn)換圖）每個狀態(tài)用結(jié)點表示若f(Ki,a)=Kj，則初態(tài)用“=>”或“-”標出 終態(tài)用雙圈或“+”標出矩陣列標題：輸出符號（VT） 行標題：狀態(tài)若f(Ki,a)=Kj，則Ki和a的交匯處是Kj初態(tài)用“=>”標出或默認第一行（表格左端） 終態(tài)用“1”標出（表格右端） 非終態(tài)用“0”標出（表格右端）KiKja舉例：參見上例的NFA，分別用狀態(tài)圖和矩陣表示。不確定的有窮自動機(NFA)例子NFAM=（{S，P，Z}，{0，1}，f，{S}，{Z}）其中：

f（S，0）={P}

f（Z，0）={P}

f（P，1）={Z}

f（Z，1）={P}

f（S，1）={S，Z}

SPZ00,11113.NFA可以接受的句子（符號串）：(同DFA)若t∈*，且存在f(S,t)=…=P，P∈終態(tài)集，則t為該NFA可以接受的句子。例：參見上例的NFA狀態(tài)圖，判斷下列句子能否被接受： aaa baab abb a aba babNFAM’能夠接受的句子的全體記為L(M’)對于每個NFAM’存在一個DFAM，使得L(M’)=L(M)

!!不確定的有窮自動機(NFA)

可以被NFAM’能夠接受的兩種情況：

M’的某結(jié)點既是初態(tài)，又是終態(tài)存在一條從初態(tài)到終態(tài)的道路4.NFA的不確定性：對于狀態(tài)K，當輸入字符a時，下一狀態(tài)不一定唯一。5.NFA的確定化：

對每個NFAM’一定存在一個DFAM，使得L(M')=L(M) 即：對每個NFAM存在著與之等價的DFAM'。 注：與某一NFA等價的DFA不唯一。證明思想：用M的一個狀態(tài)對應M的一個狀態(tài)集合，用這種方法，能從一個NFAM構(gòu)造一個DFAM，稱作子集構(gòu)造法。不確定的有窮自動機(NFA)返回NFADFA（子集法）（一）基本運算：狀態(tài)集合I的閉包：表示為-closure(I) 狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條弧而能到達的狀態(tài)的集合。注：狀態(tài)集I的任何狀態(tài)S都屬于-closure(I)狀態(tài)集合I的a弧轉(zhuǎn)換：表示為move(I,a) 定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達的狀態(tài)的全體。舉例：參見P58圖4.4，求：-closure(0) move(0,a) move(0,b)-closure(1) move(2,a) move(2,b)… move({0,1,2,4,7},a)-closure({1,3}) move({0,1,2,4,7},b)注：1.狀態(tài)集合I的ε-閉包，表示為ε-closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條ε弧而能到達的狀態(tài)的集合。狀態(tài)集合I的任何狀態(tài)S都屬于ε-closure(I)。注：2.狀態(tài)集合I的a弧轉(zhuǎn)換，表示為move(I,a)定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達的狀態(tài)的全體。I={1},-closure(I)={1,2}；I={5},-closure(I)={5,6,2}；move({1,2},a)={5,6,2,4,7,3,8}move({5,6,2},a)={3,8}；12534687aaaNFADFA（子集法）（二）轉(zhuǎn)換的主要思想：DFA的一個狀態(tài)可能對應NFA的一個或一組狀態(tài)DFA同樣記錄在NFA上讀入某個VT后可能到達的所有狀態(tài)01426578910bbb例從具體例子的討論,提煉出從NFA構(gòu)造DFA的算法。3aa012470,1,2,4,73861243,8,6,1,2,4,7a75614275,6,1,2,4,7b（三）子集法

NFAN=(K,,f,K0,Kt)構(gòu)造DFAM=(S,,d,S0,St)，使得L(M)=L(N)

：M的狀態(tài)集S由K的一些子集組成M和N的輸入字母表相同轉(zhuǎn)換函數(shù)d是這樣定義的： d([S1,...,Sj],a)=-closure(move([S1,...,Sj],a))S0=-closure(K0)為M的開始狀態(tài)St={[Si,Sk

,...,Se]，其中[Si,Sk

,...,Se]S

且{Si,Sk,,...

Se}Kt}NFADFA（子集法）構(gòu)造NFAN的狀態(tài)K的子集的算法：假定所構(gòu)造的子集族為C=(T1,T2,,...

Ti)，其中T1,T2,,...

Ti為狀態(tài)K的子集。1）開始，令-closure(K0)為C中唯一成員，并且它是未被標記的。2）While(C中存在尚未被標記的子集T)do{ 標記T； for(每個輸入字母a)do { U:=-closure(move(T,a))； if（U不在C中）then { 將U作為未標記的子集加在C中；} }}舉例：參見P58圖4.4構(gòu)造NFA對應的子集NFADFA（子集法）-closure(move(Ti,a))-closure(move(Ti,b))T0=-closure(0)

={0,1,2,4,7}T1={1,2,3,4,6,7,8}T2={1,2,4,5,6,7}T1={1,2,3,4,6,7,8}T1={1,2,3,4,6,7,8}T3={1,2,4,5,6,7,9}T2={1,2,4,5,6,7}T1={1,2,3,4,6,7,8}T2={1,2,4,5,6,7}T3={1,2,4,5,6,7,9}T1={1,2,3,4,6,7,8}T4={1,2,4,5,7,10}T4={1,2,4,5,7,10}T1={1,2,3,4,6,7,8}T2={1,2,4,5,6,7}b02134abaaaabbb初態(tài)終態(tài)DFAM：課后習題：2，3，4(a)返回01436578910abbb2a3,8,6,1,2,4,70,1,2,4,725,6,1,2,4,7325,9,6,1,2,4,742325,10,6,1,2,4,752319開始0abab6782345輸入符號ab狀態(tài)

NFA到DFA的轉(zhuǎn)換的實例19開始0abab6782345輸入符號abA狀態(tài)

A={0,1,2,4,7}

NFA到DFA的轉(zhuǎn)換的實例19開始0abab6782345輸入符號abAB狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}

NFA到DFA的轉(zhuǎn)換的實例19開始0abab6782345輸入符號abABB狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}NFA到DFA的轉(zhuǎn)換的實例19開始0abab6782345輸入符號abABCB狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}

NFA到DFA的轉(zhuǎn)換的實例19開始0abab6782345輸入符號abABCBC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}NFA到DFA的轉(zhuǎn)換的實例19開始0abab6782345輸入符號abABCBBC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}NFA到DFA的轉(zhuǎn)換的實例19開始0abab6782345輸入符號abABCBBDC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

NFA到DFA的轉(zhuǎn)換的實例19開始0abab6782345輸入符號abABCBBDCD狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

NFA到DFA的轉(zhuǎn)換的實例19開始0abab6782345輸入符號abABCBBDCBCD狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

NFA到DFA的轉(zhuǎn)換的實例19開始0abab6782345輸入符號abABCBBDCBCDBC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

NFA到DFA的轉(zhuǎn)換的實例BD開始aAabbabCba19開始0abab6782345輸入符號abABCBBDCBCDBC狀態(tài)NFA到DFA的轉(zhuǎn)換的實例NFA到DFA的轉(zhuǎn)換的實例二4f35621iaaaabbbbNFA到DFA的轉(zhuǎn)換的實例二（續(xù)）CDBAEFSbaaaaabbbbb4f35621iaaaabbbb最小化DFA沒有多余狀態(tài)(死狀態(tài))沒有兩個狀態(tài)是互相等價DFA的化簡（最小化DFA）（1）多余狀態(tài)：

從開始狀態(tài)出發(fā)，任何輸入串也不能到達的狀態(tài) 處理：消除多余狀態(tài)（2）兩個狀態(tài)s和t等價：滿足一致性——同是終態(tài)或同是非終態(tài)蔓延性——從s出發(fā)讀入某個aa和從t出發(fā)讀入某個a到達的狀態(tài)等價。處理：合并等價狀態(tài)（使用“分割法”）BD開始aAabbaa,bCbaEb多余狀態(tài)例子BD開始aAabbabCba左圖無死狀態(tài)，右圖加入死狀態(tài)E。BD開始aAabbabCba等價狀態(tài)例子A和Ｃ是等價的狀態(tài)A和Ｂ是不等價的狀態(tài)CDBAEFSbaaaaabbbbbabaC和D同是終態(tài)，讀入a到達C和F，C和F同是終態(tài)，C和F讀入a都到達C，讀入b都到達E，C和D等價。DFA的最小化DFA的最小化的唯一性對于一個DFAM=（K,∑,f,k0,,kt)，存在一個最小狀態(tài)DFAM’=（K’,∑,f’,

k0’,,kt’)，使L(M’)=L(M).結(jié)論接受L的最小狀態(tài)有窮自動機不計同構(gòu)是唯一的。即，接受L的最小狀態(tài)有窮自動機不計拓撲結(jié)構(gòu)相同而形式不同的差別，則這種最小狀態(tài)有窮自動機是唯一的。DFA的最小化算法的過程:把一個DFA的狀態(tài)分成一些不相交的子集，使得同一子集中的任何兩個狀態(tài)都是等價的.DFA的最小化DFA的最小化算法:

DFAM=（K,∑,f,k0,,kt),最小狀態(tài)DFAM’

1.構(gòu)造狀態(tài)的一初始劃分:終態(tài)kt

和非終態(tài)K-kt兩組(group)2.對∏構(gòu)造新劃分∏new

3.如∏new=∏,則令∏final=∏并繼續(xù)步驟4，否則∏:=∏new重復2.

4.合并等價狀態(tài)

有窮自動機DFA的最小化算法的核心：把一個DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的，最后每個子集中選出一個代表，同時消除其他等價狀態(tài)。DFA的最小化例子CDBAEFSbaaaaabbbbbaba１．將Ｍ的狀態(tài)分為兩個子集一個由終態(tài)｛Ｃ，Ｄ，Ｅ，Ｆ｝組成，一個由非終態(tài)｛Ｓ，Ａ，Ｂ｝組成：２．考察｛Ｓ，Ａ，Ｂ｝是否可分．

S輸入a到達A，A輸入a到達C，B輸入a到達A

因為Ａ屬｛Ｓ，Ａ，Ｂ｝而Ｃ屬｛Ｃ，Ｄ，Ｅ，Ｆ｝，S和B是兩個等價狀態(tài)，而和A是不等價狀態(tài)，所以可分為｛Ａ｝和｛Ｓ，Ｂ｝兩個集合．３．考察｛Ｓ，Ｂ｝是否可再分：

S輸入b到達B，B輸入b到達D

因為Ｂ屬｛Ｓ，Ｂ｝，Ｄ屬｛Ｃ，Ｄ，Ｅ，Ｆ｝所以，可再分為｛Ｓ｝和｛Ｂ｝兩個集合．４．考察｛Ｃ，Ｄ，Ｅ，Ｆ｝是否可再分：因為Ｃ，Ｄ，Ｅ，Ｆ輸入a和b到達的狀態(tài)都屬于｛Ｃ，Ｄ，Ｅ，Ｆ｝所以：５．｛Ｃ，Ｄ，Ｅ，Ｆ｝以｛Ｄ｝來代替則最小化的ＤＦＡ如下圖：DFA的最小化例子aaBD開始aAabbabCba12開始a0abbabDFA的最小化算法實例DFA的最小化劃分{A,C,B},{D}move({A,C},a}={B}move({A,C},b}={C}合并補充剩余弧解：

步驟一：消除多余狀態(tài) 步驟二：使用分割法，合并等價狀態(tài)。b02134abaaaabbbDFAM舉例：求最小化DFADFA的化簡（最小化DFA）

1,2,3,4,5,6,7Ia：6,7,1,4,7,4,4Ib：3,3,5,6,3,1,2{1,2,3,4}{5,6,7}{1,2}{3,4}{5}{6,7}{1,2}{3}{4}{5}{6,7}1352746aaaaaaabbbbbbb13546aaaaabbbbb舉例：求最小化DFA返回P70例2課后題：4(b)94.4正規(guī)式和有窮自動機的等價性正規(guī)式NFA正規(guī)文法DFA最小化DFA子集法語言消除多余狀態(tài)合并等價狀態(tài)轉(zhuǎn)換對于∑上的

NFAM，可以構(gòu)造一個∑上的正規(guī)式R，使得

L(R)=L(M)。對于∑上的正規(guī)式R，可以構(gòu)造一個∑上的

NFAM，使得

L(M)=L(R)。在FAM的狀態(tài)圖上加兩個狀態(tài)結(jié)點x和y。從x結(jié)點出發(fā)，用ε弧連接x結(jié)點到所有初態(tài)結(jié)點從M的所有終態(tài)結(jié)點用ε弧連接到y(tǒng)結(jié)點 此時，

x為初態(tài)和y為終態(tài)。利用消結(jié)規(guī)則，逐步消去M’中的所有結(jié)點，直至只剩下x和y。最后x和y結(jié)點間的弧上的標記則為所求的正規(guī)式R。FA正規(guī)式123R1R213R1R213R1R213R1|

R2123R1R3R213R1R2*

R3舉例：求FA所對應的正規(guī)式R03124a,baaa,ba,bbb解：03124a,baaa,ba,bbbxyεεεFA正規(guī)式024a|baaa|ba|bbbxyεεε0a|baa(a|b)*bb(a|b)*xyε則：R=(a|b)*(aa|bb)(a|b)*0a|baa(a|b)*bb(a|b)*xyε0a|bxyε(aa|bb)(a|b)*xy(a|b)*(aa|bb)(a|b)*課后習題：9將正規(guī)式分解成一系列子表達式。對于每個子表達式，用如下規(guī)則構(gòu)造FA：正規(guī)式FA正規(guī)式FAФεRR1R2

1212ε12R正規(guī)式FAR1|

R2R*13R1R2123εεR注意：由于分解的方法和順序不同，構(gòu)造的NFA可能不同，但最小化的DFA一定相同??！13R1R22從正規(guī)式到有限自動機首先構(gòu)造識別和字母表中一個符號的NFAi開始識別正規(guī)式的NFAafif開始識別正規(guī)式a的NFA構(gòu)造識別主算符為選擇的正規(guī)式的NFA

fi開始識別正規(guī)式s|t的NFAN(s)N(t)從正規(guī)式到有限自動機iN(s)f開始識別正規(guī)式st的NFAN(t)構(gòu)造識別主算符為連接的正規(guī)式的NFA

從正規(guī)式到有限自動機構(gòu)造識別主算符為閉包的正規(guī)式的NFA

N(s)f開始識別正規(guī)式s*的NFAi從正規(guī)式到有限自動機對于加括號的正規(guī)式(s)，使用N(s)本身作為它的NFA。19開始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解從正規(guī)式到有限自動機19開始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解從正規(guī)式到有限自動機19開始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解從正規(guī)式到有限自動機19開始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解從正規(guī)式到有限自動機19開始0abab6782345r9r7r8r4r