計算機科學與技術 編譯原理第三章重點

1、第三章第三章 有窮自動機有窮自動機要點：要點： 1. DFA 1. DFA和和NFANFA的定義的定義 2. NFADFA 2. NFADFA的轉換；的轉換； 3. DFA 3. DFA的化簡的化簡 4. 4. 正規(guī)文法、正規(guī)式、有正規(guī)文法、正規(guī)式、有窮自動機之間的相互轉換；窮自動機之間的相互轉換；編譯原理編譯原理2有窮自動機有窮自動機 有窮自動機（或有限自動機）作為一種識別工有窮自動機（或有限自動機）作為一種識別工具，它能正確地識別正規(guī)集，即識別正規(guī)文法所定具，它能正確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合。引入有窮自動機義的語言和正規(guī)式所表示的集合。引入有窮自動機這個

2、理論，正是為詞法分析程序的自動構造尋找特這個理論，正是為詞法分析程序的自動構造尋找特殊的方法和工具。殊的方法和工具。分類：確定的有窮自動機（分類：確定的有窮自動機（DFA） 不確定的有窮自動機（不確定的有窮自動機（NFA）33.1 概述概述 有窮自動機（有窮自動機（FA） 有窮自動機（有窮自動機（FA，F(xiàn)inite Automata）是一種有限離散數）是一種有限離散數字系統(tǒng)的抽象數學模型。字系統(tǒng)的抽象數學模型。 這個系統(tǒng)具有有限數目的內部這個系統(tǒng)具有有限數目的內部“狀態(tài)狀態(tài)”。 所謂狀態(tài)，是可以將事物區(qū)分開的一種標識。例如：數所謂狀態(tài)，是可以將事物區(qū)分開的一種標識。例如：數字電路（字電路（0，

3、1），十字路口的紅綠燈等都是離散狀態(tài)系統(tǒng)，），十字路口的紅綠燈等都是離散狀態(tài)系統(tǒng)，其狀態(tài)數目是有限的。連續(xù)狀態(tài)系統(tǒng)則如水庫的水位、室內其狀態(tài)數目是有限的。連續(xù)狀態(tài)系統(tǒng)則如水庫的水位、室內溫度變化等。溫度變化等。 電梯的控制機制，不需要保存所有以前的服務要求，僅電梯的控制機制，不需要保存所有以前的服務要求，僅需記住當前的層次、運動的方向以及未滿足的服務要求。需記住當前的層次、運動的方向以及未滿足的服務要求。 文本編輯程序和詞法分析程序是有限狀態(tài)系統(tǒng)，計算機文本編輯程序和詞法分析程序是有限狀態(tài)系統(tǒng)，計算機本身和人的大腦也可看成有限狀態(tài)系統(tǒng)。本身和人的大腦也可看成有限狀態(tài)系統(tǒng)。 4有窮自動機（有窮自

4、動機（FA） 數字系統(tǒng)：可以從一個狀態(tài)移動到另一個狀態(tài)；每次數字系統(tǒng)：可以從一個狀態(tài)移動到另一個狀態(tài)；每次狀態(tài)轉換，都上由當前狀態(tài)及一組輸入符號確定的；可以狀態(tài)轉換，都上由當前狀態(tài)及一組輸入符號確定的；可以輸出某些離散的值集。輸出某些離散的值集。 FA：一個狀態(tài)集合；狀態(tài)間的轉換規(guī)則；通過讀頭來：一個狀態(tài)集合；狀態(tài)間的轉換規(guī)則；通過讀頭來掃描的一個輸入符號串。掃描的一個輸入符號串。 讀頭：從左到右掃描符號串。移動（掃描）是由狀態(tài)讀頭：從左到右掃描符號串。移動（掃描）是由狀態(tài)轉換規(guī)則來決定的。轉換規(guī)則來決定的。5ddd;.dd+;輸入符號串一個FA的例子讀頭數字A數字+-.SGBH數字數字.數字

5、接收：若掃描完輸入串，接收：若掃描完輸入串，且在一個終止狀態(tài)上結且在一個終止狀態(tài)上結束。束。阻塞：若掃描結束但未阻塞：若掃描結束但未停止在終止狀態(tài)上；或停止在終止狀態(tài)上；或者不能掃描完輸入串者不能掃描完輸入串（如遇不合法符號）。（如遇不合法符號）。不完全描述：某些狀態(tài)不完全描述：某些狀態(tài)對于某些輸入符號不存對于某些輸入符號不存在轉換。在轉換。練習練習：+34.567 .123 3.4.56= 80;0134256eniL字母字母字母字母數字數字數字= =；0124563L ine= 80; id , Line = , num, 80 ;, 數字數字字母字母1 1= =0 0 03; ;1輸入符

6、號串輸出有限控制器讀頭other73.2 有窮自動機的形式定義有窮自動機的形式定義DFA: Deterministic Finite AutomataNFA: Nondeterministic Finite AutomataDFA的定義的定義定義定義3.1 一個確定的有窮自動機一個確定的有窮自動機(DFA) M是一個五元組：是一個五元組： M = ( Q, , t, q0, F ) (1)Q是一個非空有窮集合，它的每一個元素稱為一個狀態(tài)；是一個非空有窮集合，它的每一個元素稱為一個狀態(tài)； (2)是一個有窮字母表，它的每一個元素稱為一個輸入字是一個有窮字母表，它的每一個元素稱為一個輸入字符；符；

7、也稱為輸入符號字母表也稱為輸入符號字母表8確定的有窮自動機確定的有窮自動機DFA的定義（續(xù)）的定義（續(xù)） (3) t是從是從Q到到Q的一個單值映射；的一個單值映射； t(q,a)=q， 其中其中q, qQ說明：當前狀態(tài)為說明：當前狀態(tài)為q ，輸入字符，輸入字符a時，將轉換到下一個時，將轉換到下一個狀態(tài)狀態(tài)q ，把，把q稱為稱為q的一個后繼狀態(tài)。的一個后繼狀態(tài)。 DFA的確定性就表現(xiàn)在的確定性就表現(xiàn)在t是單值函數，即對任意狀態(tài)是單值函數，即對任意狀態(tài)qQ，輸入符號輸入符號a，t(q,a)唯一確定一個狀態(tài)。唯一確定一個狀態(tài)。 (4)q0Q，是唯一的初態(tài)；，是唯一的初態(tài)； (5)F是是Q的子集，是一

