計(jì)算機(jī)科學(xué)與技術(shù) 編譯原理第三章重點(diǎn)

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

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

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

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

5、接收：若掃描完輸入串，接收：若掃描完輸入串，且在一個(gè)終止?fàn)顟B(tài)上結(jié)且在一個(gè)終止?fàn)顟B(tài)上結(jié)束。束。阻塞：若掃描結(jié)束但未阻塞：若掃描結(jié)束但未停止在終止?fàn)顟B(tài)上；或停止在終止?fàn)顟B(tài)上；或者不能掃描完輸入串者不能掃描完輸入串（如遇不合法符號(hào)）。（如遇不合法符號(hào)）。不完全描述：某些狀態(tài)不完全描述：某些狀態(tài)對(duì)于某些輸入符號(hào)不存對(duì)于某些輸入符號(hào)不存在轉(zhuǎn)換。在轉(zhuǎn)換。練習(xí)練習(xí)：+34.567 .123 3.4.56= 80;0134256eniL字母字母字母字母數(shù)字?jǐn)?shù)字?jǐn)?shù)字= =；0124563L ine= 80; id , Line = , num, 80 ;, 數(shù)字?jǐn)?shù)字字母字母1 1= =0 0 03; ;1輸入符

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

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

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

9、”或或“”表示，終態(tài)結(jié)表示，終態(tài)結(jié)用雙圓圈表示或標(biāo)以用雙圓圈表示或標(biāo)以“+”。對(duì)。對(duì)t(q,a)=q指從狀態(tài)結(jié)指從狀態(tài)結(jié)q到狀到狀態(tài)結(jié)態(tài)結(jié)q畫標(biāo)記畫標(biāo)記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確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)DFA的表示（續(xù)）的表示（續(xù)）3.2.2 狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩

10、陣 矩陣的行表示狀態(tài)，列表示輸入字符，矩矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)的狀態(tài)行在輸入字符列下的新陣元素表示相應(yīng)的狀態(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 有關(guān)自動(dòng)機(jī)術(shù)語有關(guān)自動(dòng)機(jī)術(shù)語(1)道路：對(duì)于道路：對(duì)于*中的任何符號(hào)串中的任何符號(hào)串，

11、若存在一條從初態(tài)到，若存在一條從初態(tài)到某終態(tài)的路徑。某終態(tài)的路徑。(2)識(shí)別：道路上所有弧的標(biāo)記連接成的符號(hào)串等于識(shí)別：道路上所有弧的標(biāo)記連接成的符號(hào)串等于，則，則稱稱可為可為DFA M所識(shí)別（所接受）。所識(shí)別（所接受）。即若即若 *, t(q,)=P，其中，其中q為為DFA M的初始狀態(tài)，的初始狀態(tài)，PF（終態(tài)集）。（終態(tài)集）。若若M的初態(tài)結(jié)同時(shí)也是終態(tài)結(jié)，則空字的初態(tài)結(jié)同時(shí)也是終態(tài)結(jié)，則空字可為可為M所識(shí)別，所識(shí)別，即即qF, f(q, )=q(3)運(yùn)行：運(yùn)行： 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所識(shí)別（所接受）。所識(shí)別（所接受）。0123abbaaba, b15 3.2.4 有關(guān)確定有窮自動(dòng)機(jī)的結(jié)論有關(guān)確定有窮自動(dòng)機(jī)的結(jié)論 把把DFA M所能接受的所有符號(hào)串（符號(hào)串的所能接受的所有符號(hào)串（符號(hào)串的全體）記為全體）記為L(M)。 上的一個(gè)字集上的一個(gè)字集V*是正規(guī)的，當(dāng)且僅當(dāng)存是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)在一個(gè)上的確定有窮自動(dòng)

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

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

