1、1 本章本章將介紹正規文法和有窮自動將介紹正規文法和有窮自動機之間的關系，所涉及的內容是編譯機之間的關系，所涉及的內容是編譯中詞法分析技術和自動生成詞法分析中詞法分析技術和自動生成詞法分析程序的理論。程序的理論。第第3 3章章 自動機理論基礎自動機理論基礎2教學要求教學要求掌握：掌握：正規式，正規式，DFADFA的概念，的概念，NFANFA的概念的概念理解理解：將：將DFA DFA 轉換為轉換為NFANFA，正規文法與有窮，正規文法與有窮自動機間的轉換自動機間的轉換重點：重點：正規式構造正規式構造DFADFA，DFADFA最小化最小化難點難點：正規表達式構造：正規表達式構造DFADFA3一、正

2、規式一、正規式二、二、正規文法到正規式正規文法到正規式三、三、確定有窮自動機確定有窮自動機四、四、不確定有窮自動機不確定有窮自動機五、五、 NFA轉換為等價的轉換為等價的DFA六、六、 DFA的化簡的化簡七、七、正規式和有窮自動機的等價正規式和有窮自動機的等價八、正規文法和有窮自動機的等價性八、正規文法和有窮自動機的等價性*典型例題及解答典型例題及解答 教學大綱教學大綱4知識結構知識結構詞法分析詞法分析自動構造工具自動構造工具正規集正規集正規式正規式有窮自動機（有窮自動機（NFA DFA)正規文法正規文法5一、一、 正規式和正規集正規式和正規集 正規集正規集可以用可以用正規表達式正規表達式（簡

3、稱（簡稱正規式正規式）表示。表示。 正規表達式正規表達式是表示是表示正規集正規集一種方法。一一種方法。一個字集合是個字集合是正規集正規集當且僅當它能用當且僅當它能用正規正規式式表示。表示。6 正規式和正規集的遞歸定義：正規式和正規集的遞歸定義：對給定的字母表對給定的字母表 1) 和和都是都是 上的正規式，它們所表示的正規上的正規式，它們所表示的正規集為集為 和和;2) 任何任何a ，a是是 上的正規式，它所表示的上的正規式，它所表示的正規集為正規集為a ;73) 假定假定e e1 1和和e2都是都是 上的正規式，它們所表示的上的正規式，它們所表示的正規集為正規集為L(e1)和和L(e2)，則，

4、則i) (e1|e2)為正規式，它所表示的正規集為為正規式，它所表示的正規集為L(e1) L(e2)，ii) (e1.e2)為正規式，它所表示的正規集為為正規式，它所表示的正規集為L(e1)L(e2)，iii) (e1)*為正規式，它所表示的正規集為為正規式，它所表示的正規集為(L(e1)*，僅由僅由有限次有限次使用上述三步驟而定義的表達式才使用上述三步驟而定義的表達式才是是 上的正規式，僅由這些正規式表示的字集上的正規式，僅由這些正規式表示的字集才是才是 上的正規集。上的正規集。8正規式正規集aaa|ba,babab(a|b)(a|b)aa，bb,ab,baa*，a,aa, ，aaaa(a|

5、b)* ，a,b,aa,ab,aab,abab, (a|b)*(aa|bb) (a|b)*上所有含有兩個相繼的a或兩個相繼的b組成的串例：例： a,ba,b， 上的正規式和相應的正規集為：上的正規式和相應的正規集為：9其中的其中的“ ”讀為讀為“或或”（也有使用（也有使用“+”代替代替 “ ” 的的）；）；“ ”讀為讀為“連接連接”；“ ”讀為讀為“閉包閉包”（即，任（即，任意有限次的自重復連接）。在不致混淆時，括號可省去，意有限次的自重復連接）。在不致混淆時，括號可省去，但規定算符的優先順序為但規定算符的優先順序為“ ”、“ ”、“ ”、“ ”、“ ” 。連接符。連接符“ ”一般可省略不寫。

6、一般可省略不寫。“ ”、“ ”和和“ ” 都是左結合的都是左結合的10 討論下面兩個例子討論下面兩個例子例例1 1 令令 =l=l，dd，則，則 上的正規式上的正規式 r=l(lr=l(l d)d) 定義定義的正規集為的正規集為: l,ll,ld,ldd,: l,ll,ld,ldd,其中其中l l代表字母代表字母,d,d代表數字代表數字, ,正規式正規式 即是即是 字母字母( (字母字母| |數字數字) ) , ,它表示的正規集中的每個它表示的正規集中的每個元素的模式是元素的模式是“字母打頭的字母數字串字母打頭的字母數字串”, ,就是就是PascalPascal和多數程序設計語言允許的標和多數

7、程序設計語言允許的標識符的詞法規則識符的詞法規則. .11例例2 2：令：令 d d， ，e e，則，則 上的正上的正規式為：規式為：d d* *(.dd(.dd* *| | )(e(+|-|)(e(+|-| )dd)dd* *| | ) )表示的是無符號數。表示的是無符號數。 其中其中d d為為0 09 9中的數字。中的數字。 比如：比如：2,12.59,3.6e2,471.88e-12,12.59,3.6e2,471.88e-1等都是正規等都是正規式表示集合中的元素。式表示集合中的元素。12若兩個正規式若兩個正規式e e1 1和和e e2 2所表示的所表示的正規集相同，正規集相同，則說則說

8、e e1 1和和e e2 2等價等價, ,寫作寫作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 ) ) 正規式的等價正規式的等價13 對正規式，下列等價成立：對正規式，下列等價成立： e1|e2 = e2|e1 交換律交換律 e1 |(e2|e3) = (e1|e2)|e3 結合律結合律 e1(e2e3) = (e1e2)e3 結合