8、個終態(tài)集，終態(tài)也稱為可接收狀態(tài)或的子集，是一個終態(tài)集，終態(tài)也稱為可接收狀態(tài)或結束狀態(tài)結束狀態(tài)。9確定的有窮自動機確定的有窮自動機DFA的表示的表示 3.2.1 狀態(tài)轉換圖狀態(tài)轉換圖 設設DFA有有m個狀態(tài)，個狀態(tài)，n個輸入字符，那么這個圖含有個輸入字符，那么這個圖含有m個狀態(tài)結點，每個結點最多有個狀態(tài)結點，每個結點最多有n條箭弧射出和別的結點相連條箭弧射出和別的結點相連接，每條弧用接，每條弧用中的一個不同輸入符號作記號。整個圖含有中的一個不同輸入符號作記號。整個圖含有唯一的一個初態(tài)和若干個（可以唯一的一個初態(tài)和若干個（可以0個）終態(tài)結。個）終態(tài)結。 習慣上，初態(tài)結可以用習慣上，初態(tài)結可以用“=

9、”或或“”表示，終態(tài)結表示，終態(tài)結用雙圓圈表示或標以用雙圓圈表示或標以“+”。對。對t(q,a)=q指從狀態(tài)結指從狀態(tài)結q到狀到狀態(tài)結態(tài)結q畫標記畫標記a的弧。的弧。10 例例題：題：DFA M=(0, 1, 2, 3，a, b，t，0，3)，其中，其中t定義為：定義為： t(0,a)=1， t(0,b)=2， t(1,a)=3， t(1,b)=2， t(2,a)=1， t(2,b)=3， t(3,a)=3， t(3,b)=3解：該解：該DFA M的狀態(tài)圖：的狀態(tài)圖：0123abbaaba, b11確定的有窮自動機確定的有窮自動機DFA的表示（續(xù)）的表示（續(xù)）3.2.2 狀態(tài)轉換矩陣狀態(tài)轉換矩

10、陣 矩陣的行表示狀態(tài)，列表示輸入字符，矩矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應的狀態(tài)行在輸入字符列下的新陣元素表示相應的狀態(tài)行在輸入字符列下的新的狀態(tài)，即的狀態(tài)，即t(k,a)的值。的值。12例（題同）例（題同）解：該解：該DFA M的矩陣表示的矩陣表示狀態(tài)狀態(tài) 字符字符ab0121322133330123abbaaba, b t(0,a)=1， t(0,b)=2， t(1,a)=3， t(1,b)=2， t(2,a)=1， t(2,b)=3， t(3,a)=3， t(3,b)=3133.2.3 有關自動機術語有關自動機術語(1)道路：對于道路：對于*中的任何符號串中的任何符號串，

11、若存在一條從初態(tài)到，若存在一條從初態(tài)到某終態(tài)的路徑。某終態(tài)的路徑。(2)識別：道路上所有弧的標記連接成的符號串等于識別：道路上所有弧的標記連接成的符號串等于，則，則稱稱可為可為DFA M所識別（所接受）。所識別（所接受）。即若即若 *, t(q,)=P，其中，其中q為為DFA M的初始狀態(tài)，的初始狀態(tài)，PF（終態(tài)集）。（終態(tài)集）。若若M的初態(tài)結同時也是終態(tài)結，則空字的初態(tài)結同時也是終態(tài)結，則空字可為可為M所識別，所識別，即即qF, f(q, )=q(3)運行：運行： t(q, 1 2) = t(t(q, 1), 2)，其中，其中qQ， 1 2為輸為輸入字符串，且入字符串，且 1 ， 1 2 *

12、14例例解：解：t(0, abba) = t(t(0,a), bba)= t(1, bba) = t(t(1,b), ba) = t(2, ba) = t(t(2,b), a) = t(3, a) = 3 得證得證題：試證題：試證abba可為例可為例1的的DFA M所識別（所接受）。所識別（所接受）。0123abbaaba, b15 3.2.4 有關確定有窮自動機的結論有關確定有窮自動機的結論 把把DFA M所能接受的所有符號串（符號串的所能接受的所有符號串（符號串的全體）記為全體）記為L(M)。 上的一個字集上的一個字集V*是正規(guī)的，當且僅當存是正規(guī)的，當且僅當存在一個在一個上的確定有窮自動

13、機上的確定有窮自動機M，使得，使得L(M)=V。16有限自動機識別的語言有限自動機識別的語言 例子例子 例：下圖中的自動機所能識別的語言是什么？例：下圖中的自動機所能識別的語言是什么？q0q2q1q3abbaba17 定義定義3.4 一個不確定的有窮自動機一個不確定的有窮自動機NFA N也是一個五元組：也是一個五元組：M = ( Q, , t, q0, F ) (1)Q是一個有窮集合，它的每一個元素稱為一個狀態(tài)；是一個有窮集合，它的每一個元素稱為一個狀態(tài)； (2)是一個有窮字母表，它的每一個元素稱為一個輸入字符；是一個有窮字母表，它的每一個元素稱為一個輸入字符； 也稱為輸入符號字母表也稱為輸入

