1、第三章 有窮自動機,要點： 1. DFA和NFA的定義 2. NFADFA的轉換； 3. DFA的化簡 4. 正規文法、正規式、有窮自動機之間的相互轉換；,編譯原理,有窮自動機,有窮自動機（或有限自動機）作為一種識別工具，它能正確地識別正規集，即識別正規文法所定義的語言和正規式所表示的集合。引入有窮自動機這個理論，正是為詞法分析程序的自動構造尋找特殊的方法和工具。 分類：確定的有窮自動機（DFA） 不確定的有窮自動機（NFA）,3.1 概述 有窮自動機（FA）,有窮自動機（FA，Finite Automata）是一種有限離散數字系統的抽象數學模型。 這個系統具有有限數目的內部“狀態”。 所謂狀

2、態，是可以將事物區分開的一種標識。例如：數字電路（0，1），十字路口的紅綠燈等都是離散狀態系統，其狀態數目是有限的。連續狀態系統則如水庫的水位、室內溫度變化等。 電梯的控制機制，不需要保存所有以前的服務要求，僅需記住當前的層次、運動的方向以及未滿足的服務要求。 文本編輯程序和詞法分析程序是有限狀態系統，計算機本身和人的大腦也可看成有限狀態系統。,例 過河問題 題目,一個人帶著一頭狼、一頭羊以及一棵青菜，處于河的左岸，需要渡到河的右岸。有一條小船，每次只能攜帶人和其余的三者之一。不能讓狼和羊單獨在一起，無論在左岸還是右岸，否則狼會吃掉羊。同樣，也不能讓羊和青菜單獨一起。 如何才能安全渡過河呢？,

3、例 過河問題 分析,觀察每次擺渡后河兩岸的局勢，使問題模型化。 人（M），狼（W），羊（G），菜（C）。存在有16種子集，用連字號”-”連接子集的對偶表示狀態，例如： MG-WC，表示：人和羊在左岸，狼和菜在右岸。 16種狀態中的某些狀態，是不應該引入系統的，例如GC-MW，有關死活。 人所進行的擺渡活動，可作為系統的輸入。人可單獨過河（輸入為M），帶著狼過河（輸入為W），帶著羊過河（輸入為G）或者是帶著菜過河（輸入為C）。 問題：初始狀態應該是什么？終止狀態應該是什么？,例 過河問題 分析（續）,初始狀態：MWGC-；終止狀態：-MWGC。,MWGC-,WC-MG,g,問題：,例 過河問題

4、狀態轉換圖,MWGC-,WC-MG,C-MWG,MWG-C,MGC-W,G-MWC,MG-WC,-MWGC,W-MGC,MWC-G,g,g,g,g,m,g,g,g,g,m,m,m,c,c,c,c,w,w,w,w,起始,有窮自動機（FA）,數字系統：可以從一個狀態移動到另一個狀態；每次狀態轉換，都上由當前狀態及一組輸入符號確定的；可以輸出某些離散的值集。 FA：一個狀態集合；狀態間的轉換規則；通過讀頭來掃描的一個輸入符號串。 讀頭：從左到右掃描符號串。移動（掃描）是由狀態轉換規則來決定的。,d,d,d,;,.,d,d,+,;,輸入符號串,一個FA的例子,讀頭,數字,接收：若掃描完輸入串，且在一個

5、終止狀態上結束。 阻塞：若掃描結束但未停止在終止狀態上；或者為能掃描完輸入串（如遇不合法符號）。 不完全描述：某些狀態對于某些輸入符號不存在轉換。,練習：+34.567 .123 3.4.5,=,8,0,;,0,1,3,4,2,5,6,e,n,i,L,字母,字母,字母,字母,數字,數字,數字,=,=,；,；,0,1,2,4,5,6,3,L,i,n,e,=,8,0,;, id , Line, = , , num, 80, ;, ,數字,數字,字母,字母,1,1,=,=,0,0,0,3,;,;,1,輸入符號串,輸出,有限控制器,讀頭,3.2 有窮自動機的形式定義,DFA: Deterministi

