教案編譯原理

第三章詞法分析

詞法分析是編譯的第一個階段，在單詞的級別上分析和翻譯源程序。理論基礎(chǔ)：有限自動機理論有限自動機理論與正規(guī)文法、正規(guī)式之間在描述語言方面一一對應(yīng)的關(guān)系3.1詞法分析程序的功能3.2單詞符號及輸出單詞的形式3.3語言單詞符號的兩種定義方式3.4正規(guī)式與有窮自動機3.5正規(guī)文法與有窮自動機3.6詞法分析程序的編寫方法詞法分析程序（詞法分析器或掃描器）任務(wù)：從左至右掃描，根據(jù)詞法規(guī)則識別單詞,并轉(zhuǎn)化為機器易于使用的內(nèi)碼形式存在形式：（1）語法分析程序的子程序；（2）組織成一遍掃描第三章詞法分析

第一節(jié)詞法分析程序的功能第三章詞法分析

第二節(jié)單詞符號及輸出單詞的形式一、程序語言單詞的分類：

1．關(guān)鍵字(保留字或基本字)：begin,end2．標識符：用來表示各種名字

3．常數(shù)：如整型常數(shù)256，實型常數(shù)3.14，布爾型常數(shù)true,‘a(chǎn)bc’4．運算符：如，＋、－、*、/等等

5．分界符：如逗號，分號，冒號，括號等第三章詞法分析

第二節(jié)單詞符號及輸出單詞的形式二、詞法分析程序輸出單詞的形式詞法分析器的輸出：（單詞種別，單詞自身的值）1、單詞種別含義：單詞的種類，提供給語法分析程序使用；設(shè)置目的：最大限度地把單詞區(qū)別開來分類法：一類一種/一字一種2、單詞自身的值單詞自身的值提供給語義分析程序使用；描述方法：對于一類一種/一字一種區(qū)別對待。第三章詞法分析

第二節(jié)單詞符號及輸出單詞的形式二、詞法分析程序輸出單詞的形式設(shè)計原則：單詞種別：具體的分類設(shè)計以方便語法分析程序使用為原則。關(guān)鍵字可分成一類，也可以一個關(guān)鍵字分成一類。常數(shù)可統(tǒng)歸一類，也可按類型（整型、實型、布爾型等），每個類型的常數(shù)劃分成一類。單詞自身的值：所提供的內(nèi)容由語法分析和語義分析的任務(wù)劃分決定。第三章詞法分析

第三節(jié)語言單詞符號的兩種定義方式正規(guī)式：簡潔清晰l(l|d)*正規(guī)文法：易于識別S->l|Sl|Sd第三章詞法分析

第三節(jié)語言單詞符號的兩種定義方式3.3.1正規(guī)式與正規(guī)集正規(guī)式：(Def1)設(shè)A是非空的有限字母表，A={ai|i=1,2,……n},則（1），和ai(i=1,2,……n)都是正規(guī)式。（2）若、是正規(guī)式，則|、?、*、*也是正規(guī)式。（3）正規(guī)式只能通過有限次使用1，2規(guī)則獲得。第三章詞法分析

第三節(jié)語言單詞符號的兩種定義方式3.3.1正規(guī)式與正規(guī)集正規(guī)式：(Def2)

設(shè)有字母表Σ={a1，a2

，…，an}，在Σ上的正規(guī)式和它所表示的正規(guī)集可用如下規(guī)則來定義：（1）Φ是Σ上的正規(guī)式，它所表示的正規(guī)集是Φ，即空集{}。（2）是Σ上的正規(guī)式，它所表示的正規(guī)集僅含一空符號串，即{}。（3）ai是Σ上的一個正規(guī)式，它所表示的正規(guī)集是單個符號是所組成，即{ai}。第三章詞法分析

第三節(jié)語言單詞符號的兩種定義方式3.3.1正規(guī)式與正規(guī)集正規(guī)式：(Def2)（4）如果e1和e2是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，則：①

e1||e2是Σ上的正規(guī)式，它所表示的正規(guī)集為L(e1|e2)=L(e1)L(e2)②e1e2是Σ上的正規(guī)式，它所表示的正規(guī)集為L(e1e2)=L(e1)L(e2)③