14、符號字母表 (3) t是一個是一個Q*到到Q的子集的映射：的子集的映射： t : Q*2Q (4)q0是是Q的子集，是非空的初態(tài)集；的子集，是非空的初態(tài)集； (5)F是是Q的子集，是一個終態(tài)集，也稱可接收狀態(tài)或結束狀態(tài)。的子集，是一個終態(tài)集，也稱可接收狀態(tài)或結束狀態(tài)。3.2.5 不確定的有窮自動機不確定的有窮自動機(NFA)的定義的定義18NFA的表示用狀態(tài)轉換圖（用狀態(tài)轉換圖（ t是多值函數）是多值函數） 由由NFA的定義，可把一個含有的定義，可把一個含有m個狀態(tài)和個狀態(tài)和n個輸入字符的個輸入字符的NFA表示如下：表示如下：圖中有圖中有m個狀態(tài)節(jié)，對每個狀態(tài)節(jié)可射出若干條弧和別個狀態(tài)節(jié)，對每

15、個狀態(tài)節(jié)可射出若干條弧和別的狀態(tài)節(jié)相連，且每條弧用的狀態(tài)節(jié)相連，且每條弧用*中的一個字（不一定要不中的一個字（不一定要不同的字且可以是空字同的字且可以是空字）作標記（或稱輸入字）。整個）作標記（或稱輸入字）。整個圖中至少含有一個初態(tài)節(jié)以及若干個（可以是圖中至少含有一個初態(tài)節(jié)以及若干個（可以是0個）終個）終態(tài)節(jié)。態(tài)節(jié)。 某些節(jié)既可以是初態(tài)節(jié)也可以是終態(tài)節(jié)。某些節(jié)既可以是初態(tài)節(jié)也可以是終態(tài)節(jié)。19例例題：一個題：一個NFA M(q0, q1，0, 1，t，q0，q1)，其中，其中 t(q0, 0)=q0, q1, t(q0, 1)=q1, t(q1, 0)=, t(q1, 1)=q0, q1,解：

16、其狀態(tài)圖如下：解：其狀態(tài)圖如下：q00q1011120例例如下狀態(tài)圖也是一個如下狀態(tài)圖也是一個NFA0a,b1aabba,b2a,b21有關非確定有窮自動機的術語有關非確定有窮自動機的術語對于對于*中的任何一個串中的任何一個串t可被可被NFA M識別是指：識別是指：若對這個字（串）若對這個字（串）t存在一條從某個初態(tài)節(jié)到某一存在一條從某個初態(tài)節(jié)到某一個終態(tài)節(jié)的道路，且這條道路上所有弧的標記字依個終態(tài)節(jié)的道路，且這條道路上所有弧的標記字依序連接起來的字符串（不理睬那些標記為序連接起來的字符串（不理睬那些標記為的?。┑幕。┑扔诘扔趖，則，則t可識別（或可接受）可識別（或可接受）若若M的某些節(jié)點既是

17、初態(tài)節(jié)也是終態(tài)節(jié)，或存的某些節(jié)點既是初態(tài)節(jié)也是終態(tài)節(jié)，或存在一條從某個初態(tài)節(jié)到某個終態(tài)節(jié)的在一條從某個初態(tài)節(jié)到某個終態(tài)節(jié)的道路，則空道路，則空字字可為可為M所識別（所接受）。所識別（所接受）。22NFA和和DFA的關系的關系 DFA是是NFA的一個特例。的一個特例。 對于每個對于每個NFA M，存在一個，存在一個DFA M，使得，使得L(M)=L(M) 對于任何兩個有窮自動機對于任何兩個有窮自動機M和和M，如，如L(M)=L(M)則則稱稱M和和M是是等價等價的。的。 如果如果M僅通過重新標記它的狀態(tài)，就能轉換成僅通過重新標記它的狀態(tài)，就能轉換成M，則，則M和和M稱為同構的。稱為同構的。 對于每

18、一個對于每一個NFA M，存在一個等價的、具有最少狀態(tài)個，存在一個等價的、具有最少狀態(tài)個數的數的DFA M，對于其它的，對于其它的DFA M”，若，若M”的狀態(tài)個數的狀態(tài)個數與與M相同且等價于相同且等價于M，則必然有，則必然有M”與與M同構，即：同構，即：M在結構上是唯一的。在結構上是唯一的。23243.3 NFA DFA的轉換（的轉換（NFA的確定化）的確定化） 通過以下步驟，可以將一個通過以下步驟，可以將一個NFA轉換為等價的轉換為等價的DFA：1.尋找并消除空移環(huán)路；尋找并消除空移環(huán)路；2.消除余下的空移；消除余下的空移；3.確定化確定化 子集法、造表法；子集法、造表法；4.DFA的最小

19、化的最小化構造狀態(tài)集合的劃分構造狀態(tài)集合的劃分25 3.3.1 NFA中空移環(huán)路的尋找和消除中空移環(huán)路的尋找和消除空移環(huán)路：空移環(huán)路：一個空移環(huán)路，是一個從狀態(tài)一個空移環(huán)路，是一個從狀態(tài)A開始，并以狀態(tài)開始，并以狀態(tài)A結結束的空移動序列。束的空移動序列。q1q2q1q2q3q1q2q3qn消除方法：消除方法：合并環(huán)路上的合并環(huán)路上的節(jié)點為新節(jié)點。節(jié)點為新節(jié)點。若含初態(tài)，則若含初態(tài)，則新節(jié)點為初態(tài)。新節(jié)點為初態(tài)。若含終態(tài)，則若含終態(tài)，則新節(jié)點為終態(tài)。新節(jié)點為終態(tài)。課本課本P53 例例3.426 3.3.2 NFA的消除空移ABa1q1q2qna2anABa1q1q2qna2ana1ana2消除方

20、法：消除方法：刪除刪除弧，產生新弧?；。a生新弧。若若A為初態(tài)，則為初態(tài)，則B結點也為初態(tài)。結點也為初態(tài)。若若B為終態(tài)，則為終態(tài)，則A結點也為終態(tài)。結點也為終態(tài)。273.3.3 利用狀態(tài)轉換表消除空移1. 首先找出直接經由一個空移到達某個終態(tài)的所有狀態(tài)。每找到這樣一個狀態(tài)，標記為終態(tài)。2. 然后，考慮消除與未被標記為終態(tài)的那些狀態(tài)相關的空移。3. 對表中每一個具有射出連線的狀態(tài)繼續(xù)按上述方式處理，直到狀態(tài)表不再變動為止。4. 從表中刪除列和沒有任何元素的空行，便得到一個不含空移的狀態(tài)轉換表。28+-.dSAAAAB,CEBBFCDCDDFEGEFGHHHF表3.2 圖3.4中NDFA標記狀態(tài)后