15、個(gè)狀態(tài)節(jié)可射出若干條弧和別的狀態(tài)節(jié)相連，且每條弧用的狀態(tài)節(jié)相連，且每條弧用*中的一個(gè)字（不一定要不中的一個(gè)字（不一定要不同的字且可以是空字同的字且可以是空字）作標(biāo)記（或稱輸入字）。整個(gè)）作標(biāo)記（或稱輸入字）。整個(gè)圖中至少含有一個(gè)初態(tài)節(jié)以及若干個(gè)（可以是圖中至少含有一個(gè)初態(tài)節(jié)以及若干個(gè)（可以是0個(gè)）終個(gè)）終態(tài)節(jié)。態(tài)節(jié)。 某些節(jié)既可以是初態(tài)節(jié)也可以是終態(tài)節(jié)。某些節(jié)既可以是初態(tài)節(jié)也可以是終態(tài)節(jié)。19例例題：一個(gè)題：一個(gè)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)圖也是一個(gè)如下狀態(tài)圖也是一個(gè)NFA0a,b1aabba,b2a,b21有關(guān)非確定有窮自動(dòng)機(jī)的術(shù)語有關(guān)非確定有窮自動(dòng)機(jī)的術(shù)語對(duì)于對(duì)于*中的任何一個(gè)串中的任何一個(gè)串t可被可被NFA M識(shí)別是指：識(shí)別是指：若對(duì)這個(gè)字（串）若對(duì)這個(gè)字（串）t存在一條從某個(gè)初態(tài)節(jié)到某一存在一條從某個(gè)初態(tài)節(jié)到某一個(gè)終態(tài)節(jié)的道路，且這條道路上所有弧的標(biāo)記字依個(gè)終態(tài)節(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接起來的字符串（不理睬那些標(biāo)記為序連接起來的字符串（不理睬那些標(biāo)記為的?。┑幕。┑扔诘扔趖，則，則t可識(shí)別（或可接受）可識(shí)別（或可接受）若若M的某些節(jié)點(diǎn)既是

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

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

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

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

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

22、A的狀態(tài)記錄該狀態(tài)的狀態(tài)記錄該狀態(tài)的集合。的集合。31將NDFA M=(Q, ,t,Q0,F) 轉(zhuǎn)換為DFA M=(Q, ,t,q0,F)的步驟： 1. M的狀態(tài)集Q是由M的狀態(tài)集Q的所有子集組成的。用p1,p2, ,pi表示Q的元素。2. 若p是M的一個(gè)終態(tài)，則M中的每一個(gè)包含p的狀態(tài),p,都是M的一個(gè)終態(tài)。3. 若S=S1,S2,Sj是M的初態(tài)，則S=S1,S2,Sj是M的初態(tài)。4. 令p1,p2,pn是M中的一個(gè)狀態(tài)，其中p1,p2,pn是M中的狀態(tài)。對(duì)某個(gè)輸入符號(hào)a，考慮M中的轉(zhuǎn)換函數(shù)：t(p1,a), t(p2,a), , t(pn,a)，按以下方法得到M的轉(zhuǎn)換函數(shù)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. 對(duì)M每一狀態(tài)和每個(gè)輸入符號(hào)a，重復(fù)步驟4.32利用狀態(tài)表將NDFA轉(zhuǎn)換為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弧轉(zhuǎn)換弧轉(zhuǎn)換 假定假定I是狀態(tài)集的一個(gè)子集，是狀態(tài)集的一個(gè)子集，a是是中的一個(gè)字符，定義中的一個(gè)字符，定義 Ia _closure(J

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

25、狀態(tài)圖如下：1526a4a73a8假定假定 I= _closure(1)1, 2從狀態(tài)集從狀態(tài)集I出發(fā)經(jīng)過一條出發(fā)經(jīng)過一條a弧而能到達(dá)的狀態(tài)結(jié)全體弧而能到達(dá)的狀態(tài)結(jié)全體J為為5, 3, 4；而而_closure(J) =5, 6, 2, 3, 8, 4, 7例例35NFA的確定化的確定化 從從NFA N (Q, , t, q0, F)構(gòu)造一個(gè)構(gòu)造一個(gè)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的開始符號(hào)（初態(tài)）；的開始符號(hào)（初態(tài)）； (5) F =qj, qk, qe，其中，其中qj, qk, qe Q且且qj, qk, qeF 36具體過程具體過程為了方便起見，令為了方便起見，令中只有中只有a,b兩個(gè)字母，即兩個(gè)字母，即a, b（1）構(gòu)造一張表，此表的每一行有三列，第一列為）構(gòu)造一張表，此表的每一行有三列，第一列為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）對(duì)未重復(fù)）對(duì)未重復(fù)Ia 、 Ib的新行重復(fù)上述過程的新行重復(fù)上述過程(2)、(3) ，直到所，直到所有第二列和第三列的子集全部在第一列中出現(xiàn)；有第二列和第三列的子集全部在第一列中出現(xiàn)； 上述過程必定在有限步

28、內(nèi)終止，因?yàn)樯鲜鲞^程必定在有限步內(nèi)終止，因?yàn)镹的狀態(tài)子集的個(gè)數(shù)的狀態(tài)子集的個(gè)數(shù)是有限的。我們也可將表看成狀態(tài)轉(zhuǎn)換矩陣，即把其中每個(gè)是有限的。我們也可將表看成狀態(tài)轉(zhuǎn)換矩陣，即把其中每個(gè)子集看成一個(gè)狀態(tài)，就可以由這張表唯一刻劃出一個(gè)確定的子集看成一個(gè)狀態(tài)，就可以由這張表唯一刻劃出一個(gè)確定的有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)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)構(gòu)造轉(zhuǎn)換矩陣構(gòu)造轉(zhuǎn)換矩陣39 接上頁接上頁(2)對(duì)表中所有的子集重新命名，其中對(duì)表中所有的子集重新命名，其中0是初態(tài)，是初態(tài)，4是終態(tài)。是終態(tài)。 對(duì)應(yīng)的對(duì)應(yīng)的DFA M：0124ba3aabbabab40例例題：將下圖確