（e1

）*是Σ上的正規(guī)式，它所表示的正規(guī)集為L((e1)*)=(L(e1))*第三章詞法分析

第三節(jié)語言單詞符號的兩種定義方式3.3.1正規(guī)式與正規(guī)集正規(guī)集由正規(guī)文法或正規(guī)式產(chǎn)生的語言注：正規(guī)集是集合，可有窮也可無窮?？赏ㄟ^正規(guī)式來形式化表示。例:(a|b)*(aa|bb)*(a|b)*的正規(guī)集為

{a,b}*{aa,bb}*{a,b}*第三章詞法分析

第三節(jié)語言單詞符號的兩種定義方式3.3.1正規(guī)式與正規(guī)集注：1)利用正規(guī)集相同，可用來證明相應(yīng)正規(guī)式等價。2)“|”讀作為“或”，也可寫作為“+”或“，”；“?”讀作連接。例：求正規(guī)集L()={aibjck|i,j,k>=1}的正規(guī)式=a+b+c+第三章詞法分析

第三節(jié)語言單詞符號的兩種定義方式3.3.1正規(guī)式與正規(guī)集正規(guī)式性質(zhì)：定理1若、、是正規(guī)式則下述等價式成立1.+=+2.+(+)=(+)+

()=()3.(+)=+(+)=

+4.==5.(*)*=*6.*=＋＋(＋|)

＋

＝*

=*7.(+)*=(*+*)*=(**)*(|)*=(*|*)*=(**)*第三章詞法分析

第三節(jié)語言單詞符號的兩種定義方式3.3.1正規(guī)式與正規(guī)集正規(guī)式性質(zhì)：定理2若、、是字母表A上的正規(guī)式，且L()，則=|當且僅當=*=|當且僅當=*2015.3.11第三章詞法分析

第三節(jié)語言單詞符號的兩種定義方式3.3.2正規(guī)文法與正規(guī)式1、正規(guī)文法到正規(guī)式的轉(zhuǎn)換步驟：（1）聯(lián)立方程組（2）按照定理2，將正規(guī)文法轉(zhuǎn)換成正規(guī)式第三章詞法分析

第三節(jié)語言單詞符號的兩種定義方式1、正規(guī)文法到正規(guī)式的轉(zhuǎn)換例：已知正規(guī)文法G1的產(chǎn)生式，求出它所定義的正規(guī)式。產(chǎn)生式為：SaS|aBBbB|bAAcA|c第三章詞法分析

第三節(jié)語言單詞符號的兩種定義方式1）.由產(chǎn)生式寫出對應(yīng)的聯(lián)立方程組

S＝aS|aB……（1）

B＝bB|bA……（2）

A＝cA|c……（3）2）.根據(jù)定理2，由（1）得：S=a*aB=a+B……（4）同理，由（2）得：B=b+A……（5）同理，由（3）得：A=c*c=c+……（6）將（6）代入（5）得：B=b+c+……（7）將（7）代入（4）得：S=a+b+c+……（8）3）.故：正規(guī)式為S=a+b+c+第三章詞法分析

第三節(jié)語言單詞符號的兩種定義方式2、正規(guī)式到正規(guī)文法的轉(zhuǎn)換字母表上Σ的正規(guī)式到正規(guī)文法G=（VN，VT，P，S）的轉(zhuǎn)換方法如下：（1）令VT=Σ

；（2）對任意正規(guī)式R選擇一個非終結(jié)符Z生成規(guī)則Z->R，并令S=Z；（3）若a和b都是正規(guī)式，對形如A->ab的規(guī)則轉(zhuǎn)換成A-aB和B->b兩規(guī)則，其中B是新增的非終結(jié)符；（4）在已轉(zhuǎn)換的文法中，將形如A->a*b的規(guī)則進一步轉(zhuǎn)換成A->aA|b；（5）不斷利用規(guī)則（3）和（4）進行變換，直到每條規(guī)則最多含有一個終結(jié)符為止。第三章詞法分析