21、的情況29+-.dSAAGB,C,EAGB,C,EBBCDCDDEGEGHHH表3.3 刪除空移后的狀態(tài)轉換圖303.3.4 NFA的確定化子集法 一個例子一個例子( 無空移無空移) p55 圖圖3.9 介紹一種稱介紹一種稱子集法子集法的算法來將的算法來將NFA轉換成接轉換成接收同樣語言的收同樣語言的DFA。 算法的基本思想是：把算法的基本思想是：把DFA中的每一個狀態(tài)中的每一個狀態(tài)對應對應NFA中的一組狀態(tài)。即由于中的一組狀態(tài)。即由于NFA中的中的t是多值是多值的，所以在讀入一個輸入符號后可能達到的狀態(tài)的，所以在讀入一個輸入符號后可能達到的狀態(tài)是集合，而子集法就是用是集合，而子集法就是用DF

22、A的狀態(tài)記錄該狀態(tài)的狀態(tài)記錄該狀態(tài)的集合。的集合。31將NDFA M=(Q, ,t,Q0,F) 轉換為DFA M=(Q, ,t,q0,F)的步驟： 1. M的狀態(tài)集Q是由M的狀態(tài)集Q的所有子集組成的。用p1,p2, ,pi表示Q的元素。2. 若p是M的一個終態(tài)，則M中的每一個包含p的狀態(tài),p,都是M的一個終態(tài)。3. 若S=S1,S2,Sj是M的初態(tài)，則S=S1,S2,Sj是M的初態(tài)。4. 令p1,p2,pn是M中的一個狀態(tài)，其中p1,p2,pn是M中的狀態(tài)。對某個輸入符號a，考慮M中的轉換函數：t(p1,a), t(p2,a), , t(pn,a)，按以下方法得到M的轉換函數t: a. 令t(

23、p1,a)U t(p2,a)UU t(pn,a)=q1,q2,qr b. 置t(p1,p2,pn,a)=q1,q2,qr5. 對M每一狀態(tài)和每個輸入符號a，重復步驟4.32利用狀態(tài)表將NDFA轉換為DFA。以表3.3為例+-.dSAAGB,C,EAGB,C,EBBCDCDDEGEGHHHB,C,ED,GB,C,E新狀態(tài)新狀態(tài)D,GD,H新狀態(tài)新狀態(tài)D,HD,H新狀態(tài)新狀態(tài)333.3.5 確定化確定化-造表法造表法（2）Move(I, a)狀態(tài)集合狀態(tài)集合I的的a弧轉換弧轉換 假定假定I是狀態(tài)集的一個子集，是狀態(tài)集的一個子集，a是是中的一個字符，定義中的一個字符，定義 Ia _closure(J

24、)其中其中J是所有那些可從是所有那些可從I中的某一狀態(tài)出發(fā)經過一條中的某一狀態(tài)出發(fā)經過一條a弧而到達弧而到達的狀態(tài)結的全體。的狀態(tài)結的全體。(3)Ia _closure(Move(I, a)（1）_closure(I) 狀態(tài)集合狀態(tài)集合I的的閉包閉包(等價狀態(tài)集等價狀態(tài)集) 設設I是狀態(tài)集的一個子集，是狀態(tài)集的一個子集， _closure(I)定義為：定義為： a. 若若SI，則，則S _closure(I)； b. 若若SI，那么從，那么從S出發(fā)經過任意出發(fā)經過任意弧而能到達的任意狀態(tài)弧而能到達的任意狀態(tài)S都屬于都屬于_closure(I)；1. 有關定義34題：有一個狀態(tài)圖如下：題：有一個

25、狀態(tài)圖如下：1526a4a73a8假定假定 I= _closure(1)1, 2從狀態(tài)集從狀態(tài)集I出發(fā)經過一條出發(fā)經過一條a弧而能到達的狀態(tài)結全體弧而能到達的狀態(tài)結全體J為為5, 3, 4；而而_closure(J) =5, 6, 2, 3, 8, 4, 7例例35NFA的確定化的確定化 從從NFA N (Q, , t, q0, F)構造一個構造一個DFA M (Q, , t, q0, F)，其中，其中 (1) Q是由是由Q一些子集組成；一些子集組成； (2) M與與N的輸入字母表相同，都是的輸入字母表相同，都是； (3)t定義：定義： t(q1, q2, qj, a)=q1, q2, qi，

26、其中，其中 _closure(move(q1, q2, qj, a)= q1, q2, qi (4) q0 = _closure(q0)為為M的開始符號（初態(tài)）；的開始符號（初態(tài)）； (5) F =qj, qk, qe，其中，其中qj, qk, qe Q且且qj, qk, qeF 36具體過程具體過程為了方便起見，令為了方便起見，令中只有中只有a,b兩個字母，即兩個字母，即a, b（1）構造一張表，此表的每一行有三列，第一列為）構造一張表，此表的每一行有三列，第一列為I，第二，第二列為列為Ia，第二列為，第二列為Ib。即。即I IIaIb_closure(q0)首先置該表的第一列為首先置該表的

27、第一列為_closure(q0)。（2）一般而言，若某一行的第一列的狀態(tài)子集已確定，例如）一般而言，若某一行的第一列的狀態(tài)子集已確定，例如記為記為I，則可以求出，則可以求出Ia和和Ib ；37具體過程（續(xù)）具體過程（續(xù)） （3）檢查）檢查Ia和和Ib是否已在表的第一列中出現(xiàn)，把未曾出現(xiàn)者是否已在表的第一列中出現(xiàn)，把未曾出現(xiàn)者填入到后面空行的第一列位置上。填入到后面空行的第一列位置上。 （4）對未重復）對未重復Ia 、 Ib的新行重復上述過程的新行重復上述過程(2)、(3) ，直到所，直到所有第二列和第三列的子集全部在第一列中出現(xiàn)；有第二列和第三列的子集全部在第一列中出現(xiàn)； 上述過程必定在有限步

28、內終止，因為上述過程必定在有限步內終止，因為N的狀態(tài)子集的個數的狀態(tài)子集的個數是有限的。我們也可將表看成狀態(tài)轉換矩陣，即把其中每個是有限的。我們也可將表看成狀態(tài)轉換矩陣，即把其中每個子集看成一個狀態(tài)，就可以由這張表唯一刻劃出一個確定的子集看成一個狀態(tài)，就可以由這張表唯一刻劃出一個確定的有窮自動機有窮自動機DFA。其初態(tài)就是該表的第一行第一列的。其初態(tài)就是該表的第一行第一列的_closure(q0) ，終態(tài)就是那些含有，終態(tài)就是那些含有F的子集。的子集。38例例題：將下圖題：將下圖NFA N確定化。確定化。12b3a7045b68a910bIIaIbSab0,1,2,4,71,2,3,4,6,7

29、,81,2,4,5,6,70121,2,3,4,6,7,8 1,2,3,4,6,7,8 1,2,4,5,6,7,91131,2,4,5,6,71,2,3,4,6,7,81,2,4,5,6,72121,2,4,5,6,7,9 1,2,3,4,6,7,8 1,2,4,5,6,7,103141,2,4,5,6,7,10 1,2,3,4,6,7,81,2,4,5,6,7412解：(1)構造轉換矩陣構造轉換矩陣39 接上頁接上頁(2)對表中所有的子集重新命名，其中對表中所有的子集重新命名，其中0是初態(tài)，是初態(tài)，4是終態(tài)。是終態(tài)。 對應的對應的DFA M：0124ba3aabbabab40例例題：將下圖確

30、定化：題：將下圖確定化：解：解：(1)構造轉換矩陣構造轉換矩陣II0I1S01s,x,yws,x,yABAw y,s,x,zBCs,x,y,zw,s,x,ys,x,yCDAw,s,x,yws,x,y,zDBCsyxwz1010141接上頁接上頁 DFA M為：為：ABDC011010142例子3.7：求與右圖等價的DFA= (Q,t,q0,F) 1. =x,y2. Q=q0,q1,q2,q3,q0,q1,q0,q1,q2,q33. F=q3,q0,q3,q1,q3,q2,q3,q0,q1,q2,q3xyq0q1, q2q0q1, q2q0, q3q1, q2, q3q0, q3q1, q2,

31、q3q0, q3q1, q2, q3q0, q1, q3q1, q2, q3q0, q1, q3q0, q1,q2, q3q0, q1,q2, q3q0, q1,q2, q3q0, q1,q2, q3q0, q1,q2, q3. 確定化后的狀態(tài)轉換矩陣確定化后的狀態(tài)轉換矩陣xyq0q1q0q1q2q3q2q3q2q3q4q3q4q5q5q5q5q5433.3.6 消除不可達狀態(tài) 有窮自動機的有窮自動機的多余狀態(tài)多余狀態(tài)：是指這樣的狀態(tài)，從該自動：是指這樣的狀態(tài)，從該自動機的開始狀態(tài)出發(fā)，任何輸入串也不能達到的那個狀態(tài)。機的開始狀態(tài)出發(fā)，任何輸入串也不能達到的那個狀態(tài)。 01S0S1S5S1S2

32、S7S2S2S5S3S5S7S4S5S6S5S3S1S6S8S0S7S0S1S8S3S6443.3.7 DFA的化簡的化簡 對已求得的對已求得的DFA，可以進一步將其化簡，即求最小，可以進一步將其化簡，即求最小DFA。也就是對于任意給定的也就是對于任意給定的DFA M構造另一個構造另一個DFA M，使，使L(M)=L(M)，且，且DFA M的狀態(tài)個數少于的狀態(tài)個數少于DFA M的狀態(tài)個的狀態(tài)個數。數。 消除多余狀態(tài)消除多余狀態(tài) DFA M狀態(tài)最少化的過程：狀態(tài)最少化的過程： 把把M的狀態(tài)集分割成一些不相交的子集，使得任何不同的狀態(tài)集分割成一些不相交的子集，使得任何不同的兩個子集的狀態(tài)都是可區(qū)別

33、的，而同一子集中的任何兩個的兩個子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的。狀態(tài)都是等價的。45有關分割法所用的概念有關分割法所用的概念定義定義3.7 等價等價 設設s,t是是M的兩個不同的狀態(tài)，的兩個不同的狀態(tài)，s,t等價的意思是：如果從狀等價的意思是：如果從狀態(tài)態(tài)s出發(fā)能讀出某個字出發(fā)能讀出某個字而停于終態(tài)，那么同樣從而停于終態(tài)，那么同樣從t出發(fā)也能讀出發(fā)也能讀出同一個字出同一個字而停于終態(tài)；反之，若能從而停于終態(tài)；反之，若能從t出發(fā)讀出某個字出發(fā)讀出某個字而而停于終態(tài)，那么同樣從停于終態(tài)，那么同樣從s出發(fā)也能讀出字出發(fā)也能讀出字而停于終態(tài)。而停于終態(tài)。 等價的條件：等價

34、的條件：(1)一致性條件一致性條件 狀態(tài)狀態(tài)t,s必須同時是可接受狀態(tài)或不可接受狀態(tài)；必須同時是可接受狀態(tài)或不可接受狀態(tài)；(2)蔓延性條件蔓延性條件 對于所有輸入符號，狀態(tài)對于所有輸入符號，狀態(tài)s和狀態(tài)和狀態(tài)t必須轉換到必須轉換到等價的狀態(tài)里等價的狀態(tài)里(注：狀態(tài)注：狀態(tài)s對應有輸入對應有輸入a而狀態(tài)而狀態(tài)t無輸入無輸入a時，這兩個時，這兩個狀態(tài)是不等價的）狀態(tài)是不等價的）。46有關分割法所用的概念有關分割法所用的概念定義定義3.8 可區(qū)分可區(qū)分 若若DFA M中的兩個狀態(tài)中的兩個狀態(tài)s,t不等價，則這兩個狀態(tài)是可區(qū)別的。不等價，則這兩個狀態(tài)是可區(qū)別的。例如：終態(tài)和非終態(tài)是可區(qū)別的（讀出例如：

35、終態(tài)和非終態(tài)是可區(qū)別的（讀出）；）； 下圖中的狀態(tài)下圖中的狀態(tài)2與狀態(tài)與狀態(tài)3（讀出（讀出b字）；字）； 0124ba3aabbabab47分割法分割法(1)把把Q的終態(tài)和非終態(tài)分開，分成兩個子集的終態(tài)和非終態(tài)分開，分成兩個子集 終態(tài)組和非終態(tài)組和非終態(tài)組，形成基本分劃終態(tài)組，形成基本分劃；顯然，屬于這兩個不同子集的狀態(tài)；顯然，屬于這兩個不同子集的狀態(tài)是可區(qū)別的。是可區(qū)別的。(2)假定到某個時候假定到某個時候含有含有m個子集，記個子集，記=I(1), I(2), , I(m)，若存在一個輸入字符若存在一個輸入字符a使得使得Ia( i )不全包含在現(xiàn)行不全包含在現(xiàn)行的某個子集的某個子集I( j

36、)中，就將中，就將I( j )一分為二；至此把一分為二；至此把I( i )分成兩半，形成新的劃分成兩半，形成新的劃分分 new。48分割法（續(xù)）分割法（續(xù)） (3)重復上述過程重復上述過程(2)，直到，直到所含的子集不再增長為止，此所含的子集不再增長為止，此時得到最后的劃分時得到最后的劃分 finish；此時，此時， 中的所有子集已是不可再分的了。也就是說，同中的所有子集已是不可再分的了。也就是說，同個子集中的狀態(tài)都是互相等價的，而不同子集中的狀態(tài)則個子集中的狀態(tài)都是互相等價的，而不同子集中的狀態(tài)則是可區(qū)別的。是可區(qū)別的。 (4)對于對于 finish中的每一個子集，選取子集中的一個狀態(tài)代中的

37、每一個子集，選取子集中的一個狀態(tài)代表其它狀態(tài)，這個代表就是化簡了的表其它狀態(tài)，這個代表就是化簡了的DFA M的狀態(tài)。的狀態(tài)。例如：假定例如：假定I=S1, S2, S3這樣一個子集，則可選這樣一個子集，則可選S1代表這個代表這個子集，那么在原自動機中，凡導入到子集，那么在原自動機中，凡導入到S2, S3的弧都導入到的弧都導入到S1,然后把然后把S2, S3結點從原來的狀態(tài)集合中刪除，因為它們已成結點從原來的狀態(tài)集合中刪除，因為它們已成了一些多余的狀態(tài)（從開始狀態(tài)出發(fā)，任何輸入串也不能了一些多余的狀態(tài)（從開始狀態(tài)出發(fā)，任何輸入串也不能達到的狀態(tài)）。達到的狀態(tài)）。49對劃分的說明對劃分的說明例如：

38、假定例如：假定I( i )中的狀態(tài)中的狀態(tài)S1和和S2經經a弧分別到達狀態(tài)弧分別到達狀態(tài)t1和和t2，而而t1和和t2屬于現(xiàn)行屬于現(xiàn)行中的兩個不同子集，則將中的兩個不同子集，則將一分為二，一分為二，使得一半含有使得一半含有S1 ： I( i1 ) =S | S I( i1 )且且S經經a弧到達弧到達t1，則另一半含有則另一半含有S2 ： I( i2 ) = I( i ) I( i1);由于由于t1和和t2是可區(qū)別的，即存在一個字是可區(qū)別的，即存在一個字， t1將讀出將讀出而停于而停于終態(tài)，而終態(tài)，而t2或讀不出字或讀不出字或雖可讀出字或雖可讀出字但不到達終態(tài)，但不到達終態(tài)，或情況恰好相反。因而

39、字或情況恰好相反。因而字將將S1和和S2區(qū)別開來，也就是說，區(qū)別開來，也就是說， I( i1 )和和I( i2 )中的狀態(tài)是可區(qū)別中的狀態(tài)是可區(qū)別50若若I中含有原來的初態(tài)，則中含有原來的初態(tài)，則S1是是新初態(tài)新初態(tài)；若；若含有原來的終態(tài)，則含有原來的終態(tài)，則S1是是新終態(tài)新終態(tài)。 經過消除多余狀態(tài)和合并等價狀態(tài)而得到經過消除多余狀態(tài)和合并等價狀態(tài)而得到的的DFA M，便是最簡化的（包含最少狀態(tài)的），便是最簡化的（包含最少狀態(tài)的）DFA?；喓蟪鯌B(tài)和終態(tài)的確定化簡后初態(tài)和終態(tài)的確定51a134267=5aaaaaabbbbbbb例：化簡下圖中的例：化簡下圖中的DFA解：解：(1)把把M的狀態(tài)分

40、成兩組：的狀態(tài)分成兩組：1,2,3,4、5,6,7；52例：例：DFA化簡化簡 (2)考察考察5,6,7，由于，由于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 化簡了的

41、化簡了的DFA M為：為：53例：化簡后的例：化簡后的DFA化簡后的化簡后的DFAaa1346=5aabbbbba54例例思考題：將下列DFA M最小化。0124ba3aabbabab解：整個劃分為：解：整個劃分為：0,2、1 、3、4104a3abbabab0,1,2,34b:0,2,1,3,455例例將下圖將下圖DFA最小化。最小化。解：解：(1)把把M的狀態(tài)分成兩組：終結組的狀態(tài)分成兩組：終結組C、非終結組、非終結組A,B,D； (2)考慮考慮A,B,D，由于，由于A,B,D1=A,C，因此對，因此對A,B,D一分為一分為二，分成二，分成A、B,DABDC0110101ABC011010

42、56 例例(續(xù)續(xù))至此，整個集合含有三組：至此，整個集合含有三組：A、B,D、C。最后，令狀態(tài)最后，令狀態(tài)B代表代表B,D，將原來導入到，將原來導入到D的弧都導入到的弧都導入到B，并刪，并刪除除D。這樣，所得的化簡。這樣，所得的化簡DFA M為：為：ABC011010原因：B,D0 時B無出邊，D有出邊，不滿足蔓延性條件正確的劃分：A、B、C、D57例例化簡如下化簡如下DFA M1401101002037500161100解：整個劃分為：解：整個劃分為：0,1、2,5、3、4,7、6，用，用0,1,2,3,4分布分布代替子集代替子集0,1、2,5、3、4,7、6001210043110058

43、3.4 正規(guī)文法和有窮自動機間的轉換正規(guī)文法和有窮自動機間的轉換3.4.1 (1)正規(guī)文法正規(guī)文法GNFA M：構造規(guī)則構造規(guī)則： (a) 與與G中的中的VT相同；相同； (b) M中的中的Q與與G中的中的VN相同，即文法相同，即文法G中的每個非終結符中的每個非終結符生成自動機生成自動機M中的一個狀態(tài)，中的一個狀態(tài)，G的開始符號的開始符號S是是M的初態(tài)的初態(tài)；增增加一個新的狀態(tài)加一個新的狀態(tài)Z，作為接受狀態(tài)，作為接受狀態(tài)。 (c) 對產生式對產生式UaV，其中，其中a VT或或，U,VVN，構造，構造M的一個轉換函數的一個轉換函數t(U,a)=V； (d) 對產生式對產生式Ua，構造，構造M的

44、轉換函數的轉換函數t(U,a)=Z（終態(tài)（終態(tài)集）。集）。59正規(guī)文法正規(guī)文法GNFA M 例3.10 課本P69構造正規(guī)文法構造正規(guī)文法GS等價的等價的NFA M。 GS: S+N S-N Sd N Sd NdN Nd解：與文法解：與文法G等價的等價的NFA M如下圖：如下圖：SNF+d-ddt(S,+)=Nt(S,d)=Ft(S,-)=Nt(N,+d=Nt(S,d)=Nt(N,d)=Fd60正規(guī)文法正規(guī)文法GNFA M 例2構造正規(guī)文法構造正規(guī)文法GS等價的等價的NFA M。 GS: SaA SbB Sb AaB AbA BaS BbA B解：與文法解：與文法G等價的等價的NFA M如下圖

45、：如下圖：SaZABbbabab613.4.1 左線性文法左線性文法-NFA M 轉換規(guī)則轉換規(guī)則： (a) 文法的開始符號文法的開始符號S是是M的終態(tài)。的終態(tài)。 (b) 引入一個新的非終結符引入一個新的非終結符R作為初態(tài)結點。作為初態(tài)結點。 (c) 對于文法中的每一個形如對于文法中的每一個形如U-a的產生式，從初態(tài)的產生式，從初態(tài)結點畫一條弧到結點結點畫一條弧到結點U，且用，且用a標記該弧線。標記該弧線。 (d) 對于文法中的每一個形如對于文法中的每一個形如U-Va的產生式，從結的產生式，從結點點V畫一條弧到結點畫一條弧到結點U，且用，且用a標記該弧線。標記該弧線。623.4.1 左線性文法

46、左線性文法-NFA M 例例：GS: S-S1 S-A1 A-A0 A-0 RAS0011633.4.2 NFA M 正規(guī)文法正規(guī)文法G 轉換規(guī)則轉換規(guī)則： (a) 對轉換函數對轉換函數t(U,a)=V，寫成產生式，寫成產生式UaV； (b) 對終態(tài)對終態(tài)Z，增加產生式，增加產生式Z； (c) VN為為NFA所有狀態(tài)中的標記（所有狀態(tài)中的標記（Q），），VT為為NFA的的， NFA的初態(tài)就是開始符號的初態(tài)就是開始符號S。64例例例：給出與例：給出與NFA等價的正規(guī)文法等價的正規(guī)文法GAaDBbbaabCb解：與解：與NFA等價正規(guī)文法等價正規(guī)文法G=(VN, VT, P, S)=(A,B,C,

47、D,a,b, P, A)，其中其中P為：為： AaB AbD BbC CaA CbD C DaB DbD D 653.5 正規(guī)表達式與正規(guī)表達式與FA單詞的描述工具：正規(guī)文法單詞的描述工具：正規(guī)文法正規(guī)文法（正規(guī)文法（3型文法）的形式定義型文法）的形式定義 設設G=( VN, VT, P, S)為一文法，若為一文法，若G的任何產的任何產生式生式A 或或A B ，其中，其中A、B VN ， VT* 。66 正規(guī)文法的例子正規(guī)文法的例子例：例：“無符號實數無符號實數”定義定義 d | . | e d | . | e | d e | d | d | s d d | 其中其中s 正負符號正負符號+、6

48、73.5.1 單詞的描述工具單詞的描述工具正規(guī)式的定義正規(guī)式的定義正規(guī)式也叫正則表達式，用于描述稱為正規(guī)集的語言。正規(guī)式也叫正則表達式，用于描述稱為正規(guī)集的語言。定義定義3.9 字母表字母表上的正規(guī)式和正規(guī)集的遞歸定義為：上的正規(guī)式和正規(guī)集的遞歸定義為：(1)和和是是上的正規(guī)式，它們所代表的正規(guī)集為上的正規(guī)式，它們所代表的正規(guī)集為 ()；(2)任何任何a，a是是上的一個正規(guī)式，它所表示的正規(guī)集為上的一個正規(guī)式，它所表示的正規(guī)集為a；(3)假定假定e1與與e2都是都是上的正規(guī)式，它們所表示的正規(guī)集為上的正規(guī)式，它們所表示的正規(guī)集為L(e1)和和L(e2)，那么，那么(e1)、 e1| e2、 e

49、1 e2和和e1*也是正規(guī)式，它們所表示也是正規(guī)式，它們所表示的正規(guī)集分別為的正規(guī)集分別為 L(e1)、L(e1)L(e2)、 L(e1) L(e2)、 (L(e1) * (4)僅用有限次使用上述三步驟而定義的表達式方是僅用有限次使用上述三步驟而定義的表達式方是上的正規(guī)上的正規(guī)式，僅有這些正規(guī)式所表示的字集才是式，僅有這些正規(guī)式所表示的字集才是上的正規(guī)集。上的正規(guī)集。68正規(guī)式正規(guī)式運算符優(yōu)先關系運算符優(yōu)先關系 |(或或) (連接連接) 正規(guī)文法正規(guī)文法將將上的一個正規(guī)式上的一個正規(guī)式r，轉換為正規(guī)文法，轉換為正規(guī)文法G=( VN, VT, P, S).1.令令VT= 2. S-r , S為開

50、始符號為開始符號3. 若若x和和y都是正規(guī)式，則都是正規(guī)式，則 產生式產生式 重寫為：重寫為：r1. A-xy A-xB B-yr2. A-x*yA-xA A-y r3. A-x|y A-x A-yl不斷做變換，直到每個產生式右端最多只含一個不斷做變換，直到每個產生式右端最多只含一個VN 883.5.6 正規(guī)式正規(guī)式-正規(guī)文法正規(guī)文法l例例 將正規(guī)式將正規(guī)式R=a(a d) 轉換為相應的正規(guī)文法。轉換為相應的正規(guī)文法。 VT=a,d Sa(a d) r3. SaA AaAAdA A VN=S,Ar1. SaA A(a d) r2. A(a d)A A893.5.6 正規(guī)文法正規(guī)文法-正規(guī)式正規(guī)

51、式對對G= ( VN, VT, P, S), 存在一個存在一個 = VT上的正規(guī)式上的正規(guī)式e，使得，使得 L(R)=L(e) 。在此介紹在此介紹2種轉換方法：種轉換方法：一：一：1.令令 =VT2.轉換規(guī)則轉換規(guī)則 文法產生式文法產生式正規(guī)式正規(guī)式AxB ByA=xy AxA y A=x y Ax y A=x yl不斷做變換，直到只剩下一個不斷做變換，直到只剩下一個開始符號開始符號定義的產定義的產生式，且該產生式生式，且該產生式右端不含右端不含VN 903.5.6 正規(guī)文法正規(guī)文法-正規(guī)式正規(guī)式 例子例子例例 文法文法Gs:SaA AaA AdA Sa Aa Ad S=a(a d) (a d

52、) a =a(a d) (a d) =a(a d) ) 所以，所以，t=a(a d) 解答：解答： SaA a AaA a dA d A(a d)A (a d) A(a d) (a d)913.5.6 正規(guī)文法正規(guī)文法-正規(guī)式正規(guī)式二二.方程組求解法方程組求解法 p78 例例3.19 S-0A|1B|0|1 A-0S|1B|1 B-1S+0A解：寫出關于變量解：寫出關于變量S、A、B的正規(guī)方程組：的正規(guī)方程組： S=(0+1)+0A+1B (1) A=1+0S+1B (2) B=1S+0A (3)將將(3)代入代入(1)和和(2), 可得：可得： S=(0+1)+0A+1(1s+0A)=(0+

53、1)+(0+10)A+11S (6) A=1+0S+1(1S+0A)=1+10A+(0+11)S (7) 將將(7)重寫為重寫為A=aA+b的形式：的形式： A=10A+(1+(0+11)S) 則則A=(10)*(1+(0+11)S) 將將A代入代入(6), 得得S=0+1+(0+10)10*(1+(0+11)S)+11S S=(0+10)(10*)(0+11)+11)S+(0+10)(10*)1+0+1) 則：則： S= (0+10)(10*)(0+11)+11)* (0+10)(10*)1+0+1)92 3.6 DFA在計算機中的表示在計算機中的表示要在計算機中表示一個要在計算機中表示一個

