編譯原理2.2 自動機理論

本章將介紹正規(guī)文法和有窮自動機之間的關系，所涉及的內容是編譯中詞法分析技術和自動生成詞法分析程序的理論。第3章自動機理論基礎1教學要求掌握：正規(guī)式，DFA的概念，NFA的概念理解：將DFA轉換為NFA，正規(guī)文法與有窮自動機間的轉換重點：正規(guī)式構造DFA，DFA最小化難點：正規(guī)表達式構造DFA2一、正規(guī)式二、正規(guī)文法到正規(guī)式三、確定有窮自動機四、不確定有窮自動機五、NFA轉換為等價的DFA六、DFA的化簡七、正規(guī)式和有窮自動機的等價八、正規(guī)文法和有窮自動機的等價性*典型例題及解答教學大綱3知識結構詞法分析自動構造工具{正規(guī)集}正規(guī)式有窮自動機（NFADFA)正規(guī)文法①⑤⑥②③④4一、正規(guī)式和正規(guī)集正規(guī)集可以用正規(guī)表達式（簡稱正規(guī)式）表示。正規(guī)表達式是表示正規(guī)集一種方法。一個字集合是正規(guī)集當且僅當它能用正規(guī)式表示。5正規(guī)式和正規(guī)集的遞歸定義：對給定的字母表1)

和都是上的正規(guī)式，它們所表示的正規(guī)集為{}和;2)任何a，a是上的正規(guī)式，它所表示的正規(guī)集為{a};63)假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集為L(e1)和L(e2)，則i)(e1|e2)為正規(guī)式，它所表示的正規(guī)集為L(e1)L(e2)，ii)(e1.e2)為正規(guī)式，它所表示的正規(guī)集為L(e1)L(e2)，iii)(e1)*為正規(guī)式，它所表示的正規(guī)集為(L(e1))*，僅由有限次使用上述三步驟而定義的表達式才是上的正規(guī)式，僅由這些正規(guī)式表示的字集才是上的正規(guī)集。7正規(guī)式正規(guī)集a｛a｝a|b｛a,b}ab｛ab}(a|b)(a|b)｛aa，bb,ab,ba}a*｛，a,aa,…，aa…aa｝(a|b)*｛，a,b,aa,ab,aab,abab,…｝(a|b)*(aa|bb)(a|b)**上所有含有兩個相繼的a或兩個相繼的b組成的串例：＝{a,b}，上的正規(guī)式和相應的正規(guī)集為：8其中的“”讀為“或”（也有使用“+”代替

“”的）；“”讀為“連接”；“”讀為“閉包”（即，任意有限次的自重復連接）。在不致混淆時，括號可省去，但規(guī)定算符的優(yōu)先順序為“”、“”、“”、“”、

“”。連接符“”一般可省略不寫?！啊薄ⅰ啊焙?/p>

“”都是左結合的9

討論下面兩個例子例1令={l，d}，則上的正規(guī)式r=l(ld)定義的正規(guī)集為:{l,ll,ld,ldd,……},其中l(wèi)代表字母,d代表數字,正規(guī)式即是字母(字母|數字)

,它表示的正規(guī)集中的每個元素的模式是“字母打頭的字母數字串”,就是Pascal和多數程序設計語言允許的標識符的詞法規(guī)則.10例2：令＝｛d，，e，＋，－｝，則上的正規(guī)式為：d*(.dd*|)(e(+|-|)dd*|)表示的是無符號數。其中d為0～9中的數字。比如：2,12.59,3.6e2,471.88e-1等都是正規(guī)式表示集合中的元素。11若兩個正規(guī)式e1和e2所表示的正規(guī)集相同，則說e1和e2等價,寫作e1=e2。例如：e1=(ab)，e2=ba又如：e1=b(ab),e2=(ba)be1=(ab),e2

=(ab)正規(guī)式的等價12對正規(guī)式，下列等價成立：e1|e2=e2|e1 交換律e1|(e2|e3)=(e1|e2)|e3 結合律e1(e2e3)=(e1e2)e3 結合律e1(e2|e3)=e1e2|e1e3 分配律(e2|e3)e1=e2e1|e3e1 分配律e=e=e e1e2<>e2e1