9、律結合律 e1(e2|e3) = e1e2|e1e3 分配律分配律 (e2|e3)e1 = e2e1|e3 e1分配律分配律 e = e = e e1e2 e2 e1 S*=(S|)* 是是“連接連接”的恒等元素（零一律）的恒等元素（零一律） (a*)*=a*L(e1|e2) = L(e1 ) L(e2)= L(e2 ) L(e1)= L(e2|e1)14對于任意一個正規文法，存在一個同一語言的正規式。對每一個正規式，存在一個正規文法。即正規式正規文法 正規式正規式正規文法正規文法文法G=（VN，VT，P，S）令VT=，對正規式r，選擇一個非終結符S生成Sr，S為G的開始符號。 若x，y都是正

10、規式，對形如Axy的產生式，寫成AxB，By。其中B VN二、正規文法與正規式轉換二、正規文法與正規式轉換* *15 對形如Ax*y的產生式，重寫為： AxB Ay BxB By B為新的非終結符，B VN對形如Ax|y的產生式，重寫為： Ax Ay 不斷利用上述規則進行變換即可。16例：將Ra(a|d)*變換成正規文法。令S是文法開始符號。解：S a(a|d)*SaAA(a|d)*A(a|d)BA B(a|d)BB 根據上述規則1xa，y(a|d)*根據上述規則2x(a|d)y17最后得到：SaAAaBAdBA BaBBdBB 18 正規文法正規文法正規式正規式轉換規則：轉換規則： AxB，

11、By 正規式為： A=xy AxA|y 正規式為： A=x*y Ax，Ay 正規式為： A=x|y 例：文法GS：S aAS aA aAA dAA aA d轉換為正規式19S aAS aA aAA dAA aA dSaA|aAaA|dAAa|dA(aA|dA)|(a|d) A(a|d)A|(a|d) A(a|d)*(a|d)根據上述規則3Ax，Ay推出A=x|y將它化為正規文法變成A (a|d)A|(a|d) 再根據上述規則2轉換xy (a|d)20Sa( (a|d)*(a|d) |a =a(a|d)+|a =a(a|d)+|)= a(a|d)+將A代入SaA|a得到如下：21 三、三、確定的

12、有窮自動機確定的有窮自動機DFA 有窮自動機( (也稱有限自動機也稱有限自動機) )作為一種識作為一種識別裝置別裝置，是詞法分析程序的工具和方法，能自動識別（且是正確識別正確識別）正規集。即識別正規即識別正規文法所定義的語言和正規式所表示的集合，引文法所定義的語言和正規式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程序入有窮自動機這個理論，正是為詞法分析程序的自動構造尋找特殊的方法和工具。的自動構造尋找特殊的方法和工具。分為確定的有窮自動機（確定的有窮自動機（DFA）不確定的有窮自動機（不確定的有窮自動機（NFA） 22一個確定的有窮自動機M是一個五元組： M=（Q，f，q0，Z），其