30、定化：題：將下圖確定化：解：解：(1)構(gòu)造轉(zhuǎn)換矩陣構(gòu)造轉(zhuǎn)換矩陣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：求與右圖等價(jià)的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)轉(zhuǎn)換矩陣確定化后的狀態(tài)轉(zhuǎn)換矩陣xyq0q1q0q1q2q3q2q3q2q3q4q3q4q5q5q5q5q5433.3.6 消除不可達(dá)狀態(tài) 有窮自動(dòng)機(jī)的有窮自動(dòng)機(jī)的多余狀態(tài)多余狀態(tài)：是指這樣的狀態(tài)，從該自動(dòng)：是指這樣的狀態(tài)，從該自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能達(dá)到的那個(gè)狀態(tài)。機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能達(dá)到的那個(gè)狀態(tài)。 01S0S1S5S1S2

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

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

34、的條件：(1)一致性條件一致性條件 狀態(tài)狀態(tài)t,s必須同時(shí)是可接受狀態(tài)或不可接受狀態(tài)；必須同時(shí)是可接受狀態(tài)或不可接受狀態(tài)；(2)蔓延性條件蔓延性條件 對(duì)于所有輸入符號(hào)，狀態(tài)對(duì)于所有輸入符號(hào)，狀態(tài)s和狀態(tài)和狀態(tài)t必須轉(zhuǎn)換到必須轉(zhuǎn)換到等價(jià)的狀態(tài)里等價(jià)的狀態(tài)里(注：狀態(tài)注：狀態(tài)s對(duì)應(yīng)有輸入對(duì)應(yīng)有輸入a而狀態(tài)而狀態(tài)t無輸入無輸入a時(shí)，這兩個(gè)時(shí)，這兩個(gè)狀態(tài)是不等價(jià)的）狀態(tài)是不等價(jià)的）。46有關(guān)分割法所用的概念有關(guān)分割法所用的概念定義定義3.8 可區(qū)分可區(qū)分 若若DFA M中的兩個(gè)狀態(tài)中的兩個(gè)狀態(tài)s,t不等價(jià)，則這兩個(gè)狀態(tài)是可區(qū)別的。不等價(jià)，則這兩個(gè)狀態(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)分開，分成兩個(gè)子集的終態(tài)和非終態(tài)分開，分成兩個(gè)子集 終態(tài)組和非終態(tài)組和非終態(tài)組，形成基本分劃終態(tài)組，形成基本分劃；顯然，屬于這兩個(gè)不同子集的狀態(tài)；顯然，屬于這兩個(gè)不同子集的狀態(tài)是可區(qū)別的。是可區(qū)別的。(2)假定到某個(gè)時(shí)候假定到某個(gè)時(shí)候含有含有m個(gè)子集，記個(gè)子集，記=I(1), I(2), , I(m)，若存在一個(gè)輸入字符若存在一個(gè)輸入字符a使得使得Ia( i )不全包含在現(xiàn)行不全包含在現(xiàn)行的某個(gè)子集的某個(gè)子集I( j

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

37、每一個(gè)子集，選取子集中的一個(gè)狀態(tài)代表其它狀態(tài)，這個(gè)代表就是化簡(jiǎn)了的表其它狀態(tài)，這個(gè)代表就是化簡(jiǎn)了的DFA M的狀態(tài)。的狀態(tài)。例如：假定例如：假定I=S1, S2, S3這樣一個(gè)子集，則可選這樣一個(gè)子集，則可選S1代表這個(gè)代表這個(gè)子集，那么在原自動(dòng)機(jī)中，凡導(dǎo)入到子集，那么在原自動(dòng)機(jī)中，凡導(dǎo)入到S2, S3的弧都導(dǎo)入到的弧都導(dǎo)入到S1,然后把然后把S2, S3結(jié)點(diǎn)從原來的狀態(tài)集合中刪除，因?yàn)樗鼈円殉山Y(jié)點(diǎn)從原來的狀態(tài)集合中刪除，因?yàn)樗鼈円殉闪艘恍┒嘤嗟臓顟B(tài)（從開始狀態(tài)出發(fā)，任何輸入串也不能了一些多余的狀態(tài)（從開始狀態(tài)出發(fā)，任何輸入串也不能達(dá)到的狀態(tài)）。達(dá)到的狀態(tài)）。49對(duì)劃分的說明對(duì)劃分的說明例如：