54、DFA，只需表示它的映射，只需表示它的映射3.6.1 矩陣表示法矩陣表示法 例例3.21 映射映射t(q0,x1)=q1, t(q0,x2)=q3, t(q1,x1)=q2, t(q1,x2)=q0, t(q2,x1)=q3, t(q2,x2)=q2. 定義二維數組定義二維數組M=1,3, 2,0,3,2 x1X2q0q1q3q1q2q0q2q3q1q3q0q2933.6.2 表結構表結構l 在表結構中，每一個狀態(tài)對應一個表，表中包括在表結構中，每一個狀態(tài)對應一個表，表中包括狀態(tài)名，從該狀態(tài)發(fā)出的弧數、每條弧上的標記狀態(tài)名，從該狀態(tài)發(fā)出的弧數、每條弧上的標記（輸入字母）以及弧達到狀態(tài)所在表的首

55、地址。（輸入字母）以及弧達到狀態(tài)所在表的首地址。l 例例3.22 p81943.6.3 自動機的編程實現(xiàn)自動機的編程實現(xiàn) p820: if IS-Digit(T) then goto 2 else if (T=+) or (T=-) then goto 1 else if (T=.) then goto 3 else Error;1: if IS-Digit(T) then goto 2 else if (T=.) then goto 3 else Error;2: if IS-Digit(T) then goto 2 else if (T=.) then goto 4 else goto 5;3: if IS-Digit(T) then goto 4 else Error4: if IS-Digit(T) then goto 4 else Error5: halt 1d+-.0324dd.dd95第三章作業(yè)第三章作業(yè) p83-