S*=(S|ε)*是“連接”的恒等元素（零一律）(a*)*=a*L(e1|e2)=L(e1)

L(e2)=L(e2)

L(e1)=L(e2|e1)13對于任意一個正規(guī)文法，存在一個同一語言的正規(guī)式。對每一個正規(guī)式，存在一個正規(guī)文法。即正規(guī)式正規(guī)文法正規(guī)式正規(guī)文法文法G=（VN，VT，P，S）令VT=Σ，對正規(guī)式r，選擇一個非終結符S生成S→r，S為G的開始符號。若x，y都是正規(guī)式，對形如A→xy的產生式，寫成A→xB，B→y。其中BVN二、正規(guī)文法與正規(guī)式轉換*14對形如A→x*y的產生式，重寫為：

A→xBA→yB→xBB→yB為新的非終結符，BVN對形如A→x|y的產生式，重寫為：

A→xA→y

不斷利用上述規(guī)則進行變換即可。15例：將R＝a(a|d)*變換成正規(guī)文法。令S是文法開始符號。解：S→a(a|d)*S→aAA→(a|d)*A→(a|d)BA→B→(a|d)BB→

根據上述規(guī)則1x＝a，y＝(a|d)*根據上述規(guī)則2x＝(a|d)y＝16最后得到：S→aAA→aBA→dBA→B→aBB→dBB→17

正規(guī)文法正規(guī)式轉換規(guī)則：

A→xB，B→y正規(guī)式為：A=xy

A→xA|y正規(guī)式為：A=x*y

A→x，A→y正規(guī)式為：A=x|y

例：文法G[S]：S→aAS→aA→aAA→dAA→aA→d轉換為正規(guī)式18S→aAS→aA→aAA→dAA→aA→dS＝aA|aA＝aA|dAA＝a|dA＝(aA|dA)|(a|d)A＝(a|d)A|(a|d)A＝(a|d)*(a|d)根據上述規(guī)則3A→x，A→y推出A=x|y將它化為正規(guī)文法變成A→(a|d)A|(a|d)再根據上述規(guī)則2轉換x＝y＝(a|d)19S＝a(

(a|d)*(a|d))|a=a(a|d)+|a=a((a|d)+|)=a(a|d)+將A代入S＝aA|a得到如下：20

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

21一個確定的有窮自動機M是一個五元組：

M=（Q，Σ，f，q0，Z），其中：①Q是一個有窮集，每個元素表示一個狀態(tài)；②Σ是一個有窮字母表，每個元素是一個輸入字符；③f是轉換函數，是在Q×Σ→Q上的映象，如：f(Qi，a)=Qj(Qi,QjQ)；④q0是初態(tài)，q0K；⑤ZQ，是終態(tài)集。含義：當前狀態(tài)為Ki，輸入字符a，轉換為Kj狀態(tài)DFA映射的唯一性和初態(tài)的唯一性22方法如下：初始態(tài)用“－”或“”表示；終態(tài)點用“＋”或“”表示；若f(Ki

，a)=Kj

，則從狀態(tài)點Ki

到Kj畫弧，標記為a。1、單詞的構成規(guī)則用狀態(tài)轉換圖表示DFA等價表示法：DFA形式定義=狀態(tài)轉換圖=狀態(tài)矩陣23狀態(tài)轉換圖(也稱狀態(tài)變遷圖)是一張有限方向圖。有限個狀態(tài)，用結點表示狀態(tài)，其中有一個初態(tài)(初態(tài)用箭頭指出)，至少有一個終態(tài)(終態(tài)用雙圈表示)。狀態(tài)之間用帶箭頭的弧線連結，弧線上標記的字符表示在射出狀態(tài)下可能出現的輸入字符或字符類。識別標識符的轉換圖012字母字母或數字其它*24一個狀態(tài)圖可用于識別一定的字符串，大多數程序設計語言的單詞符號都可以用轉換圖來識別。識別過程是：從初始狀態(tài)0開始，若讀入一個字母，轉入1狀態(tài)，若再讀入字母或數字，仍處于1狀態(tài)，否則轉向2狀態(tài)，結束一個標識符的識別過程。狀態(tài)上的*表示多讀入一個符號。012字母字母或數字其它*25例如：DFAM=({0，1，2，3}，{a，b}，f，0，{3})，其中：f定義如下：f(0，a)=1 f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1 f(2，b)=3f(3，a)=3 f(3，b)=3狀態(tài)圖如下：0312aaaa狀態(tài)轉換圖bbbb26例:一個單部電梯對3層樓進行控制的電梯控制 系統的DFA描述。