6、c Finite Automata NFA: Nondeterministic Finite Automata DFA的定義 定義3.1 一個確定的有窮自動機(DFA) M是一個五元組： M = ( K, , f, S, Z ) (1)K是一個非空有窮集合，它的每一個元素稱為一個狀態； (2)是一個有窮字母表，它的每一個元素稱為一個輸入字符； 也稱為輸入符號字母表,確定的有窮自動機DFA的定義（續）,(3) f是從K到K的單值部分映射； f(ki,a)=kj， 其中kiK，kjK 說明：當前狀態為ki ，輸入字符a時，將轉換到下一個狀態kj ，把kj稱為ki的一個后繼狀態。 DFA的確定性就表

7、現在f是單值函數，即對任意狀態kK，輸入符號a，f(k,a)唯一確定一個狀態。 (4)SK，是唯一的初態； (5)Z是K的子集，是一個終態集，終態也稱為可接收狀態或結束狀態。,確定的有窮自動機DFA的表示,3.2.1 狀態轉換圖 設DFA有m個狀態，n個輸入字符，那么這個圖含有m個狀態結，每個結點最多有n條箭弧射出和別的結點相連接，每條弧用中的一個不同輸入符號作記號。整個圖含有唯一的一個初態和若干個（可以0個）終態結。 習慣上，初態結可以用“=”或“”表示，終態結用雙圓圈表示或標以“+”。對f(ki,a)=kj指從狀態結ki到狀態結kj畫標記a的弧。,例,題：DFA M=(0, 1, 2, 3

8、，a, b，f，0，3)，其中f定義為： 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 解：該DFA M的狀態圖：,確定的有窮自動機DFA的表示（續）,3.2.2 狀態轉換矩陣 矩陣的行表示狀態，列表示輸入字符，矩陣元素表示相應的狀態行在輸入字符列下的新的狀態，即f(k,a)的值。,例（題同）,解：該DFA M的矩陣表示,0 0 0 1,3.2.3 有關自動機術語,(1)道路：對于*中的任何字，若存在一條從初態到某終態的路徑。 (2)識別：道路上所有弧的標記連接成的字等于，則稱可為D

9、FA M所識別（所接受）。 即若t*, f(S,t)=P，其中S為DFA M的初始狀態，PZ（終態集）。 若M的初態結同時也是終態結，則空字可為M所識別，即QK, f(Q, )=Q (3)運行： f(Q, t1t2) = f(f(Q, t1), t2)，其中QK， t1t2為輸入字符串，且t1 ，t1t2 *,例,解：f(0, abba) = f(f(0,a), bba)= f(1, bba) = f( f(1,b), ba) = f(2, ba) = f(f(2,b), a) = f(3, a) = 3 得證,題：試證abba可為例1的DFA M所識別（所接受）。,3.2.4 有關確定有窮自

10、動機的結論,把DFA M所能接受的所有字（字的全體）記為L(M)。 上的一個字集V*是正規的，當且僅當存在一個上的確定有窮自動機M，使得L(M)=V。,有限自動機識別的語言 例子,例：下圖中的自動機所能識別的語言是什么？,q0,q2,q1,q3,a,b,b,a,b,a,定義3.4 一個不確定的有窮自動機NFA N也是一個五元組： M = ( K, , f, S, Z ) (1)K是一個有窮集合，它的每一個元素稱為一個狀態； (2)是一個有窮字母表，它的每一個元素稱為一個輸入字符； 也稱為輸入符號字母表 (3) f是一個K*到K的子集的映射： f : K*2k (4)S是K的子集，是非空的初態集

11、； (5)Z是K的子集，是一個終態集，也稱可接收狀態或結束狀態。,3.2.5 不確定的有窮自動機(NFA)的定義,NFA的表示,用狀態轉換圖（ f是多值函數） 由NFA的定義，可把一個含有m個狀態和n個輸入字符的NFA表示如下： 圖中有m個狀態結，對每個狀態結可射出若干條弧和別的狀態結相連，且每條弧用*中的一個字（不一定要不同的字且可以是空字）作標記（或稱輸入字）。整個圖中至少含有一個初態結以及若干個（可以是0個）終態結。 某些結既可以是初態結也可以是終態結。,例,題：一個NFA M(s, t，0, 1，f，s，t)，其中 f(s, 0)=s, t, f(s, 1)=t, f(t, 0)=,