第三節(jié)語言單詞符號的兩種定義方式2、正規(guī)式到正規(guī)文法的轉(zhuǎn)換例：將R=(a|b)(aa)*(a|b)第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機*有限自動機：為什么研究有窮自動機？有限自動機是一種識別裝置，它能準確地識別正規(guī)集。它為詞法分析程序的構(gòu)造提供了方法和工具。有限自動機的基本屬性與功能：有限自動機是具有離散輸入輸出系統(tǒng)的數(shù)學(xué)模型。它具有有限數(shù)目的內(nèi)部狀態(tài)，系統(tǒng)可以根據(jù)當前所處的狀態(tài)和面臨的輸入字符決定系統(tǒng)的后繼行為。其當前狀態(tài)概括了過去輸入處理的信息。第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機*有窮自動機模型狀態(tài)：初始狀態(tài)、中間狀態(tài)和終止狀態(tài)。

在初始狀態(tài)下，讀頭指向輸入帶的最左單元，準備讀入第一個字符，每讀入一個字符，從當前狀態(tài)進入下一狀態(tài)；當讀頭讀入所有字符后，狀態(tài)進入終態(tài)，則輸入帶上的輸入串被接受，否則，輸入串有錯。注：1)終止狀態(tài)可以有若干個，而初始狀態(tài)一般只有一個。

2)可用狀態(tài)轉(zhuǎn)換圖表示狀態(tài)變換，狀態(tài)用結(jié)點表示，讀入符號用邊表示。

abcde……有限狀態(tài)控制器輸入帶讀頭狀態(tài)變換第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機例：正規(guī)式<標識符>＝<字母>(<字母><數(shù)字>)*的狀態(tài)轉(zhuǎn)換圖形式如下：標程序中識符xtemp的識別匹配過程為：

12222212字母字母數(shù)字xtemp第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機3.4.1確定有窮自動機DFA（DeterministicFiniteAutomation）(1)定義：確定有限自動機是一個五元組M=(Q,,f,S,Z）其中：Q：有限狀態(tài)集 ：有限字母表f：QQ上的單值映射，f(qi,a)=qjS：唯一的初態(tài)，S

∈QZ：終止狀態(tài)集，ZQ注：這里確定的含義，就是狀態(tài)轉(zhuǎn)換關(guān)系f是一個函數(shù)，即對于給定的當前狀態(tài)qi和當前讀入的符號a，有唯一確定的下一狀態(tài)qj第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機3.4.1確定有窮自動機(2)狀態(tài)轉(zhuǎn)換關(guān)系表示：狀態(tài)轉(zhuǎn)換矩陣：DFA的映射關(guān)系由一個矩陣來表示。狀態(tài)轉(zhuǎn)換圖：注：1）用矩陣表示轉(zhuǎn)換便于計算機處理，但不直觀，而用狀態(tài)轉(zhuǎn)換圖表示比較直觀。2）在整個狀態(tài)轉(zhuǎn)換圖中只有一個初始狀態(tài)結(jié)點，用“”射入的結(jié)點表示初始狀態(tài)?？捎腥舾山K止狀態(tài)(也可能沒有)，用雙園圈表示。若初始狀態(tài)結(jié)點同時又是終止狀態(tài)結(jié)點，則表示空串可為相應(yīng)DFA識別。例：DFAM=({0,1,2,3},{a,b},f,0,{3})f:f(0,a)=1f(0,b)=2f(1,a)＝3f(1,b)＝2f(2,a)=1f(2,b)=3f(3,a)＝3f(3,b)＝3狀態(tài)轉(zhuǎn)換矩陣

輸入狀態(tài)ab0121322133331aa032bbabab第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機（3）DFA對字符串的識別對Σ*上的任何符號串，若存在一條從初態(tài)結(jié)到終結(jié)態(tài)的道路，而且在這條路上所有弧的標記連接成的符號串等于，則稱為DFAM所識別（接受）。DFAM所示別的符號串的全體記為L(M)，稱為DFAM所識別的語言。第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機3.4.2非確定有窮自動機NFA(Non-deterministicFA)(1)定義：非確定有窮自動機是一個五元組

M=（Q,,f,S,Z），其中：Q：有限狀態(tài)集 ：有限字母表f：Q2Q(Q的子集)上的映射S：非空的初態(tài)集，S是Q的真子集Z：終止狀態(tài)集，Z是Q的子集，可為空集注：*非確定主要是指后繼狀態(tài)可有多個*DFA是NFA的特例3.4.1確定有窮自動機DFA（DeterministicFiniteAutomation）注：*NFA映射的含義可表達成：f(Q’0,a)={Q0,Q1,Q2,…..,Qk}，其中Qi∈Q*多值映射還可以擴展到對輸入字符串，即f（S,ω）=P，P∈2s。如：設(shè)ω=ab,根據(jù)對讀入字符的映射關(guān)系，有f(S,ab)=f(f(S,a),b)=f({S1,S2,…,Sn},b)=f(S1,b)∪f(S2,b)∪…∪f(Sn,b)第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機例設(shè)NFAM＝({q0,q1},{0,1},f,{q0},{q1})f映射為

字符狀態(tài)01q0q0

q1q1

q0，q1q0q0q111000第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機3.4.2非確定有窮自動機NFA(2)兩自動機等價：任何兩個有限自動機M和M’，若它們識別的語言相同(L(M)=L(M’))，則稱M和M’等價注：存在判定任何兩個有限自動機等價性的算法第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機3.4.3由正規(guī)表達式R構(gòu)造NFA關(guān)系定理定理：上的NFAM所能識別的語言L(M)可以用上的正規(guī)式來表示。即：對上的NFAM，可構(gòu)造一個正規(guī)式，使得L()=L(M)定理：上任何正規(guī)式，存在DFAM使得L(M)=L()。即：由正規(guī)式可以構(gòu)造一個DFAM，使得L(M)＝L()第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機3.4.3由正規(guī)表達式R構(gòu)造NFA輸入：字母表上的正規(guī)式R輸出：識別（接受）語言L(R)的NFAM1)由正規(guī)式