問題分析：用戶請求（輸入）上1、上2、上3

下1、下2、下3

狀態(tài)設置（所處樓層）

1層2層3層

S1S2S327Ch2形式語言自動機理論基礎2.2自動機基礎2.2.1確定的FA（DFA）S2S3S1上2/下2上3/下3上1/下1下1下2上3上2下1上3282、用矩陣表示DFA:方法：行表示狀態(tài)列表示輸入字符元素表示相應狀態(tài)行和輸入字符下的新狀態(tài)。

“”標明初態(tài)，默認第一行是初態(tài)。

終態(tài)行在表右端標1，非終態(tài)標029例如：DFAM=({0，1，2，3}，{a，b}，f，0，{3})，其中：f定義如下：f(0，a)=1 f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1 f(2，b)=3f(3，a)=3 f(3，b)=3狀態(tài)轉換矩陣30例：－＋baSZa,b表示：f(S,a)=Zf(S,b)=Zf(Z,a)=Zf(Z,b)=ZabSZZZZZ01寫成正規(guī)式是：(a|b)(a|b)*31Ch2形式語言自動機理論基礎2.2自動機基礎2.2.1確定的FA（DFA）電梯控制的狀態(tài)矩陣表示上1下1上2下2上3下3S1*S1S2*S3*

S1S1 S1S2S2S2 S2

S3 S3S3S3323、DFA接受（識別）的概念：

對于Σ*中的任何字符串t，若存在一條初態(tài)到某一終態(tài)的路，且這條路上所有弧的標記符連接成的字符串等于t，則稱t可為DFAM所接受。

若M的初態(tài)同時又是終態(tài)，則空字可為M所接受。33②

輸入字符串t（t表示成Tt1形式，TΣ，t1Σ*），在DFAM上運行的定義為：f（Q，Tt1）=f(f(Q,T),t1)，其中QK。4、接受（識別）的理解：①

設QK，函數f(Q,)=Q，則輸入字符串是空串，并停留在原狀態(tài)上。

34例：證明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,baa35DFA的確定性表現在：對任何狀態(tài)s∈S，在讀入了輸入符號a∈Σ之后，能夠唯一地確定下一個狀態(tài)映射函數δ：S×Σ→S是一個單值函數從狀態(tài)轉換圖來看，若字母表Σ含有n個輸入字符，那末任何一個狀態(tài)結點最多有n條弧射出，而且每條弧以一個不同的輸入字符標記。36③DFAM所能接受的字符串的全體記為L（M）—稱為語言（也即句子的集合）結論：上一個符號串集V是正規(guī)的，當且僅當存在一個上的確定有窮自動機M，使得V=L(M)文法是語言的生成系統，是從產生的觀點來描述語言的。自動機是語言的識別系統，是從識別的觀點來描述語言的文法和自動機的對比37四、不確定的有窮自動機NFA一個不確定的有窮自動機NFA

M是一個五元組：M=（Q，Σ，f，q0，Z），其中：①Q是一個有窮集，每個元素表示一個狀態(tài)；②Σ是一個有窮字母表，每個元素是一個輸入字符；③f是一個從Q×(Σ∪ε)到2Q的映象；

④q0是初態(tài)，q0Q

；⑤ZQ，是一個終態(tài)集?！疽c】至少一個初態(tài)，若干個終態(tài)。38DFA和NFA的主要區(qū)別為：（1）DFA任何狀態(tài)都沒有ε轉換，即沒有任何狀態(tài)可以不進行輸入符號的匹配就直接進入下一個狀態(tài)；（2）DFA對任何狀態(tài)S和任何輸入符號a，最多只有一條標記為a的邊離開S，即轉換函數δ：S