13、中： Q是一個有窮集，每個元素表示一個狀態；是一個有窮字母表，每個元素是一個輸入字符； f是轉換函數，是在QQ上的映象上的映象，如： f(Qi ，a)= Qj (Qi, QjQ)； q0是初態， q0 K； ZQ，是終態集。 含義：當前狀態為Ki，輸入字符a，轉換為Kj狀態DFADFA映射的唯一性和初態的唯一性映射的唯一性和初態的唯一性23 方法如下： 初始態用 “”或“”表示； 終態點用 “” 或“” 表示； 若f(Ki ，a)= Kj ，則從狀態點Ki 到Kj畫弧，標記為a。1 1、單詞的構成規則用狀態轉換圖表示、單詞的構成規則用狀態轉換圖表示DFADFA等價表示法：等價表示法：DFADF

14、A形式定義形式定義= =狀態轉換圖狀態轉換圖= =狀態矩陣狀態矩陣24狀態轉換圖(也稱狀態變遷圖狀態變遷圖)是一張有限方向圖。有限個狀態，用結點表示狀態，其中有一個初態有一個初態(初態用箭頭指出)，至少有一個終態至少有一個終態(終態用雙圈表示)。狀態之間用帶箭頭的弧線連結，弧線上標記的字符表示在射出狀態下可能出現的輸入字符或字符類。識別標識符的轉換圖012字母字母或數字其它*25一個狀態圖可用于識別一定的字符串，大多數程序設計語言的單詞符號都可以用轉換圖來識別。識別過程是識別過程是：從初始狀態0開始，若讀入一個字母，轉入1狀態，若再讀入字母或數字，仍處于1狀態，否則轉向2狀態，結束一個標識符的

15、識別過程。狀態上的*表示多讀入一個符號。012字母字母或數字其它*26例如：例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：其中：f定義如下：定義如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3 f(3，b)=3狀態圖如下：0312aaaa狀態轉換圖狀態轉換圖bbbb27例: 一個單部電梯對3層樓進行控制的電梯控制系統的DFA描述。問題分析：用戶請求（輸入）上1、上2、上3下1、下2、下3狀態設置（所處樓層）1層2層3層S1S2S328Ch2 形式語言自動機理論基礎2.2 自動機基礎2.2.1 確定的FA

16、（DFA）S2S3S1上2/下2上3/下3上1/下1下1下2上3上2下1上3292、用矩陣表示、用矩陣表示DFA :方法： 行表示狀態 列表示輸入字符 元素表示相應狀態行和輸入字符下的新狀態。 “” 標明初態，默認第一行是初態。 終態行在表右端標1，非終態標030 例如：例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：其中：f定義如下：定義如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3 f(3，b)=3 a b 0 1 2 1 3 2 2 1 3 3* 3 3 狀態轉換矩陣狀態轉換矩陣31例：baSZa

17、,b表示：f(S,a)=Z f(S,b)=Z f(Z,a)=Z f(Z,b)=ZabSZZZZZ01寫成正規式是： (a|b)(a|b)*32Ch2 形式語言自動機理論基礎2.2 自動機基礎2.2.1 確定的FA（DFA）電梯控制的狀態矩陣表示上1下1上2 下2上3下3S1* S1S2*S3*S1S1S1S2S2 S2S2S3S3S3 S3333、DFA接接受（識別）的概念受（識別）的概念： 對于對于*中的任何字符串中的任何字符串t，若存在一條初態到若存在一條初態到某一終態的路，且這條路上所有弧的標記符連接成某一終態的路，且這條路上所有弧的標記符連接成的字符串等于的字符串等于t，則稱，則稱t可

18、為可為DFA M所接受。所接受。 若若M的初態同時又是終態，則空字可為的初態同時又是終態，則空字可為M所接所接受。受。34 輸入字符串輸入字符串t（t表示成表示成Tt1形式，形式，T ，t1 *），在），在DFA M上運行的定義為：上運行的定義為：f（Q，Tt1）=f(f(Q,T),t1)，其中，其中Q K。4、接受（識別）的理解：接受（識別）的理解： 設設Q K，函數，函數f(Q, )=Q，則輸入字符串是，則輸入字符串是空串，并停留在原狀態上。空串，并停留在原狀態上。 35例：證明例：證明t t= =baabbaab被下圖的被下圖的DFADFA所接受所接受。f f（S S，baabbaab）