12、f(t, 1)=s, t,解：其狀態圖如下：,例,如下狀態圖也是一個NFA,有關非確定有窮自動機的術語,對于*中的任何一個串t可被NFA M識別是指：若對這個字（串）t存在一條從某個初態結到某一個終態結的道路，且這條道路上所有弧的標記字依序連接起來的字（不理睬那些標記為的弧）等于t，則t可識別（或可接受） 若M的某些結點既是初態結也是終態結，或存在一條從某個初態結到某個終態結的道路，則空字可為M所識別（所接受）。,補充：遞歸思想構造文法,在某些復雜的語言中，字符串可能包含一種結構，它遞歸地作為另一種（或者同一種）結構的一部分而出現，可利用遞歸思想來構造對應的文法。 例1：定義語言L=| 中a和

13、b的個數相同的文法。 解：先構造出基礎情況的文法： S- ab | ba | 再遞歸地構造出歸納情況的文法（新的生成式不能改變a和b的個數關系）： S- Sab | aSb | abS | Sba | bSa | baS,遞歸思想構造文法 （續）,例1：求一個文法G，使得(G)即該文法的語言是奇數個和奇數個的組合。 解：因為語言是奇數個和奇數個的組合，所以打頭的最小語言有四種組合： aa bb ab ba 定義S和A，S是表示奇數個 a和奇數個b的組合，而A是表示偶數個a和偶數個b的組合。 開始遞歸構造文法： S-aaS | bbS | abA | baA A-aaA | bbA | abS

14、| baS | ,補充：如何設計有限自動機,如同文法的設計，自動機的設計也是一個創造過程。有一種做法，在設計各種類型的自動機時都很有幫助，即采用一種心理上的技巧，把自己放在要設計的機器的位置上，考慮自己該如何實現自動機的任務。 假定自己是一臺有限自動機，接受到一個輸入符號串時，必須確定到目前為止所看到的字符串是否可為該自動機所識別。為了能夠判斷這一點，必須估算出識別時需要記住哪些關鍵的東西。 為什么不記住所有看到的東西呢？因為你是一臺有限自動機，只有有限個狀態，而這些狀態是你記住事情的唯一辦法。輸入串可能很長，而你不可能記住所有的事情。 幸運的是，許多語言只需要記住某些關鍵的信息就可以了。,設

15、計有限自動機（續1）,例1：構造一臺有限自動機，識別所有由奇數個a和奇數個b組成的字符串。,解：為了確定a和b的個數是否是奇數，不需要記住所看到的整個字符串，而只需要記住至此所看到的a、b個數是偶數還是奇數即可。一旦確定了關鍵信息，就可以開始設計狀態了。 這些信息有如下四種可能性：,設計有限自動機（續2）,例1：(1)到此為止是偶數個a和偶數個b; (2)到此為止是奇數個a和偶數個b; (3)到此為止是偶數個a和奇數個b; (4)到此為止是奇數個a和奇數個b。 根據每種可能性設計一個狀態，并根據可能的輸入符號來設計狀態之間的轉移條件。,設計有限自動機（續3）,例2：設計有限自動機M，識別含有0

16、0作為子串的所有0，1*上的字符串組成的語言。 如：0010，1001，110001001,解：3種可能性： (1)到此為止未看到模式“00”的任何符號; (2)到此為止看見了一個0; (3)到此為止已經看見整個模式“00”。,設計有限自動機（續4）,例2自動機的狀態轉換圖為：,或者為（NFA）：,設計有限自動機（續5）,例3 構造一個有窮自動機M，識別所有形如0k的字符串，其中k是2或3的倍數。,（2）識別0k的字符串，其中k是3的倍數：,（1）識別0k的字符串，其中k是2的倍數：,設計有限自動機（續6）,例3 的有窮自動機M為：,以上兩個自動機是否等價？,這個自動機顯示了轉換的方便之處。,

17、設計有限自動機（續7）,1.思考題： 構造一個有窮自動機M，識別0，1，2上的語言，該語言的每個字符串代表的十進制數能被3整除。 如：102，1020，10201，110,2.編程題：根據有窮自動機M，編寫程序，識別所有由奇數個a和奇數個b組成的字符串。,(1)用戶輸入：ab組成的符號串； (2)一個字符一個字符地讀、分析； (3)不要使用計數器。,設計有限自動機（續8）,1.思考題： 構造一個有窮自動機M，識別0，1，2上的語言，該語言的每個字符串代表的十進制數能被3整除。 如：102，1020，10201，110,思路(1) :所有位數之和； (2): q0: 3n+0 q1: 3n+1