38、假定例如：假定I( i )中的狀態(tài)中的狀態(tài)S1和和S2經(jīng)經(jīng)a弧分別到達(dá)狀態(tài)弧分別到達(dá)狀態(tài)t1和和t2，而而t1和和t2屬于現(xiàn)行屬于現(xiàn)行中的兩個(gè)不同子集，則將中的兩個(gè)不同子集，則將一分為二，一分為二，使得一半含有使得一半含有S1 ： I( i1 ) =S | S I( i1 )且且S經(jīng)經(jīng)a弧到達(dá)弧到達(dá)t1，則另一半含有則另一半含有S2 ： I( i2 ) = I( i ) I( i1);由于由于t1和和t2是可區(qū)別的，即存在一個(gè)字是可區(qū)別的，即存在一個(gè)字， t1將讀出將讀出而停于而停于終態(tài)，而終態(tài)，而t2或讀不出字或讀不出字或雖可讀出字或雖可讀出字但不到達(dá)終態(tài)，但不到達(dá)終態(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)。 經(jīng)過消除多余狀態(tài)和合并等價(jià)狀態(tài)而得到經(jīng)過消除多余狀態(tài)和合并等價(jià)狀態(tài)而得到的的DFA M，便是最簡(jiǎn)化的（包含最少狀態(tài)的），便是最簡(jiǎn)化的（包含最少狀態(tài)的）DFA。化簡(jiǎn)后初態(tài)和終態(tài)的確定化簡(jiǎn)后初態(tài)和終態(tài)的確定51a134267=5aaaaaabbbbbbb例：化簡(jiǎn)下圖中的例：化簡(jiǎn)下圖中的DFA解：解：(1)把把M的狀態(tài)分

40、成兩組：的狀態(tài)分成兩組：1,2,3,4、5,6,7；52例：例：DFA化簡(jiǎn)化簡(jiǎn) (2)考察考察5,6,7，由于，由于5,6,7a=4,7，因此對(duì)，因此對(duì)5,6,7一分為一分為二：二：5、6,7； (3) 考察考察1,2,3,4，由于，由于1,2,3,4a=1,4,6,7，因此對(duì)，因此對(duì)1,2,3,4一分為二：一分為二：1,2、3,4； (4)考察考察3,4，由于，由于3,4a=1,4，因此將，因此將3,4一分為二：一分為二：3、4；至此，整個(gè)劃分為：至此，整個(gè)劃分為：1,2、3 、4 、5 、6,7。用。用1，3，4，5，6分別來代替子集分別來代替子集1,2、3 、4 、5 、6,7 化簡(jiǎn)了的

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