19、=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屬于終態。屬于終態。得證。得證。bSUVQabba, baa36 DFA的確定性表現在：的確定性表現在： 對任何狀態s S，在讀入了輸入符號a 之后，能夠唯一地確定唯一地確定下一個狀態 映射函數：SS是一個單值單值函數 從狀態轉換圖來看，若字母表含有n個輸入字符，那末任何一個狀態結點最多有最多有n條弧條弧射出射出，而且每條弧以一

20、個不同的輸入不同的輸入字符字符標記。37 DFA M所能接受的字符串的全體記為L（M）稱為語言 （也即句子的集合）結論：結論： 上一個符上一個符號號串集串集V V 是正規的，當且僅當是正規的，當且僅當存在一個存在一個 上的確定有窮自動機上的確定有窮自動機M M，使得，使得V=L(M)V=L(M) 文法是語言的生成系統，是從產生的觀點來描述語言的。 自動機是語言的識別系統，是從識別的觀點來描述語言的文法和自動機的對比文法和自動機的對比38四、四、 不確定的有窮自動機不確定的有窮自動機NFA 一個不確定的有窮自動機NFA M是一個五元組：M=（Q，f， q0 ，Z），其中： Q是一個有窮集，每個元

21、素表示一個狀態； 是一個有窮字母表，每個元素是一個輸入字符； f是一個從Q()到到2Q的映象； q0是初態， q0 Q ； Z Q，是一個終態集。【要點】至少一個初態，若干個終態。39 （1）DFA任何狀態都沒有沒有轉換，即沒有任何狀態可以不進行輸入符號的匹配就直接進入下一個狀態； （2）DFA對任何狀態S和任何輸入符號a，最多只有一條標記為a的邊離開S，即轉換函數：S S是一個單值單值部分函數。40例子例子 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

22、=Zf f（Z Z，1 1）=P=Pf f（S S，1 1）=S=S，ZZ狀態圖表示狀態圖表示SPZ00,1111 * *上的符號串上的符號串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所接受（識別）所接受（識別）41Ch2 形式語言自動機理論基礎2.2 自動機基礎2.2.2 非確定的FA(NFA)例2.24: 給出一個接收字符串aa*|bb*的NFA M，如下圖所示。對字符串aaa的接受路徑為0，1，2，2，2，接受路徑中邊的標記是，a，a，a，它們的連

23、接為字符串aaa，在連接中消失。abastart04132a42*上的符號串t被NFA M接受（識別）: 對于*中的任何一個串t，若存在一條從某一初態結點到某一終態結點的通路，且這條通路上所有弧的標記字依序連接成的串(不理采那些標記為的弧)等于t，則稱t可為NFA M所識別(讀出或接受)。 若M的某些結點既是初態結點又是終態結點；或者存在一條從某個初態結點到某個終態結點的道路,其上所有弧的標記均為，那么空字可為M所接受。43 使用NFA判定某個輸入符號串的時候，可能出現不確定的情況：不知道下面選擇那個狀態。如果選擇不好，該輸入符號串可能不能到達終止狀態。但是，我們不能說該輸入符號串不能被該NF

24、A接受。 如果通過嘗試的方法，不斷試探來確定輸入符號串是否可被接受，那么判定的效率將降低。解決的方法是將NFA轉換為等價的DFA。 NFA M所能接受的符號串的全體記為L(M)結論：上一個符號串集V 是正規的，當且僅當存在一個上的不確定的有窮自動機M，使得V=L(M)。44定理：設定理：設L為一個由不確定的有窮自動機接受的集合，則存為一個由不確定的有窮自動機接受的集合，則存在一個接受在一個接受L的確定的有窮自動機。的確定的有窮自動機。將將NFA轉換成接受同樣語言的轉換成接受同樣語言的DFA，這種算法稱為，這種算法稱為子集法。子集法。NFA與與DFA的等價性：的等價性：對于每個對于每個NFA M

25、存在一個存在一個DFA M，使使L(M)=L(M)。NFA可以利用可以利用子集法進行確定化子集法進行確定化，對于一個，對于一個NFA M總可以構總可以構造一個等價的造一個等價的DFA M。NFA到到DFA構造基本思路構造基本思路：DFA的每一個狀態對于的每一個狀態對于NFA的一的一組狀態。組狀態。DFA利用它的一個狀態去記錄在利用它的一個狀態去記錄在NFA讀入一個輸入讀入一個輸入符號后可能到達的所有狀態。符號后可能到達的所有狀態。五、五、NFANFA轉換為等價的轉換為等價的DFADFA（NFANFA確定化）確定化）454647 -closure(I) = -closure(1)=1，2=I J