構(gòu)造一個如下僅有兩個結(jié)點x,y的狀態(tài)圖。2)按所引入的3條正規(guī)式分裂規(guī)則分裂；對于R=，，a的情況，按書P40-41圖3.7，3.8，3.9所示處理。3)重復(fù)步驟2直到每個弧上的標記是上的一個字符或為止。注：將所得的NFAM(因為包含弧)進行確定化就得到DFA。xy第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機3.4.3由正規(guī)表達式R構(gòu)造NFA正規(guī)式分裂規(guī)則：12|1221121‘12*

211‘xy(a|b)*(aa|bb)(a|b)*例：根據(jù)正規(guī)式(a|b)*(aa|bb)(a|b)*,構(gòu)造DFAM，使之等價1y(a|b)*(a|b)*

2x(aa|bb)1y

2xaa5

bba|b

6

a|b1y

2xa5

ba

6

abb34ab第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機3.4.4NFA確定化為DFA的方法(1)定理對于每個NFAM，存在一個DFAM’，使得L(M)=L(M’)。即，設(shè)L是一NFA接受的正規(guī)集，則存在一個DFA接受L第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機3.4.4NFA確定化為DFA的方法(2)問題已知-輸入：一個NFAN求-輸出：一個接受相同語言的DFAM求解基本思想：把NFA狀態(tài)集的一個子集轉(zhuǎn)化為DFA中的一個狀態(tài)；通過DFA的狀態(tài)記錄在NFA輸入符號之后可能到達的所有狀態(tài)的集合。3.4.4NFA確定化為DFA的方法

(3)算法①:算法：由NFAM=(Q,,f,S,Z)構(gòu)造一個等價的DFAM’=(Q’,,f’,S’,Z’）1.取S’=S，2.若狀態(tài)集Q’中有狀態(tài)S’i={s0,s1,……sj},sk∈Q,0kj;而且M機中有f({s0,s1,……sj},a)=f(s0,a)∪f(s1,a)∪……∪f(sj,a)= ={s0,s1,……st}，令其為St’

，若St’不在Q’中，則將St’加入Q’。

算法：

3.重復(fù)步驟2，直到Q’中無新狀態(tài)加入為止。

4.取終態(tài)Z’={I|I∈Q’,且I∩Z<>}

注：1)上述過程可在有限步內(nèi)完成，因為M機狀態(tài)的冪集是有限的；2)上述過程也可用表格法來描述，其中列是字符集中的字符；行是Q’中的各狀態(tài)，開始僅包含S’狀態(tài)，隨著算法的執(zhí)行，Q’的狀態(tài)逐漸增多直止不再增多為止；表格元素就是f’映射函數(shù)。3.4.4NFA確定化為DFA的方法