42、56 例例(續(xù)續(xù))至此，整個(gè)集合含有三組：至此，整個(gè)集合含有三組：A、B,D、C。最后，令狀態(tài)最后，令狀態(tài)B代表代表B,D，將原來導(dǎo)入到，將原來導(dǎo)入到D的弧都導(dǎo)入到的弧都導(dǎo)入到B，并刪，并刪除除D。這樣，所得的化簡(jiǎn)。這樣，所得的化簡(jiǎn)DFA M為：為：ABC011010原因：B,D0 時(shí)B無出邊，D有出邊，不滿足蔓延性條件正確的劃分：A、B、C、D57例例化簡(jiǎn)如下化簡(jiǎn)如下DFA M1401101002037500161100解：整個(gè)劃分為：解：整個(gè)劃分為：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ī)文法和有窮自動(dòng)機(jī)間的轉(zhuǎn)換正規(guī)文法和有窮自動(dòng)機(jī)間的轉(zhuǎn)換3.4.1 (1)正規(guī)文法正規(guī)文法GNFA M：構(gòu)造規(guī)則構(gòu)造規(guī)則： (a) 與與G中的中的VT相同；相同； (b) M中的中的Q與與G中的中的VN相同，即文法相同，即文法G中的每個(gè)非終結(jié)符中的每個(gè)非終結(jié)符生成自動(dòng)機(jī)生成自動(dòng)機(jī)M中的一個(gè)狀態(tài)，中的一個(gè)狀態(tài)，G的開始符號(hào)的開始符號(hào)S是是M的初態(tài)的初態(tài)；增增加一個(gè)新的狀態(tài)加一個(gè)新的狀態(tài)Z，作為接受狀態(tài)，作為接受狀態(tài)。 (c) 對(duì)產(chǎn)生式對(duì)產(chǎn)生式UaV，其中，其中a VT或或，U,VVN，構(gòu)造，構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)的一個(gè)轉(zhuǎn)換函數(shù)t(U,a)=V； (d) 對(duì)產(chǎn)生式對(duì)產(chǎn)生式Ua，構(gòu)造，構(gòu)造M的

44、轉(zhuǎn)換函數(shù)的轉(zhuǎn)換函數(shù)t(U,a)=Z（終態(tài)（終態(tài)集）。集）。59正規(guī)文法正規(guī)文法GNFA M 例3.10 課本P69構(gòu)造正規(guī)文法構(gòu)造正規(guī)文法GS等價(jià)的等價(jià)的NFA M。 GS: S+N S-N Sd N Sd NdN Nd解：與文法解：與文法G等價(jià)的等價(jià)的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構(gòu)造正規(guī)文法構(gòu)造正規(guī)文法GS等價(jià)的等價(jià)的NFA M。 GS: SaA SbB Sb AaB AbA BaS BbA B解：與文法解：與文法G等價(jià)的等價(jià)的NFA M如下圖

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

46、左線性文法-NFA M 例例：GS: S-S1 S-A1 A-A0 A-0 RAS0011633.4.2 NFA M 正規(guī)文法正規(guī)文法G 轉(zhuǎn)換規(guī)則轉(zhuǎn)換規(guī)則： (a) 對(duì)轉(zhuǎn)換函數(shù)對(duì)轉(zhuǎn)換函數(shù)t(U,a)=V，寫成產(chǎn)生式，寫成產(chǎn)生式UaV； (b) 對(duì)終態(tài)對(duì)終態(tài)Z，增加產(chǎn)生式，增加產(chǎn)生式Z； (c) VN為為NFA所有狀態(tài)中的標(biāo)記（所有狀態(tài)中的標(biāo)記（Q），），VT為為NFA的的， NFA的初態(tài)就是開始符號(hào)的初態(tài)就是開始符號(hào)S。64例例例：給出與例：給出與NFA等價(jià)的正規(guī)文法等價(jià)的正規(guī)文法GAaDBbbaabCb解：與解：與NFA等價(jià)正規(guī)文法等價(jià)正規(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ī)表達(dá)式與正規(guī)表達(dá)式與FA單詞的描述工具：正規(guī)文法單詞的描述工具：正規(guī)文法正規(guī)文法（正規(guī)文法（3型文法）的形式定義型文法）的形式定義 設(shè)設(shè)G=( VN, VT, P, S)為一文法，若為一文法，若G的任何產(chǎn)的任何產(chǎn)生式生式A 或或A B ，其中，其中A、B VN ， VT* 。66 正規(guī)文法的例子正規(guī)文法的例子例：例：“無符號(hào)實(shí)數(shù)無符號(hào)實(shí)數(shù)”定義定義 d | . | e d | . | e | d e | d | d | s d d | 其中其中s 正負(fù)符號(hào)正負(fù)符號(hào)+、6

