編譯原理重點3.ppt

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

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

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

4、狀態(tài)轉(zhuǎn)換圖,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）,數(shù)字系統(tǒng)：可以從一個狀態(tài)移動到另一個狀態(tài)；每次狀態(tài)轉(zhuǎn)換，都上由當前狀態(tài)及一組輸入符號確定的；可以輸出某些離散的值集。 FA：一個狀態(tài)集合；狀態(tài)間的轉(zhuǎn)換規(guī)則；通過讀頭來掃描的一個輸入符號串。 讀頭：從左到右掃描符號串。移動（掃描）是由狀態(tài)轉(zhuǎn)換規(guī)則來決定的。,d,d,d,;,.,d,d,+,;,輸入符號串,一個FA的例子,讀頭,數(shù)字,接收：若掃描完輸入串，且在一個

5、終止狀態(tài)上結(jié)束。 阻塞：若掃描結(jié)束但未停止在終止狀態(tài)上；或者為能掃描完輸入串（如遇不合法符號）。 不完全描述：某些狀態(tài)對于某些輸入符號不存在轉(zhuǎn)換。,練習：+34.567 .123 3.4.5,=,8,0,;,0,1,3,4,2,5,6,e,n,i,L,字母,字母,字母,字母,數(shù)字,數(shù)字,數(shù)字,=,=,；,；,0,1,2,4,5,6,3,L,i,n,e,=,8,0,;, id , Line, = , , num, 80, ;, ,數(shù)字,數(shù)字,字母,字母,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是一個非空有窮集合，它的每一個元素稱為一個狀態(tài)； (2)是一個有窮字母表，它的每一個元素稱為一個輸入字符； 也稱為輸入符號字母表,確定的有窮自動機DFA的定義（續(xù)）,(3) f是從K到K的單值部分映射； f(ki,a)=kj， 其中kiK，kjK 說明：當前狀態(tài)為ki ，輸入字符a時，將轉(zhuǎn)換到下一個狀態(tài)kj ，把kj稱為ki的一個后繼狀態(tài)。 DFA的確定性就表

7、現(xiàn)在f是單值函數(shù)，即對任意狀態(tài)kK，輸入符號a，f(k,a)唯一確定一個狀態(tài)。 (4)SK，是唯一的初態(tài)； (5)Z是K的子集，是一個終態(tài)集，終態(tài)也稱為可接收狀態(tài)或結(jié)束狀態(tài)。,確定的有窮自動機DFA的表示,3.2.1 狀態(tài)轉(zhuǎn)換圖 設(shè)DFA有m個狀態(tài)，n個輸入字符，那么這個圖含有m個狀態(tài)結(jié)，每個結(jié)點最多有n條箭弧射出和別的結(jié)點相連接，每條弧用中的一個不同輸入符號作記號。整個圖含有唯一的一個初態(tài)和若干個（可以0個）終態(tài)結(jié)。 習慣上，初態(tài)結(jié)可以用“=”或“”表示，終態(tài)結(jié)用雙圓圈表示或標以“+”。對f(ki,a)=kj指從狀態(tài)結(jié)ki到狀態(tài)結(jié)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的狀態(tài)圖：,確定的有窮自動機DFA的表示（續(xù)）,3.2.2 狀態(tài)轉(zhuǎn)換矩陣 矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)的狀態(tài)行在輸入字符列下的新的狀態(tài)，即f(k,a)的值。,例（題同）,解：該DFA M的矩陣表示,0 0 0 1,3.2.3 有關(guān)自動機術(shù)語,(1)道路：對于*中的任何字，若存在一條從初態(tài)到某終態(tài)的路徑。 (2)識別：道路上所有弧的標記連接成的字等于，則稱可為D

9、FA M所識別（所接受）。 即若t*, f(S,t)=P，其中S為DFA M的初始狀態(tài)，PZ（終態(tài)集）。 若M的初態(tài)結(jié)同時也是終態(tài)結(jié)，則空字可為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 有關(guān)確定有窮自

10、動機的結(jié)論,把DFA M所能接受的所有字（字的全體）記為L(M)。 上的一個字集V*是正規(guī)的，當且僅當存在一個上的確定有窮自動機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是一個有窮集合，它的每一個元素稱為一個狀態(tài)； (2)是一個有窮字母表，它的每一個元素稱為一個輸入字符； 也稱為輸入符號字母表 (3) f是一個K*到K的子集的映射： f : K*2k (4)S是K的子集，是非空的初態(tài)集