(3)算法①:

注：3)NFA確定化的實質(zhì)是以原有狀態(tài)集上的覆蓋片(COVER)作為DFA上的一個狀態(tài)，將原狀態(tài)間的轉(zhuǎn)換改為覆蓋片間的轉(zhuǎn)換，從而將不確定問題確定化。4)通常，經(jīng)確定化后，狀態(tài)數(shù)增加，而且可能出現(xiàn)一些等價狀態(tài)，這時需要化簡。3.4.4NFA確定化為DFA的方法

(3)算法①:3.4.4NFA確定化為DFA的方法

(4)算法②:通過-closure()

問題回顧：已知-輸入：一個NFAN求-輸出：一個接受相同語言的DFAM預(yù)備知識：-closure設(shè)I是NFAN的一個狀態(tài)子集，-closure(I)的定義為：（1）若s∈I，則s∈-closure(I)。（2）若s∈I，則從s出發(fā)經(jīng)過任意條弧而能到達的任何狀態(tài)s’,都屬于-closure(I)。算法：1.置DFAM中的狀態(tài)集Q’和Z’為；2.給出M的初態(tài)S’=-closure({S})，并把S’置為未標記狀態(tài)后加入到Q’中；3.如果Q’中存在未標記的狀態(tài)T={t0,t1,……tj}，

ti∈Q，則進行如下變換：(1)對于每個a∈Σ，置:J=f({t0,t1,……,tj},a)=f(t0,a)f(t1,a)…f(ti,a)U=-closure(J)如果U不在Q’中，則將U置為無標記的狀態(tài)添加到Q’中，且把狀態(tài)轉(zhuǎn)移f’(T,a)=U添加到M中，如果U中至少含有一個元素是N的終態(tài)，則把U置為M的終態(tài)，即把U添加到Z’中；3.4.4NFA確定化為DFA的方法

(4)算法②:通過-closure()

第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機(2)對T置標記（表示不再是新加入Q’中的狀態(tài)）。4.重復(fù)步驟3，直到Q’中不再含有未標記的狀態(tài)為止；5.重命名Q’中的狀態(tài)，最后獲得等價的DFAM。例把上例的NFA確定化

設(shè)NFAM＝({q0,q1},{0,1},f,{q0},{q1}),狀態(tài)轉(zhuǎn)換圖為，試將其確定化解：

1.M’的初態(tài)：I0={q0}。則Q中就有了I0狀態(tài)2.由Q中的狀態(tài)I0={q0}，查看M機，有：

f({q0},0)={q0}、f({q0},1)={q1}=I1

此時，Q={I0,I1}q0q1110003.由Q中的狀態(tài)I1={q1}，查看M機，有：

f({q1},0)={q0,q1}

=I2、f({q1},1)={q0}=I0此時，Q={I0,I1,I2}3.由Q中的狀態(tài)I2={q0,q1}，查看M機，有：