26、=5，4，3 Ia= -closure(J)= -closure(5，4，3) =5，4，3，6，2，7，861a 234578aa 設設a是是 中的一個中的一個字符，定義字符，定義Ia= -closure(J) 其中，其中，J為為I中的某中的某個狀態出發經過個狀態出發經過一條一條a弧而到達弧而到達的狀態集合。的狀態集合。48 把確定化的過程把確定化的過程: : 不失一般性，設字母表只包含兩個不失一般性，設字母表只包含兩個a a和和b b，我們構造一張表我們構造一張表: :IIaIb -Closure(X)49首先，置第首先，置第1行第行第1列為列為 -closure(X)求出求出這一列的這一

27、列的Ia，Ib；然后，檢查這兩個然后，檢查這兩個Ia，Ib，看它們是否已在，看它們是否已在表中的第一列中出現，把未曾出現的填入表中的第一列中出現，把未曾出現的填入后面的空行的第后面的空行的第1列上，求出每行第列上，求出每行第2，3列列上的集合上的集合.重復上述過程，知道所有第重復上述過程，知道所有第2，3列子集全列子集全部出現在第一列為止。部出現在第一列為止。50IIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,

28、1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YXY 514236ab ababab51 現在把這張表看成一個狀態轉換矩陣，把現在把這張表看成一個狀態轉換矩陣，把其中的每個子集看成一個狀態。其中的每個子集看成一個狀態。 這張表唯一刻劃了一個確定的有限自動機這張表唯一刻劃了一個確定的有限自動機M，它的初態是，它的初態是 -closure(X) ，它的終，它的終態是含有原終態態是含有原終態Y的子集。的子集。 不難看出，這個不難看出，這個DFA M與與M等價。等價。52Iab0121322143*344*655*656

29、*340123546aabbbabaababab53Ch2 形式語言自動機理論基礎2.2 自動機基礎2.2.3 NFA確定化綜述 求Ia步驟：(1) 求-closure(I)；(2) 求J；(3) 求-closure(J)；NFA確定化關鍵：(1) 消去弧；(2) 解決映射不唯一問題。-closure(I)求Ia54Ch2 形式語言自動機理論基礎2.2 自動機基礎2.2.3 NFA確定化例2: 有NFA M如下圖所示。12385467aaa55Ch2 形式語言自動機理論基礎2.2 自動機基礎2.2.3 NFA確定化IIa2, 3, 4, 5, 6, 7, 8 3, 8120 -closure(

30、S0)=1,21*2*2, 3, 4, 5, 6, 7, 8 3, 8565758六、確定有窮自動機六、確定有窮自動機DFA的化簡的化簡（DFA最小化）最小化） 說一個有窮自動機是化簡了的，即是說，它說一個有窮自動機是化簡了的，即是說，它沒有多余狀態沒有多余狀態并且它的狀態中并且它的狀態中沒有兩個是互相等沒有兩個是互相等價的價的。一個有窮自動機可以通過消除多余狀態和。一個有窮自動機可以通過消除多余狀態和合并等價狀態而轉換成一個最小的與之等價的有合并等價狀態而轉換成一個最小的與之等價的有窮自動機。窮自動機。 將多余狀態消除而形成一個最小的等價的DFA。化簡不僅是去除死狀態，不可能到達狀態，還包括

31、狀態的合并。 DFA的最小化就是尋求最小狀態的最小化就是尋求最小狀態DFA591、多余狀態的概念： 所謂有窮自動機的多余狀態，是指這樣的狀態：從自動所謂有窮自動機的多余狀態，是指這樣的狀態：從自動機的開始狀態出發，任何輸入串也不能到達的那個狀態；或機的開始狀態出發，任何輸入串也不能到達的那個狀態；或者從這個狀態沒有通路到達終態。者從這個狀態沒有通路到達終態。 如下圖中的S4狀態是多余的。在圖中，沒有一個狀態能到達S4。當S4是多余時，又可以推出S6是多余的。同樣也可以推出S8也是多余的。 最小狀態最小狀態DFA的含義的含義: 1.沒有多余狀態沒有多余狀態(死狀態死狀態) 2.沒有兩個狀態是互相