11、； (5)Z是K的子集，是一個終態(tài)集，也稱可接收狀態(tài)或結(jié)束狀態(tài)。,3.2.5 不確定的有窮自動機(NFA)的定義,NFA的表示,用狀態(tài)轉(zhuǎn)換圖（ f是多值函數(shù)） 由NFA的定義，可把一個含有m個狀態(tài)和n個輸入字符的NFA表示如下： 圖中有m個狀態(tài)結(jié)，對每個狀態(tài)結(jié)可射出若干條弧和別的狀態(tài)結(jié)相連，且每條弧用*中的一個字（不一定要不同的字且可以是空字）作標記（或稱輸入字）。整個圖中至少含有一個初態(tài)結(jié)以及若干個（可以是0個）終態(tài)結(jié)。 某些結(jié)既可以是初態(tài)結(jié)也可以是終態(tài)結(jié)。,例,題：一個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,解：其狀態(tài)圖如下：,例,如下狀態(tài)圖也是一個NFA,有關(guān)非確定有窮自動機的術(shù)語,對于*中的任何一個串t可被NFA M識別是指：若對這個字（串）t存在一條從某個初態(tài)結(jié)到某一個終態(tài)結(jié)的道路，且這條道路上所有弧的標記字依序連接起來的字（不理睬那些標記為的弧）等于t，則t可識別（或可接受） 若M的某些結(jié)點既是初態(tài)結(jié)也是終態(tài)結(jié)，或存在一條從某個初態(tài)結(jié)到某個終態(tài)結(jié)的道路，則空字可為M所識別（所接受）。,補充：遞歸思想構(gòu)造文法,在某些復(fù)雜的語言中，字符串可能包含一種結(jié)構(gòu)，它遞歸地作為另一種（或者同一種）結(jié)構(gòu)的一部分而出現(xiàn)，可利用遞歸思想來構(gòu)造對應(yīng)的文法。 例1：定義語言L=| 中a和

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

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

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

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