18、q2: 3n+2 q0+1-q1，因 (3n+0)*10+1)/3余1； q1+1-q2，因 (3n+1)*10+1)/3余2； .,NFA和DFA的關系,DFA是NFA的一個特例。 對于每個NFA M，存在一個DFA M，使得L(M)=L(M) 對于任何兩個有窮自動機M和M，如L(M)=L(M)則稱M和M是等價的。 如果M僅通過重新標記它的狀態，就能轉換成M，則M和M稱為同構的。 對于每一個FA M，存在一個等價的、具有最少狀態個數的FA M，對于其它的FA M，若M的狀態個數與M相同且等價與M，則必然有M與M同構，即：M在結構上是唯一的。,3.3 NFA DFA的轉換（NFA的確定化）,通

19、過以下步驟，可以將一個NFA轉換為等價的DFA： 1.尋找并消除空移環路； 2.消除余下的空移； 3.確定化。,3.3.1 NFA中空移環路的尋找和消除,空移環路： 一個空移環路，是一個從狀態A開始，并以狀態A結束的空移動序列。,消除方法： 合并環路上的結點為新結點。 若含初態，則新結點為初態。 若含終態，則新結點為終態。 課本P56 例3.4,3.3.2 NFA的消除空移,A,B,a1,q1,q2,qn,a2,an,a1,a2,an,消除方法： 刪除弧，產生新弧。 若A為初態，則B結點也為初態。 若B為終態，則A結點也為終態。,3.3.4 NFA的確定化子集法,添加一個例子( 無空移) 介紹