32、等價（不可區別）沒有兩個狀態是互相等價（不可區別）6001S0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6S8S01S7S0S11S8S3S6001S0S1S50S1S2S71S2S2S51S3S5S70S5S3S10S7S0S11化簡后的結果：左右等價612、等價的條件（狀態、等價的條件（狀態S和和T） 兩個狀態兩個狀態s s和和t t等價：滿足等價：滿足一致性一致性同是終態或同是非終態同是終態或同是非終態蔓延性蔓延性從從S S出發讀入所有出發讀入所有a a a a和從和從T T出發出發讀入讀入a a到達的狀態等價。到達的狀態等價。623、等價的方法（

33、分割法）等價的方法（分割法）方法：將DFA的狀態分割成一些互不相交的子集。把一個把一個DFADFA（不含多余狀態）的狀態分成一些不（不含多余狀態）的狀態分成一些不相交的子集，使得任何不同的兩子集的狀態都相交的子集，使得任何不同的兩子集的狀態都是可區別的，而同一子集中的任何兩個狀態都是可區別的，而同一子集中的任何兩個狀態都是等價的。是等價的。分割法的核心 把DFA的全部狀態劃分成一些互不相交的子集，使得任何不同的兩子集的狀態都是可區別的（不等價），而同一子集中的任何兩個狀態都是等價的.63DFA化簡（最小化方法最小化方法） 算法算法： 所有狀態分成兩個子集終態集和非終態集； 運用判定狀態等價的原

34、則分別對兩個子集的狀態進行分析和劃分，若發現某個狀態與其它狀態不等價，則將其作為一個新的狀態子集，如果無法區分，則放在同一子集中； 從每個子集中選出一個狀態做代表，即可構成簡化的DFA； 含有原來初態的子集仍為初態，各終態的子集仍為終態。64Ch2 形式語言自動機理論基礎2.2 自動機基礎2.2.4 DFA的化簡Step1: 形成基本劃分。劃分為終態集和非終態集。P0 = （ 0,1 , 2）考察 ： 0,1a =1 0,10,1b =2 2a例1： 設確定有限自動機DFA M ，如圖所示。bbaa021Step2: 重新命名。令 0,1為0，令2為1。基本劃分不可對 0,1 再分65Ch2

35、形式語言自動機理論基礎2.2 自動機基礎2.2.4 DFA的化簡baa10化簡后的DFA M66CBASaaabbbba,CDBAEFSbaaaaaabbbbbba例例2：化簡下圖的：化簡下圖的DFA671643257aaaaaaabbbbbbb例例3：將下圖中的：將下圖中的DFA M最小化。最小化。68Ch2 形式語言自動機理論基礎2.2 自動機基礎2.2.4 DFA的化簡第一步，對M的狀態形成基本劃分： 設p是基本劃分。將 p分成q , q2，即p=(1, 2, 3, 4 , 5, 6, 7 )= ( q1,q2 )第二步，對q , q2考察知：對p的q，I=1時 Ia= 6I=2時 Ia

36、= 7I=3時 Ia= 1I=4時 Ia= 4Ib= 3Ib= 3Ib= 5Ib= 669Ch2 形式語言自動機理論基礎2.2 自動機基礎2.2.4 DFA的化簡對q1形成新的劃分：q1=(q3, q4)=（1, 2，3, 4）對p的q2， I=5時 Ia=7 Ib=3I=6時 Ia=4 Ib=1I=7時 Ia=4 Ib=2在輸入a或b的情況下， q2中的狀態5與狀態 6,7 是不等價的，構成q2新的劃分：70Ch2 形式語言自動機理論基礎2.2 自動機基礎2.2.4 DFA的化簡q2新的劃分：q2 =( q5, q6 )=（5，6, 7）由此，對基本劃分p0 經考察且劃分后，形成新的劃分p1

37、：p1 =（q3，q4，q5，q6）= ( 1,2，3,4，5，6,7 )71Ch2 形式語言自動機理論基礎2.2 自動機基礎2.2.4 DFA的化簡第三步，對新形成的劃分p1重復上述第二步，則對p1 中q4的狀態 3,4 在輸入字符a的情況下考察其是不等價的，再劃分為q4=（q7, q8）=（3, 4）對劃分p1 經考察且劃分后，形成新的劃分p2：p2 =（q3, q5, q6, q7, q8 ）= ( 1,2, 5, 6,7 , 3, 4 )721643257aaaaaaabbbbbbb16435aaaaabbbbb至此所有狀態集中的狀態皆為等價狀態。73 合并狀態注意：a、由于一個子集中