17、設(shè)計有限自動機（續(xù)7）,1.思考題： 構(gòu)造一個有窮自動機M，識別0，1，2上的語言，該語言的每個字符串代表的十進制數(shù)能被3整除。 如：102，1020，10201，110,2.編程題：根據(jù)有窮自動機M，編寫程序，識別所有由奇數(shù)個a和奇數(shù)個b組成的字符串。,(1)用戶輸入：ab組成的符號串； (2)一個字符一個字符地讀、分析； (3)不要使用計數(shù)器。,設(shè)計有限自動機（續(xù)8）,1.思考題： 構(gòu)造一個有窮自動機M，識別0，1，2上的語言，該語言的每個字符串代表的十進制數(shù)能被3整除。 如：102，1020，10201，110,思路(1) :所有位數(shù)之和； (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的關(guān)系,DFA是NFA的一個特例。 對于每個NFA M，存在一個DFA M，使得L(M)=L(M) 對于任何兩個有窮自動機M和M，如L(M)=L(M)則稱M和M是等價的。 如果M僅通過重新標記它的狀態(tài)，就能轉(zhuǎn)換成M，則M和M稱為同構(gòu)的。 對于每一個FA M，存在一個等價的、具有最少狀態(tài)個數(shù)的FA M，對于其它的FA M，若M的狀態(tài)個數(shù)與M相同且等價與M，則必然有M與M同構(gòu)，即：M在結(jié)構(gòu)上是唯一的。,3.3 NFA DFA的轉(zhuǎn)換（NFA的確定化）,通

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

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

21、 _closure(I)定義為： a. 若SI，則S _closure(I)； b. 若SI，那么從S出發(fā)經(jīng)過任意弧而能到達的任意狀態(tài)S都屬于_closure(I)；,題：有一個狀態(tài)圖如下：,假定 I= _closure(1)1, 2 從狀態(tài)集I出發(fā)經(jīng)過一條a弧而能到達的狀態(tài)結(jié)全體J為5, 3, 4； 而_closure(J) =5, 6, 2, 3, 8, 4, 7,例,NFA的確定化,從NFA N (K, , f, K0, Kt)構(gòu)造一個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的開始符號（初態(tài)）； (5) St =Sj, Sk, Se，其中Sj, Sk, Se S且Sj, Sk, SeKt ,子集化的具體過程,為了方便起見，令中只有a,b兩個字母，即a, b （1）構(gòu)造一張表，此表的每一行有三列，第一列為I，第二列為Ia，第二列為Ib。即,首先置該表的第一列為_closure(K0)。,（2）一般而言，若某一行的第一列的狀態(tài)子集已確定，例如記為I，則可以求出Ia和Ib ；,子集化的具體過程（續(xù)

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

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

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

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

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

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

30、：終結(jié)組C、非終結(jié)組A,B,D； (2)考慮A,B,D，由于A,B,D1=A,C，因此對A,B,D一分為二，分成A、B,D,例(續(xù)),至此，整個集合含有三組：A、B,D、C。 最后，令狀態(tài)B代表B,D，將原來導(dǎo)入到D的弧都導(dǎo)入到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 正規(guī)文法和有窮自動機間的轉(zhuǎn)換,3.4.1 (1)正規(guī)文法GNFA M： 構(gòu)造規(guī)則： (a) 與G中

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

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

33、(c) VN為NFA所有狀態(tài)中的標記（K），VT為NFA的， NFA的初態(tài)就是開始符號S。,例,例：給出與NFA等價的正規(guī)文法G,解：與NFA等價正規(guī)文法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 正規(guī)表達式與FA,單詞的描述工具：正規(guī)文法 正規(guī)文法（3型文法）的形式定義 設(shè)G=( VN, VT, P, S)為一文法，若G的任何產(chǎn)生式A 或A B ，其中A、B VN ， VT* 。,正規(guī)文法的例子,例：“無符號實數(shù)”定義 d | . | e d | . | e | d e | d

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

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

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

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

38、L(M)。,所求的正規(guī)式R=(a|b)*(aa|bb)(a|b)*,0,a, b,(aa|bb)(a|b)*,Y,y,例,NFA M的狀態(tài)圖如下，求正規(guī)式R，使得L(R)=L(M)。,解：正規(guī)式R=(aa|bb) | (ab|ba)(aa|bb)*(ab|ba)*,0,aa,bb,x,(ab|ba)(aa|bb)*(ab|ba),例,有些自動機比較復(fù)雜，我們也并不完全按照上述規(guī)則進行轉(zhuǎn)換。例如,可分四種走向（要點，劃分圖成多個子圖,本題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 正規(guī)式NFA,從正規(guī)式R構(gòu)造NFA的算法： 首先把正規(guī)式R表示成如下圖的拓廣轉(zhuǎn)換圖：,R,然后通過對R進行分裂和加進新結(jié)的方法，逐步把這個圖轉(zhuǎn)換變成每條弧標記為的一個字符或。其轉(zhuǎn)換規(guī)則如下：,注： 在整個分裂的過程中，所有新結(jié)均采用不同的名字，結(jié)點x,y為構(gòu)造成的NFA的唯一的初態(tài)和終態(tài)。,正規(guī)式 轉(zhuǎn)換系統(tǒng),a (a),s | t (s,t是正規(guī)式),st,s*,正規(guī)式NFA（續(xù)）,正規(guī)式NFA（續(xù)）例1,R=(a|b)*abb構(gòu)造NFA N，使得L(N)=L(R)。,解：,正規(guī)式

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

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

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

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

44、-x*yA-xA A-y r3. A-x|y A-x A-y 不斷做變換，直到每個產(chǎn)生式右端最多只含一個VN,3.5.6 正規(guī)式-正規(guī)文法,例 將正規(guī)式R=a(ad)轉(zhuǎn)換為相應(yīng)的正規(guī)文法。 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 正規(guī)文法-正規(guī)式,對G= ( VN, VT, P, S), 存在一個 = VT上的正規(guī)式R，使得 L(R)=L(G) 。在此介紹2種轉(zhuǎn)換方法： 一： 1.令 =VT 2.轉(zhuǎn)換規(guī)則 文法產(chǎn)生式正規(guī)式 AxB ByA=xy AxAy A=xy Axy A=xy 不斷做變

45、換，直到只剩下一個開始符號定義的產(chǎn)生式，且該產(chǎn)生式右端不含VN,3.5.6 正規(guī)文法-正規(guī)式 例子,例 文法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 正規(guī)文法-正規(guī)式,對G= ( VN, VT, P, S), 存在一個 = VT上的正規(guī)式R，使得 L(R)=L(G) 。在此介紹2種轉(zhuǎn)換方法： 二：方程組求解法 課本P83 如果S=aS+b 則有S=a*b 例子：關(guān)于標識符的文法 - 字母 - 數(shù)字 - 字母 = 字母

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