ΣS是一個單值部分函數。39例子NFAM=（{S，P，Z}，{0，1}，f，{S，P}，{Z}）其中f（S，0）={P}f（Z，0）={P}f（P，1）={Z}f（Z，1）={P}f（S，1）={S，Z}狀態(tài)圖表示SPZ00,1111∑*上的符號串t被NFAM接受若t∑*，f(S0，t)=P，其中S0∈S，PZ，則稱t為NFAM所接受（識別）40Ch2形式語言自動機理論基礎2.2自動機基礎2.2.2非確定的FA(NFA)例2.24:給出一個接收字符串aa*|bb*的NFAM， 如下圖所示。

對字符串aaa的接受路徑為0，1，2，2，2，接受 路徑中邊的標記是ε，a，a，a，它們的連接為字符串aaa，ε在連接中消失。εεabastart04132a41∑*上的符號串t被NFAM接受（識別）:對于Σ*中的任何一個串t，若存在一條從某一初態(tài)結點到某一終態(tài)結點的通路，且這條通路上所有弧的標記字依序連接成的串(不理采那些標記為ε的弧)等于t，則稱t可為NFAM所識別(讀出或接受)。若M的某些結點既是初態(tài)結點又是終態(tài)結點；或者存在一條從某個初態(tài)結點到某個終態(tài)結點的道路,其上所有弧的標記均為ε，那么空字ε可為M所接受。42使用NFA判定某個輸入符號串的時候，可能出現不確定的情況：不知道下面選擇那個狀態(tài)。如果選擇不好，該輸入符號串可能不能到達終止狀態(tài)。但是，我們不能說該輸入符號串不能被該NFA接受。如果通過嘗試的方法，不斷試探來確定輸入符號串是否可被接受，那么判定的效率將降低。解決的方法是將NFA轉換為等價的DFA。NFAM所能接受的符號串的全體記為L(M)結論：上一個符號串集V是正規(guī)的，當且僅當存在一個上的不確定的有窮自動機M，使得V=L(M)。43定理：設L為一個由不確定的有窮自動機接受的集合，則存在一個接受L的確定的有窮自動機。將NFA轉換成接受同樣語言的DFA，這種算法稱為子集法。NFA與DFA的等價性：對于每個NFAM存在一個DFAM’，使L(M)=L(M’)。NFA可以利用子集法進行確定化，對于一個NFAM總可以構造一個等價的DFAM’。NFA到DFA構造基本思路：DFA的每一個狀態(tài)對于NFA的一組狀態(tài)。DFA利用它的一個狀態(tài)去記錄在NFA讀入一個輸入符號后可能到達的所有狀態(tài)。五、NFA轉換為等價的DFA（NFA確定化）444546-closure(I)=-closure({1})={1，2}=IJ={5，4，3}Ia=-closure(J)=-closure({5，4，3})={5，4，3，6，2，7，8}61a234578aa設a是中的一個字符，定義Ia=-closure(J)其中，J為I中的某個狀態(tài)出發(fā)經過一條a弧而到達的狀態(tài)集合。47把確定化的過程:不失一般性，設字母表只包含兩個a和b，我們構造一張表:48首先，置第1行第1列為-closure({X})求出這一列的Ia，Ib；然后，檢查這兩個Ia，Ib，看它們是否已在表中的第一列中出現，把未曾出現的填入后面的空行的第1列上，求出每行第2，3列上的集合...重復上述過程，知道所有第2，3列子集全部出現在第一列為止。49IIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,2,3,1,6,Y}{5,4,1}{5,4,1}{5,3,1}{5,2,4,1,6,Y}{5,2,3,1,6,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}{5,4,6,1,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}XY514236abababab50現在把這張表看成一個狀態(tài)轉換矩陣，把其中的每個子集看成一個狀態(tài)。這張表唯一刻劃了一個確定的有限自動機M，它的初態(tài)是-closure({X})，它的終態(tài)是含有原終態(tài)Y的子集。不難看出，這個DFAM與M’等價。51Iab0121322143*344*655*656*340123546aabbbabaababab52Ch2形式語言自動機理論基礎2.2自動機基礎2.2.3NFA確定化

綜述—求Ia步驟：

(1)求ε-closure(I)；

(2)求J；