20、一種稱子集法的算法來將NFA轉換成接收同樣語言的DFA。 算法的基本思想是：把DFA中的每一個狀態對應NFA中的一組狀態。即由于NFA中的f是多值的，所以在讀入一個輸入符號后可能達到的狀態是集合，而子集法就是用DFA的狀態記錄該狀態的集合。,確定化的有關運算,（2）Move(I, a)狀態集合I的a弧轉換 假定I是狀態集的一個子集，a是中的一個字符，定義 Ia _closure(J) 其中J是所有那些可從I中的某一狀態出發經過一條a弧而到達的狀態結的全體。 (3)Ia _closure(Move(I, a),（1）_closure(I) 狀態集合I的閉包(等價狀態集) 設I是狀態集的一個子集，

21、 _closure(I)定義為： a. 若SI，則S _closure(I)； b. 若SI，那么從S出發經過任意弧而能到達的任意狀態S都屬于_closure(I)；,題：有一個狀態圖如下：,假定 I= _closure(1)1, 2 從狀態集I出發經過一條a弧而能到達的狀態結全體J為5, 3, 4； 而_closure(J) =5, 6, 2, 3, 8, 4, 7,例,NFA的確定化,從NFA N (K, , f, K0, Kt)構造一個DFA M (S, , D, S0, St)，其中 (1) S是由K一些子集組成； (2) M與N的輸入字母表相同，都是； (3)D定義： D(S1, S

22、2, Sj, a)=R1, R2, Ri，其中 _closure(move(S1, S2, Sj, a)= R1, R2, Ri (4) S0 = _closure(K0)為M的開始符號（初態）； (5) St =Sj, Sk, Se，其中Sj, Sk, Se S且Sj, Sk, SeKt ,子集化的具體過程,為了方便起見，令中只有a,b兩個字母，即a, b （1）構造一張表，此表的每一行有三列，第一列為I，第二列為Ia，第二列為Ib。即,首先置該表的第一列為_closure(K0)。,（2）一般而言，若某一行的第一列的狀態子集已確定，例如記為I，則可以求出Ia和Ib ；,子集化的具體過程（續

23、）,（3）檢查Ia和Ib是否已在表的第一列中出現，把未曾出現者填入到后面空行的第一列位置上。 （4）對未重復Ia 、 Ib的新行重復上述過程(2)、(3) ，直到所有第二列和第三列的子集全部在第一列中出現；,上述過程必定在有限步內終止，因為N的狀態子集的個數是有限的。我們也可將表看成狀態轉換矩陣，即把其中每個子集看成一個狀態，就可以由這張表唯一刻劃出一個確定的有窮自動機DFA。其初態就是該表的第一行第一列的_closure(K0) ，終態就是那些含有的Kt子集。,例,題：將下圖NFA N確定化。,解：(1)構造轉換矩陣,接上頁,(2)對表中所有的子集重新命名，其中0是初態，4是終態。 對應的D

24、FA M：,例,題：將下圖確定化：,解：(1)構造轉換矩陣,接上頁, DFA M為：,3.3.6 消除不可達狀態,有窮自動機的多余狀態：是指這樣的狀態，從該自動機的開始狀態出發，任何輸入串也不能達到的那個狀態。,3.3.7 DFA的化簡,對已求得的DFA，可以進一步將其化簡，即求最小DFA。也就是對于任意給定的DFA M構造另一個DFA M，使L(M)=L(M)，且DFA M的狀態個數少于DFA M的狀態個數。 消除多余狀態 DFA M狀態最少化的過程： 把M的狀態集分割成一些不相交的子集，使得任何不同的兩個子集的狀態都是可區別的，而同一子集中的任何兩個狀態都是等價的。,有關分割法所用的概念,

25、定義3.8 等價 設s,t是M的兩個不同的狀態，s,t等價的意思是：如果從狀態s出發能讀出某個字而停于終態，那么同樣從t出發也能讀出同一個字而停于終態；反之，若能從t出發讀出某個字而停于終態，那么同樣從s出發也能讀出字而停于終態。,等價的條件： (1)一致性條件 狀態t,s必須同時是可接受狀態或不可接受狀態； (2)蔓延性條件 對于所有輸入符號，狀態s和狀態t必須轉換到等價的狀態里(注：狀態s對應有輸入a而狀態t無輸入a時，這兩個狀態是不等價的）。,有關分割法所用的概念,定義3.9 可區分 若DFA M中的兩個狀態s,t不等價，則這兩個狀態是可區別的。 例如：終態和非終態是可區別的（讀出）；

26、下圖中的狀態2與狀態3（讀出b字）；,分割法,(1)把K的終態和非終態分開，分成兩個子集 終態組和非終態組，形成基本分劃；顯然，屬于這兩個不同子集的狀態是可區別的。 (2)假定到某個時候含有m個子集，記=I(1), I(2), , I(m)，若存在一個輸入字符a使得Ia( i )不全包含在現行的某個子集I( j )中，就將I( j )一分為二；至此把I( i )分成兩半，形成新的劃分 new。,分割法（續）,(3)重復上述過程(2)，直到所含的子集不再增長為止，此時得到最后的劃分 finish； 此時， 中的所有子集已是不可再分的了。也就是說，同個子集中的狀態都是互相等價的，而不同子集中的狀態

27、則是可區別的。 (4)對于 finish中的每一個子集，選取子集中的一個狀態代表其它狀態，這個代表就是化簡了的DFA M的狀態。 例如：假定I=S1, S2, S3這樣一個子集，則可選S1代表這個子集，那么在原自動機中，凡導入到S2, S3的弧都導入到S1,然后把S2, S3結點從原來的狀態集合中刪除，因為它們已成了一些多余的狀態（從開始狀態出發，任何輸入串也不能達到的狀態）。,對劃分的說明,例如：假定I( i )中的狀態S1和S2經a弧分別到達狀態t1和t2，而t1和t2屬于現行中的兩個不同子集，則將一分為二，使得一半含有S1 ： I( i1 ) =S | S I( i1 )且S經a弧到達t

28、1，則另一半含有S2 ： I( i2 ) = I( i ) I( i1); 由于t1和t2是可區別的，即存在一個字， t1將讀出而停于終態，而t2或讀不出字或雖可讀出字但不到達終態，或情況恰好相反。因而字將S1和S2區別開來，也就是說， I( i1 )和I( i2 )中的狀態是可區別,若I中含有原來的初態，則S1是新初態；若含有原來的終態，則S1是新終態。 經過消除多余狀態和合并等價狀態而得到的DFA M，便是最簡化的（包含最少狀態的）DFA。,化簡后初態和終態的確定,例：化簡下圖中的DFA,解：(1)把M的狀態分成兩組：1,2,3,4、5,6,7；,例：DFA化簡,(2)考察5,6,7，由于

29、5,6,7a=4,7，因此對5,6,7一分為二：5、6,7；,(3) 考察1,2,3,4，由于1,2,3,4a=1,4,6,7，因此對1,2,3,4一分為二：1,2、3,4；,(4)考察3,4，由于3,4a=1,4，因此將3,4一分為二：3、4；,至此，整個劃分為：1,2、3 、4 、5 、6,7。用1，3，4，5，6分別來代替子集1,2、3 、4 、5 、6,7 化簡了的DFA M為：,例：化簡后的DFA,化簡后的DFA,例,思考題：將下列DFA M最小化。,解：整個劃分為：0,2、1 、3、4,0,1,2,34 b:0,2,1,3,4,例,將下圖DFA最小化。,解：(1)把M的狀態分成兩組

30、：終結組C、非終結組A,B,D； (2)考慮A,B,D，由于A,B,D1=A,C，因此對A,B,D一分為二，分成A、B,D,例(續),至此，整個集合含有三組：A、B,D、C。 最后，令狀態B代表B,D，將原來導入到D的弧都導入到B，并刪除D。這樣，所得的化簡DFA M為：,原因：B,D0 時B無出邊，D有出邊，不滿足蔓延性條件 正確的劃分：A、B、C、D,例,化簡如下DFA M,解：整個劃分為：0,1、2,5、3、4,7、6，用0,1,2,3,4分布代替子集0,1、2,5、3、4,7、6,3.4 正規文法和有窮自動機間的轉換,3.4.1 (1)正規文法GNFA M： 構造規則： (a) 與G中

31、的VT相同； (b) M中的K與G中的VN相同，即文法G中的每個非終結符生成自動機M中的一個狀態，G的開始符號S是M的初態；增加一個新的狀態Z，作為接受狀態。 (c) 對產生式AtB，其中t VT或，A,BVN，構造M的一個轉換函數f(A,t)=B； (d) 對產生式At，構造M的轉換函數f(A,t)=Z（終態集）。,正規文法GNFA M 例1 課本P73,構造正規文法GS等價的NFA M。 GS: S+N S-N Sd N Sd NdN Nd,解：與文法G等價的NFA M如下圖：,正規文法GNFA M 例2,構造正規文法GS等價的NFA M。 GS: SaA SbB Sb AaB AbA B

32、aS BbA B,解：與文法G等價的NFA M如下圖：,3.4.1 左線性文法-NFA M,轉換規則： (a) 文法的開始符號S是M的終態。 (b) 引入一個新的非終結符R作為初態結點。 (c) 對于文法中的每一個形如A-a的產生式，從初態結點畫一條弧到結點A，且用a標記該弧線。 (d) 對于文法中的每一個形如A-Ba的產生式，從結點B畫一條弧到結點A，且用a標記該弧線。,3.4.1 左線性文法-NFA M,例：GS: S-S1 S-A1 A-A0 A-0,3.4.2 NFA M 正規文法G,轉換規則： (a) 對轉換函數f(A,t)=B，寫成產生式AtB； (b) 對終態Z，增加產生式Z；

33、(c) VN為NFA所有狀態中的標記（K），VT為NFA的， NFA的初態就是開始符號S。,例,例：給出與NFA等價的正規文法G,解：與NFA等價正規文法G=(VN, VT, P, S)=(A,B,C,D,a,b, P, A)，其中P為： AaB AbD BbC CaA CbD C DaB DbD D ,3.5 正規表達式與FA,單詞的描述工具：正規文法 正規文法（3型文法）的形式定義 設G=( VN, VT, P, S)為一文法，若G的任何產生式A 或A B ，其中A、B VN ， VT* 。,正規文法的例子,例：“無符號實數”定義 d | . | e d | . | e | d e | d

34、 | d | s d d | 其中s 正負符號+、,3.5.1 單詞的描述工具正規式的定義,正規式也叫正則表達式，用于描述稱為正規集的語言。 定義3.10 字母表上的正規式和正規集的遞歸定義為： (1)和是上的正規式，它們所代表的正規集為 ()； (2)任何a，a是上的一個正規式，它所表示的正規集為a； (3)假定e1與e2都是上的正規式，它們所表示的正規集為L(e1)和L(e2)，那么(e1)、 e1| e2、 e1 e2和e1*也是正規式，它們所表示的正規集分別為 L(e1)、L(e1)L(e2)、 L(e1) L(e2)、 (L(e1) * (4)僅用有限次使用上述三步驟而定義的表達式方

35、是上的正規式，僅有這些正規式所表示的字集才是上的正規集。,正規式運算符優先關系,|(或) (連接) *(閉包) *、|都滿足左結合 注：連接號可省略,例：正規式,例2,令=l, d, ., e, +, -，則上的 正規式 d*(.dd*|) (e(+|-|)dd*| ) l (l|d)* dd*,正規集 所有無符號的數 標識符 所有無符號整數,定義 3.11 正規式等價,若兩個正規式e1, e2所表示的正規集相等(即L(e1)=L(e2)，則e1, e2等價，記為e1=e2。 例如： a|b=b|a ， b(ab)*=(ba)*b， (a|b)*=(a*b*)*,正規式的代數規律,定理3.1

36、設 r, s, t為正規式 （1）r|s = s|r “或”滿足交換律 （2）r|(s|t)=(r|s)|t “或”滿足結合律 （3）r(st)=(rs)t “連接”的可結合律 （4）r(s|t)=rs|rt，(s|t)r=sr|tr 分配律 （5）r =r = r 的恒等式 參考課本P75定理3.1,3.5.3 正規式和有窮自動機的等價性,正規式和有窮自動機的等價性由以下兩點說明： (1)上的非確定自動機M所能識別的字的全體L(M)是上的一個正規集； （或對于 上的NFA M，可以構造一個 上的正規式R，使得L(R)=L(M)） (2)對于上的每個正規集V，存在一個上的確定有窮自動機M，使得

37、V=L(M)； （或對于 上的每個正規式R，可以構造一個NFA M，使得L(M)=L(R)）,3.5.5 NFA M正規式R,把狀態圖的概念拓廣，令每條弧可用一個正規式作標記 1.添加x,y結點構造NFA M，其中x與所有的初始結弧連接，y與所有終態結弧連接。 2.反復使用以下規則，消去M中的所有結，直到只剩下x,y結； 在消結過程中逐步用正規式來標記箭弧，其消結的規則如下：,R1,R2,R1 R2,NFA M正規式R（續）,R1,R2,R1 | R2,R1,R2,R1 R2 *R3,R3,最后，x和y結點間弧上的標記則為所求的正規式R。,例,NFA M的狀態圖如下，求正規式R，使得L(R)=

38、L(M)。,所求的正規式R=(a|b)*(aa|bb)(a|b)*,0,a, b,(aa|bb)(a|b)*,Y,y,例,NFA M的狀態圖如下，求正規式R，使得L(R)=L(M)。,解：正規式R=(aa|bb) | (ab|ba)(aa|bb)*(ab|ba)*,0,aa,bb,x,(ab|ba)(aa|bb)*(ab|ba),例,有些自動機比較復雜，我們也并不完全按照上述規則進行轉換。例如,可分四種走向（要點，劃分圖成多個子圖,本題4個）： (1) sut： a(ba)*a(a|b)* (2) suvt： ab(ab)*b(a|b)* (3) svut： ba(ba)*a(a|b)* (4

39、) svt： b(ab)*b(a|b)*,(|b)a(ba)*)|(|a)b(ab)*)(a|b)+,3.5.4 正規式NFA,從正規式R構造NFA的算法： 首先把正規式R表示成如下圖的拓廣轉換圖：,R,然后通過對R進行分裂和加進新結的方法，逐步把這個圖轉換變成每條弧標記為的一個字符或。其轉換規則如下：,注： 在整個分裂的過程中，所有新結均采用不同的名字，結點x,y為構造成的NFA的唯一的初態和終態。,正規式 轉換系統,a (a),s | t (s,t是正規式),st,s*,正規式NFA（續）,正規式NFA（續）例1,R=(a|b)*abb構造NFA N，使得L(N)=L(R)。,解：,正規式

40、NFA（續）例2,構造與正規式R=(a*b)*ba(a|b)*等價的最簡DFA M，使得L(M)=L(R)。,語法制導法,用正規式的語法結構指導構造過程。 首先構造識別和中的任何符號的自動機，然后構造識別含一個選擇（或）、并置（連接）和閉包算符的正規式的自動機。 例如正規式R，首先把R分解成子表達式，然后使用以下構造規則為R構造NFA，對R的各種語法結構的構造規則具體描述如下： 1. (a)對于正規式 ，所構造的NFA為：,(b)對于正規式 ，所構造的NFA為：,(c)對于正規式a(a) ，所構造的NFA為：,語法制導法（續）,2.若s,t為上的正規式，相應的NFA分別為N(s)和N(t)，則

41、 (a)對于正規式R=s|t，所構造的NFA(R)如下：,其中x,y分別是NFA(R)的初態和終態，從x到N(s)和N(t)的初態各有一條弧，從N(s)和N(t)的終態各有一條弧到y 。,語法制導法（續）,(b)對于正規式R=st，所構造的NFA(R)如下：,其中N(s)的初態成了N(R)的初態, N(t)的終態成了N(R)的終態， N(s)的終態和N(t)的初態合并為N(R)的一個既不是初態也不是終態的狀態。,(c)對于正規式R=s*，所構造的NFA(R)如下：,其中，x和y分別是NFA(R)的初態和終態,語法制導法（續）,(d)對于正規式(s)，其NFA同s的NFA一樣。 每次構造新的狀態

42、時，都給它不同的名字，這樣所有的狀態都有不同的名字。根據上述方法構造的NFA具有以下性質： (1) NFA(R)的狀態數最多是R中符號和算符數的兩倍（ 構造的每步最多引入兩個新結點）； (2) NFA(R)只有一個初態和一個終態； (3) NFA(R)的每個狀態（除終態）有一個用的符號標記的向外的轉換，或者最多兩個向外的弧轉換。 例：為R=(a|b)*abb構造NFA N，使得L(N)=L(R)。 解：參見書本P61,綜合題,構造正規式R=(a|b)*(aa|bb)(a|b)*相應的DFA。,解：(1)構造NFA N,4.4 正規式和有窮自動機的等價性,(2)對NFA N確定化： 構造狀態轉換

43、矩陣,4.4 正規式和有窮自動機的等價性, DFA M為：,(3)對DFA M進行化簡,整個劃分為：0,1,2,3,4,5,6,3.5.6 正規文法和正規式間的轉換,一個正規語言，可以由正規文法來定義，也可以由正規式定義。任意正規文法，存在一個對應的正規式；反之亦然。 方法： 1.直接轉換 2.間接轉換 正規文法有窮自動機正規式 正規式有窮自動機正規文法,3.5.6 正規式-正規文法,將上的一個正規式r，轉換為正規文法G=( VN, VT, P, S). 1.令VT= 2. S-r , S為開始符號 3. 若x和y都是正規式，則 產生式 重寫為： r1. A-xy A-xB B-y r2. A

44、-x*yA-xA A-y r3. A-x|y A-x A-y 不斷做變換，直到每個產生式右端最多只含一個VN,3.5.6 正規式-正規文法,例 將正規式R=a(ad)轉換為相應的正規文法。 VT=a,d Sa(ad) r1. SaA A(ad) r2. A(ad)A A,r3. SaA AaA AdA A VN=S,A,3.5.6 正規文法-正規式,對G= ( VN, VT, P, S), 存在一個 = VT上的正規式R，使得 L(R)=L(G) 。在此介紹2種轉換方法： 一： 1.令 =VT 2.轉換規則 文法產生式正規式 AxB ByA=xy AxAy A=xy Axy A=xy 不斷做變

45、換，直到只剩下一個開始符號定義的產生式，且該產生式右端不含VN,3.5.6 正規文法-正規式 例子,例 文法Gs:SaA AaA AdA Sa Aa Ad 解答： SaAa AaAadAd A(ad)A(ad) A(ad)(ad), S=a(ad)(ad)a =a(ad)(ad) =a(ad) 所以，R=a(ad),3.5.6 正規文法-正規式,對G= ( VN, VT, P, S), 存在一個 = VT上的正規式R，使得 L(R)=L(G) 。在此介紹2種轉換方法： 二：方程組求解法 課本P83 如果S=aS+b 則有S=a*b 例子：關于標識符的文法 - 字母 - 數字 - 字母 = 字母

46、 + 數字 + 字母 = （字母+數字）+ 字母 所以， =字母(字母+數字)* 即，標識符可以用正規式: 字母(字母|數字)* 來表示,補充：右線性語言的封閉性,3型文法中的右線性文法所對應的語言，右線性語言。 右線性語言恰好是正則集。 對右線性語言L1,L2進行并、積和閉包運算的結果，仍然是右線性語言。 設L，L1,L2是右線性語言，則有: (1) L1L2為右線性語言 (2) L1L2為右線性語言 (3) L*為右線性語言 (4) L的補集為右線性語言 (5) L1L2為右線性語言 ,補充：右線性語言的封閉性(續1),(4) L的補集為右線性語言 例子： 根據下圖DFA M，對字母表a,b