48、73.5.1 單詞的描述工具單詞的描述工具正規(guī)式的定義正規(guī)式的定義正規(guī)式也叫正則表達(dá)式，用于描述稱為正規(guī)集的語言。正規(guī)式也叫正則表達(dá)式，用于描述稱為正規(guī)集的語言。定義定義3.9 字母表字母表上的正規(guī)式和正規(guī)集的遞歸定義為：上的正規(guī)式和正規(guī)集的遞歸定義為：(1)和和是是上的正規(guī)式，它們所代表的正規(guī)集為上的正規(guī)式，它們所代表的正規(guī)集為 ()；(2)任何任何a，a是是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為上的一個(gè)正規(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)僅用有限次使用上述三步驟而定義的表達(dá)式方是僅用有限次使用上述三步驟而定義的表達(dá)式方是上的正規(guī)上的正規(guī)式，僅有這些正規(guī)式所表示的字集才是式，僅有這些正規(guī)式所表示的字集才是上的正規(guī)集。上的正規(guī)集。68正規(guī)式正規(guī)式運(yùn)算符優(yōu)先關(guān)系運(yùn)算符優(yōu)先關(guān)系 |(或或) (連接連接) 正規(guī)文法正規(guī)文法將將上的一個(gè)正規(guī)式上的一個(gè)正規(guī)式r，轉(zhuǎn)換為正規(guī)文法，轉(zhuǎn)換為正規(guī)文法G=( VN, VT, P, S).1.令令VT= 2. S-r , S為開

50、始符號(hào)為開始符號(hào)3. 若若x和和y都是正規(guī)式，則都是正規(guī)式，則 產(chǎn)生式產(chǎn)生式 重寫為：重寫為：r1. A-xy A-xB B-yr2. A-x*yA-xA A-y r3. A-x|y A-x A-yl不斷做變換，直到每個(gè)產(chǎn)生式右端最多只含一個(gè)不斷做變換，直到每個(gè)產(chǎn)生式右端最多只含一個(gè)VN 883.5.6 正規(guī)式正規(guī)式-正規(guī)文法正規(guī)文法l例例 將正規(guī)式將正規(guī)式R=a(a d) 轉(zhuǎn)換為相應(yīng)的正規(guī)文法。轉(zhuǎn)換為相應(yīng)的正規(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、式對(duì)對(duì)G= ( VN, VT, P, S), 存在一個(gè)存在一個(gè) = VT上的正規(guī)式上的正規(guī)式e，使得，使得 L(R)=L(e) 。在此介紹在此介紹2種轉(zhuǎn)換方法：種轉(zhuǎn)換方法：一：一：1.令令 =VT2.轉(zhuǎn)換規(guī)則轉(zhuǎn)換規(guī)則 文法產(chǎn)生式文法產(chǎn)生式正規(guī)式正規(guī)式AxB ByA=xy AxA y A=x y Ax y A=x yl不斷做變換，直到只剩下一個(gè)不斷做變換，直到只剩下一個(gè)開始符號(hào)開始符號(hào)定義的產(chǎn)定義的產(chǎn)生式，且該產(chǎn)生式生式，且該產(chǎn)生式右端不含右端不含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解：寫出關(guān)于變量解：寫出關(guān)于變量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在計(jì)算機(jī)中的表示在計(jì)算機(jī)中的表示要在計(jì)算機(jī)中表示一個(gè)要在計(jì)算機(jī)中表示一個(gè)

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. 定義二維數(shù)組定義二維數(shù)組M=1,3, 2,0,3,2 x1X2q0q1q3q1q2q0q2q3q1q3q0q2933.6.2 表結(jié)構(gòu)表結(jié)構(gòu)l 在表結(jié)構(gòu)中，每一個(gè)狀態(tài)對(duì)應(yīng)一個(gè)表，表中包括在表結(jié)構(gòu)中，每一個(gè)狀態(tài)對(duì)應(yīng)一個(gè)表，表中包括狀態(tài)名，從該狀態(tài)發(fā)出的弧數(shù)、每條弧上的標(biāo)記狀態(tài)名，從該狀態(tài)發(fā)出的弧數(shù)、每條弧上的標(biāo)記（輸入字母）以及弧達(dá)到狀態(tài)所在表的首

55、地址。（輸入字母）以及弧達(dá)到狀態(tài)所在表的首地址。l 例例3.22 p81943.6.3 自動(dòng)機(jī)的編程實(shí)現(xiàn)自動(dòng)機(jī)的編程實(shí)現(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-