f({q0,q1},0)={q0,q1}、f({q0,q1},1)={q0,q1}=I2此時，Q={I0,I1,I2}4.F={I1,I2}NFA經(jīng)過確定化后，變?yōu)椋篋FAM’=({I0,I1,I2},{0,1},,I0,{I1,I2}

）

Q01I0={q0}I0={q0}I1={q1}I1={q1}I2={q0,q1}

I0={q0}I2={q0,q1}

I2={q0,q1}

I2={q0,q1}

01I0I0I1I1I2I0I2I2I2狀態(tài)轉(zhuǎn)換圖如下：I0I111000I21第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機3.4.5DFA的化簡(最小化)********（1）問題：化簡DFAM已知-輸入：DFAM求-輸出：DFAM’，使得L(M’)=L(M)且M’的狀態(tài)數(shù)最少化簡前提：接受的語言必須相同第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機3.4.5DFA的化簡（2）概念：DFA化簡：尋找一個狀態(tài)數(shù)比源DFAM少的DFAM’，使得L(M’)=L(M)且對于M’(1)沒有多余狀態(tài)（2）它的狀態(tài)集中，沒有兩個狀態(tài)是互相等價的多余狀態(tài)：：從該自動機的開始狀態(tài)出發(fā)，任何輸入串都不能達到的狀態(tài)。等價狀態(tài)：設(shè)DFAM=(Q,,f,S0,F)，s，t∈Q。若對任何Σ，f(s,)F當且僅當f(t,)F

，則稱狀態(tài)s和t是等價的。如果s和t不等價，則稱s和t是可區(qū)別的。第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機3.4.5DFA的化簡(3)化簡(最小化)算法基本思想——劃分法1.將DFAM中的狀態(tài)劃分為互不相交的子集，每個子集內(nèi)部的狀態(tài)都等價；而在不同子集間的狀態(tài)均不等價。2.從每個子集中任選一個狀態(tài)作為代表，消去其它等價狀態(tài)。3.把那些原來射入其它等價狀態(tài)的弧改為射入相應(yīng)的代表狀態(tài)。3.4.5DFA的化簡(4)化簡算法1.把狀態(tài)集S劃分為終態(tài)集和非終態(tài)集：∏0＝{I01,I02}，I01屬于非終態(tài)集,I02屬于終態(tài)集。因為終態(tài)能識別，而非終態(tài)不能，所以它們是可區(qū)別的；2.假定經(jīng)過k次劃分后：∏k＝{Ik1……Ikm}.這m個子集之間可區(qū)分，子集內(nèi)部還是否可以劃分？任取一個子集Iki={s1,s2,……sk},若存在某讀入字符a，使f(Iki,a)的結(jié)果不是全部包含在∏k的某個子集中，則說明Iki中有不等價的狀態(tài)，還要進一步劃分。對∏k中所有子集都進行測試，以完成一次劃分。第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機3.4.5DFA的化簡(4)化簡算法3.重復(fù)步驟2，直到所含的子集數(shù)不再增加為止。4.對每個子集任取一狀態(tài)為代表。若該子集包含原有的初態(tài)，則相應(yīng)代表狀態(tài)就是最小化后M的初態(tài)；同樣，若該子集包含原有的終態(tài)，則相應(yīng)代表狀態(tài)就是最小化后M的終態(tài)。注：可以通過消除多余狀態(tài)，合并等價狀態(tài)而轉(zhuǎn)化成一個最小化的與之等價的有限自動機。第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機例：設(shè)有一DFA的狀態(tài)轉(zhuǎn)換圖如下，試化簡之。0123546aaaaaaabbbbbbb解：1.把M的狀態(tài)分為兩組：終態(tài)集，非終態(tài)集∏0＝{{0,1,2},{3,4,5,6}}2.a)考察非終態(tài)集：

f({0,1,2},a)={1,3}不屬于∏0的任何一個子集，所以{0，1，2}要分開得到：∏1`＝{{1}，{0,2}，{3,4,5,6}}再看：f({0,2},a)={1}屬于∏1‘的子集

f({0,2},b)={2,5}不屬于∏1‘的任何子集，所以{0,2}要分開得到：∏1``＝{{1}，{0}，{2}，{3,4,5,6}}第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機解：（續(xù)）2.b)考察終態(tài)集：

f({3,4,5,6},a)={3,6}包含于∏1“的子集{3,4,5,6}f({3,4,5,6},b)={4,5}包含于∏1“的子集{3,4,5,6}所以{3,4,5,6}不可再劃分3.整個劃分為4個組：∏2＝{{1},{0},{2},{3,4,5,6}}4.令狀態(tài)3代表{3,4,5,6}，把原來到達狀態(tài)4，5，6的弧都導(dǎo)入3，并刪除4，5，6。得：第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機第三章詞法分析

第四節(jié)正規(guī)式與有窮自動機012aab3aabb即為化簡了的DFA3.4.6有窮自動機到正規(guī)式的轉(zhuǎn)換方法：（1）在原有轉(zhuǎn)換圖上添加兩節(jié)點x，y；x通過線與所有初態(tài)節(jié)點相連，所有終態(tài)節(jié)點通過線與y相連（2）按如下法則逐步消