(3)求ε-closure(J)；NFA確定化關鍵：(1)消去ε弧；(2)解決映射不唯一問題。ε-closure(I)

求Ia53Ch2形式語言自動機理論基礎2.2自動機基礎2.2.3NFA確定化例2:有NFAM’如下圖所示。12385467aaaεεε

εε54Ch2形式語言自動機理論基礎2.2自動機基礎2.2.3NFA確定化IIa{2,3,4,5,6,7,8}{3,8}Φ120ε-closure(S0)={1,2}1*2*{2,3,4,5,6,7,8}{3,8}555657六、確定有窮自動機DFA的化簡（DFA最小化）說一個有窮自動機是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的。一個有窮自動機可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉換成一個最小的與之等價的有窮自動機。將多余狀態(tài)消除而形成一個最小的等價的DFA?；啿粌H是去除死狀態(tài)，不可能到達狀態(tài)，還包括狀態(tài)的合并。

DFA的最小化就是尋求最小狀態(tài)DFA581、多余狀態(tài)的概念：所謂有窮自動機的多余狀態(tài)，是指這樣的狀態(tài)：從自動機的開始狀態(tài)出發(fā)，任何輸入串也不能到達的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達終態(tài)。如下圖中的S4狀態(tài)是多余的。在圖中，沒有一個狀態(tài)能到達S4。當S4是多余時，又可以推出S6是多余的。同樣也可以推出S8也是多余的。

最小狀態(tài)DFA的含義:1.沒有多余狀態(tài)(死狀態(tài))2.沒有兩個狀態(tài)是互相等價（不可區(qū)別）5901S0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6S8S01S7S0S11S8S3S6001S0S1S50S1S2S71S2S2S51S3S5S70S5S3S10S7S0S11化簡后的結果：左右等價602、等價的條件（狀態(tài)S和T）

兩個狀態(tài)s和t等價：滿足一致性——同是終態(tài)或同是非終態(tài)蔓延性——從S出發(fā)讀入所有aa和從T出發(fā)讀入a到達的狀態(tài)等價。613、等價的方法（分割法）方法：將DFA的狀態(tài)分割成一些互不相交的子集。把一個DFA（不含多余狀態(tài)）的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的。分割法的核心把DFA的全部狀態(tài)劃分成一些互不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的（不等價），而同一子集中的任何兩個狀態(tài)都是等價的.62DFA化簡（最小化方法）算法：所有狀態(tài)分成兩個子集——終態(tài)集和非終態(tài)集；運用判定狀態(tài)等價的原則分別對兩個子集的狀態(tài)進行分析和劃分，若發(fā)現某個狀態(tài)與其它狀態(tài)不等價，則將其作為一個新的狀態(tài)子集，如果無法區(qū)分，則放在同一子集中；從每個子集中選出一個狀態(tài)做代表，即可構成簡化的DFA；含有原來初態(tài)的子集仍為初態(tài)，各終態(tài)的子集仍為終態(tài)。63Ch2形式語言自動機理論基礎2.2自動機基礎2.2.4DFA的化簡Step1:形成基本劃分。劃分為終態(tài)集和非終態(tài)集。

P0=（{0,1},{2}）考察：{0,1}a={1}?{0,1} {0,1}b={2}?{2}a例1：設確定有限自動機DFAM'，如圖所示。

bbaa021Step2:重新命名。令{0,1}為0，令{2}為1?；緞澐?/p>

不可對{0,1}再分64Ch2形式語言自動機理論基礎2.2自動機基礎2.2.4DFA的化簡baa10化簡后的DFAM65CBASaaabbbba,CDBAEFSbaaaaaabbbbbba例2：化簡下圖的DFA661643257aaaaaaabbbbbbb例3：將下圖中的DFAM最小化。67Ch2形式語言自動機理論基礎2.2自動機基礎2.2.4DFA的化簡第一步，對M的狀態(tài)形成基本劃分：設p０是基本劃分。將p０分成q１,q2，即

p０=({1,2,3,4},{5,6,7})=(q1,q2)第二步，對q１,q2考察知：對p０的q１，I=1時Ia={6} I=2時Ia={7} I=3時Ia={1} I=4時Ia={4}Ib={3} Ib={3} Ib={5} Ib={6}68Ch2形式語言自動機理論基礎2.2自動機基礎2.2.4DFA的化簡對q1形成新的劃分：