38、，各狀態等價，故只需將原進入該子集中各狀態的弧都改為進入所選的狀態，子集中各狀態射出的弧均改為從該狀態射出。b、含有原來初態的子集仍為初態，含原終態的子集仍為終態74例例4：將下圖中的：將下圖中的DFA M最小化。最小化。1402357600000000111111751、一個終態（可接受態）組成，一個非終態組成。 P0(0,1,2,3,5,4,6,7)2、0,1狀態輸入1到2狀態,2,5輸入1到4狀態,3狀態輸入1為,2狀態和4狀態屬于不同的子集,P1=(0,1,2,5,3)3、4,7輸入1到狀態4,6輸入1到, P3=(4,7,6)0,1、2,5、 3、4,7、 6都不可再分了,分別用A,

39、B,C,D,E表示,簡化后圖如下:761402357600000000111111ADBCE0000011177 正規式和FA之間也可以互相轉換，轉換的方法是從已知的正規式先構造出等價的-NFA（本節），去掉-NFA中的空動作變換為不含遷移的NFA，然后再把NFA轉化為DFA，最后再對DFA化簡，求得最小DFA。 上述各種轉換關系可用圖2-8表示。七、七、正規式和有窮自動機的等價性正規式和有窮自動機的等價性 78正規式和有窮自動機的等價性：正規式和有窮自動機的等價性： 對于對于上的上的NFA MNFA M，可以構造一個，可以構造一個上的正規式上的正規式R R，使得，使得L(R)=L(M)L(R

40、)=L(M)。 對于對于上的每個正規式上的每個正規式R R，可以構，可以構造一個造一個上的上的NFA MNFA M，使得，使得L(M)=L(R)L(M)=L(R)。79Ch2 形式語言自動機理論基礎2.3 正規式與自動機2.3.2 正規式與FA(1) 增加結點X，并從 X引弧到達S0中的所有狀態；(2) 增加結點 Y，并從Z中所有狀態引弧 到達 Y；step1: 將NFA M進行拓廣；1、在NFA M上構照正規式R。即從L(M) L(R）方法：在每一條弧上用一個正規式作標記。規則如下：80Y3aXstep2: 利用利用替換規則一替換規則一逐步消去逐步消去 M中的結和弧，并中的結和弧，并用正規式

41、代替原來用正規式代替原來M 中的弧標記，直至只剩下中的弧標記，直至只剩下結為止。結為止。XY81(1)123R1R213R1R2(2)12R1R221R1|R221R1+R2替換為或(3)321R1R2R331R1R2*R3替換為替換為替換規則一替換規則一82Ch2 形式語言自動機理論基礎2.3 正規式與自動機2.3.2 正規式與FAY1234bbaa0a,b例1: 有NFA M 如下圖所示。a,ba,b83Ch2 形式語言自動機理論基礎2.3 正規式與自動機2.3.2 正規式與FAY1234bbaa0a,ba,ba,bX84Ch2 形式語言自動機理論基礎2.3 正規式與自動機2.3.2 正規

42、式與FAY123baa,b4X(a|b)*b(a|b)*a用規則(3)消去0結和a,b弧a,b85Ch2 形式語言自動機理論基礎2.3 正規式與自動機2.3.2 正規式與FA用規則(3)消去2,4結和2個a|b弧Y13X(a|b)*b(a|b)*ab(a|b)*a(a|b)*86Ch2 形式語言自動機理論基礎2.3 正規式與自動機2.3.2 正規式與FA(a|b)*aa(a|b)*YX用規則(1)消去1,3結(a|b)*b b(a|b)*87Ch2 形式語言自動機理論基礎2.3 正規式與自動機2.3.2 正規式與FA用規則(2)消去2個弧(a|b)*bb(a|b)*|(a|b)*aa(a|b)

43、*YYX用分配率實施化簡(a|b)*(aa|bb)(a|b)*X正規式正規式88例2: L(M)如下圖：求正規式R，使L(R)=L(M).解：aba,baba,bxyya|bxa|byx(a|b)(a|b)*因此：L(R)= (a|b)(a|b)*8903412aabba,ba,ba,b例3：M狀態圖如下：求正規式R，是L(R)=L(M).90解：加解：加x,y結點。結點。a,b03412aabba,ba,bxy91042aabba,ba,bxya,ba,b0aa(a|b)*bb(a|b)*xy92y(a|b)*(aa|bb)(a|b)*x所以 L(R) =(a|b)*(aa|bb)(a|b)

44、* 例4：L(M)如下圖，求L(R)-+abbaaba,b93解：-+abbaaba,b-abbaaba,bxy94-abbaa|ba,bxy-a|ba|b|abbaxy(a|b|abba)*(a|b)xy所以所以 L(R) = (a|b|abba)*(a|b) =(a|b)*(a|b)=(a|b)+95例例5：L(M) 如下圖，求如下圖，求L(R) .-+abbbbabbaa,ba解：-+abbbbabbaa,ba96abba|abb|bb+a,b-aa*(abba|abb|bb)(a|b)*+-所以 L(R) = a*(abba|abb|bb)(a|b)* 注：注：abba+abb+bb

45、不能把不能把bb提取出來提取出來972、L(R) NFA，從正規式，從正規式R構造構造NFA由正規式V直接形成拓廣的FA狀態圖。構造上的NFA M，使得L(M)=L(V);方法如下：方法如下：98Ch2 形式語言自動機理論基礎2.3 正規式與自動機2.3.2 正規式與FAai1) 若V是或上的字符ai , 則2) 若1）不成立，則V具有V1|V2，V1V2，(V1)*形式，按照替換規則二分解V；3） 對新產生的弧標記重復1）、2），直到沒有新的弧和結產生為止。得到V相應的M，且L(M)=L(v).XYXY99Ch2 形式語言自動機理論基礎2.3 正規式與自動機2.3.2 正規式與FAR1R1|