q1=(q3,q4)=（{1,2}，{3,4}） 對p０的q2，I=5時Ia={7}Ib={3} I=6時Ia={4}Ib={1} I=7時Ia={4}Ib={2}

在輸入a或b的情況下，q2中的狀態(tài){5}與狀態(tài){6,7}是不等價的，構成q2新的劃分：69Ch2形式語言自動機理論基礎2.2自動機基礎2.2.4DFA的化簡q2新的劃分：

q2=(q5,q6)=（{5}，{6,7}）由此，對基本劃分p0經考察且劃分后，形成新的劃分p1：

p1=（q3，q4，q5，q6）

=({1,2}，{3,4}，{5}，{6,7})70Ch2形式語言自動機理論基礎2.2自動機基礎2.2.4DFA的化簡

第三步，對新形成的劃分p1重復上述第二 步，則對p1中q4的狀態(tài){3,4}在輸入字符a

的情況下考察其是不等價的，再劃分為

q4=（q7,q8）=（{3},{4}）對劃分p1經考察且劃分后，形成新的劃分p2：

p2=（q3,q5,q6,q7,q8）

=({1,2},{5},{6,7},{3},{4})711643257aaaaaaabbbbbbb16435aaaaabbbbb至此所有狀態(tài)集中的狀態(tài)皆為等價狀態(tài)。72合并狀態(tài)注意：a、由于一個子集中，各狀態(tài)等價，故只需將原進入該子集中各狀態(tài)的弧都改為進入所選的狀態(tài)，子集中各狀態(tài)射出的弧均改為從該狀態(tài)射出。b、含有原來初態(tài)的子集仍為初態(tài)，含原終態(tài)的子集仍為終態(tài)73例4：將下圖中的DFAM最小化。1402357600000000111111741、一個終態(tài)（可接受態(tài)）組成，一個非終態(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表示,簡化后圖如下:751402357600000000111111ADBCE0000011176正規(guī)式和FA之間也可以互相轉換，轉換的方法是從已知的正規(guī)式先構造出等價的ε-NFA（本節(jié)），去掉ε-NFA中的空動作變換為不含ε遷移的NFA，然后再把NFA轉化為DFA，最后再對DFA化簡，求得最小DFA。上述各種轉換關系可用圖2-8表示。七、正規(guī)式和有窮自動機的等價性

77正規(guī)式和有窮自動機的等價性：

※對于Σ上的NFAM，可以構造一個Σ上的正規(guī)式R，使得L(R)=L(M)?！鶎τ讦采系拿總€正規(guī)式R，可以構造一個Σ上的NFAM，使得L(M)=L(R)。78Ch2形式語言自動機理論基礎2.3正規(guī)式與自動機2.3.2正規(guī)式與FA(1)增加結點X，并從X引ε弧到達S0中的所有狀態(tài)；(2)增加結點Y，并從Z中所有狀態(tài)引ε弧到達Y；step1:將NFAM進行拓廣；1、在NFAM上構照正規(guī)式R。即從L(M)L(R）方法：在每一條弧上用一個正規(guī)式作標記。規(guī)則如下：79Y3aXstep2:利用替換規(guī)則一逐步消去M’中的結和弧，并用正規(guī)式代替原來M’中的弧標記，直至只剩下結為止。XY80(1)123R1R213R1R2(2)12R1R221R1|R221R1+R2替換為或(3)321R1R2R331R1R2*R3替換為替換為替換規(guī)則一81Ch2形式語言自動機理論基礎2.3正規(guī)式與自動機2.3.2正規(guī)式與FAY1234bbaa0a,b例1:有NFAM如下圖所示。

a,ba,bεε82Ch2形式語言自動機理論基礎2.3正規(guī)式與自動機2.3.2正規(guī)式與FAY1234bbaa0a,ba,ba,bXεεε83Ch2形式語言自動機理論基礎2.3正規(guī)式與自動機2.3.2正規(guī)式與FAY123baa,b

4Xεε(a|b)*b(a|b)*a

用規(guī)則(3)消去0結和a,b弧

a,b84Ch2形式語言自動機理論基礎2.3正規(guī)式與自動機2.3.2正規(guī)式與FA用規(guī)則(3)消去2,4結和2個a|b弧Y13X(a|b)*b(a|b)*ab(a|b)*a(a|b)*85Ch2形式語言自動機理論基礎2.3正規(guī)式與自動機2.3.2正規(guī)式與FA(a|b)*aa(a|b)*YX用規(guī)則(1)消去1,3結

(a|b)*bb(a|b)*86Ch2形式語言自動機理論基礎2.3正規(guī)式與自動機2.3.2正規(guī)式與FA用規(guī)則(2)消去2個弧

(a|b)*bb(a|b)*|(a|b)*aa(a|b)*

YY

X用分配率實施化簡

(a|b)*(aa|bb)(a|b)*

X正規(guī)式87例2:L(M)如下圖：求正規(guī)式R，使L(R)=L(M).解：－＋aba,baba,bxyya|bxa|byx(a|b)(a|b)*因此：L(R)=(a|b)(a|b)*8803412aabba,ba,ba,b例3：M狀態(tài)圖如下：求正規(guī)式R，是L(R)=L(M).89解：加x,y結點。a,b03412aabba,ba,bxy90042aabba,ba,bxya,ba,b0aa(a|b)*bb(a|b)*xy91y(a|b)*(aa|bb)(a|b)*x所以L(R)=(a|b)*(aa|bb)(a|b)*

例4：L(M)如下圖，求L(R)-++abbaaba,b92解：-++abbaaba,b-abbaaba,bxy93-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)+94例5：L(M)如下圖，求L(R).-+abbbbabbaa,ba解：-+abbbbabbaa,ba95abba|abb|bb+a,b-aa*(abba|abb|bb)(a|b)*+-所以L(R)=a*(abba|abb|bb)(a|b)*注：abba+abb+bb

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

XYXYε98Ch2形式語言自動機理論基礎2.3正規(guī)式與自動機2.3.2正規(guī)式與FAR1R1|R2ABR2AB替換為R1*ABεACεB替換為R1ACR2BR1R2AB替換為

R1替換規(guī)則二(1)⑵⑶99例1：L(R)=(a|b)*abb，構造NFA使L(N)=L(R)解：xy(a|b)*abbxyabba,bxyabbabxyababb100例：L(R)=(a|b)*(aa|bb)(a|b)*構造L(M)使與L(R)等價。101xy(a+b)*(aa+bb)(a+b)*xy(a+b)*aa+bb(a+b)*xyaabba,ba,b102xyabaaabbb103八、正規(guī)文法和有窮自動機的等價性采用下面的規(guī)則可以從正規(guī)文法G直接構造一個有窮自動機NFAM；使得L（M）＝L（G）：M的字母表與G的終結符集相同為G中的每個非終結符生成M的一個狀態(tài)，G的開始符S是開始狀態(tài)S增加一個新狀態(tài)Z，作為NFA的終態(tài)對G中的形如A→tB的規(guī)則（其中t為終結符或?，A和B為非終結符的產生式），構造M的一個轉換函數f(A,t)=B對G中形如A→t的產生式，構造M的一個轉換函數f(A,t)=Z104

[例2-6]已知正規(guī)文法G3＝({S，A，B}，{a，b，c}，P，S)，其中P內包含以下產生式：根據上述轉換方法，與G3等價的FAM為：其中δ函數的定義式為：105例2：與文法G［S］等價的NFAM如圖4.11G[S]:S→aAS→bBS→ε

A→aBA→bAB→aSB→bAB→ε106有窮自動機轉換成等價的正規(guī)文法：對轉換函數f(A,t)=B,可寫一產生式：A→

tB對可接受狀態(tài)Z，增加一產生式：Z→

ε有窮自動機的初態(tài)對應文法開始符有窮自動機的字母表為文法的終結符集107例3：給出與圖4.12的NFA等價的正規(guī)文法GG＝（｛A，B，C，D｝，｛a，b}，P，A），其中P為：A→aBC→

εA→

bD

D→

aBB→

bC

D→

bDC→

aA

D→

εC→

bD108本章小結