46、R2ABR2AB替換為R1*ABACB替換為R1ACR2BR1R2AB替換為R1替換規則二(1)100例1：L(R) =(a|b)*abb，構造NFA使L(N)=L(R)解：xy(a|b)*abbxyabba,bxyabbabxyababb101例： L(R) =(a|b)*(aa|bb)(a|b)*構造L(M)使與L(R) 等價。102xy(a+b)*(aa+bb)(a+b)*xy(a+b)*aa+bb(a+b)*xyaabba,ba,b103xya baaabbb104八、正規文法和有窮自動機的等價性八、正規文法和有窮自動機的等價性采用下面的規則可以從正規文法采用下面的規則可以從正規文法G

47、直接構造一個有窮直接構造一個有窮自動機自動機NFAM；使得；使得L（M）L（G）：）：M M的字母表與的字母表與G G的終結符集相同的終結符集相同為為G G中的每個非終結符生成中的每個非終結符生成M M的一個狀態，的一個狀態，G G的開始符的開始符S S是開是開始狀態始狀態S S增加一個新狀態增加一個新狀態Z Z，作為，作為NFANFA的終態的終態對對G G中的形如中的形如A A tBtB的規則（其中的規則（其中t t為終結符或為終結符或 ，A A和和B B為為非終結符的產生式），構造非終結符的產生式），構造M M的一個轉換函數的一個轉換函數f(A,t)=Bf(A,t)=B對對G G中形如中形

48、如A A t t的產生式，構造的產生式，構造M M的一個轉換函數的一個轉換函數f(A,t)=Zf(A,t)=Z105 例例2-6 2-6 已知正規文法已知正規文法G3G3(S(S，A A，BB，aa，b b，c c，P P，S) S)，其中，其中P P內包含以下產生式：內包含以下產生式：根據上述轉換方法，與G3等價的FA M為：其中函數的定義式為：106例例2：與文法：與文法GS等價的等價的NFAM如圖如圖4.11GS: S a A S a A S bBS bBS S A aBA aBA bA A bA B aSB aSB bA B bA B B 107有窮自動機轉換成等價的正規文法：有窮自動機轉換成等價的正規文法：對轉換函數對轉換函數f(A,t)=B,可寫一產生式：可寫一產生式：A tB對可接受對可接受狀態狀態Z，增加一產生式：，增加一產生式：Z 有窮自動機的初態對應文法開始符有窮自動機的初態對應文法開始符有窮自動機的字母表為文法的終結符集有窮自動機的字母表為文法的終結符集108例