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

第三章有窮自動(dòng)機(jī)要點(diǎn)：1.DFA和NFA的定義2.NFA→DFA的轉(zhuǎn)換；3.DFA的化簡(jiǎn)4.正規(guī)文法、正規(guī)式、有窮自動(dòng)機(jī)之間的相互轉(zhuǎn)換；編譯原理有窮自動(dòng)機(jī)

有窮自動(dòng)機(jī)（或有限自動(dòng)機(jī)）作為一種識(shí)別工具，它能正確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語(yǔ)言和正規(guī)式所表示的集合。引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具。分類：確定的有窮自動(dòng)機(jī)（DFA）

不確定的有窮自動(dòng)機(jī)（NFA）3.1概述有窮自動(dòng)機(jī)（FA）

有窮自動(dòng)機(jī)（FA，F(xiàn)initeAutomata）是一種有限離散數(shù)字系統(tǒng)的抽象數(shù)學(xué)模型。

這個(gè)系統(tǒng)具有有限數(shù)目的內(nèi)部“狀態(tài)”。

所謂狀態(tài)，是可以將事物區(qū)分開(kāi)的一種標(biāo)識(shí)。例如：數(shù)字電路（0，1），十字路口的紅綠燈等都是離散狀態(tài)系統(tǒng)，其狀態(tài)數(shù)目是有限的。連續(xù)狀態(tài)系統(tǒng)則如水庫(kù)的水位、室內(nèi)溫度變化等。

電梯的控制機(jī)制，不需要保存所有以前的服務(wù)要求，僅需記住當(dāng)前的層次、運(yùn)動(dòng)的方向以及未滿足的服務(wù)要求。

文本編輯程序和詞法分析程序是有限狀態(tài)系統(tǒng)，計(jì)算機(jī)本身和人的大腦也可看成有限狀態(tài)系統(tǒng)。有窮自動(dòng)機(jī)（FA）

數(shù)字系統(tǒng)：可以從一個(gè)狀態(tài)移動(dòng)到另一個(gè)狀態(tài)；每次狀態(tài)轉(zhuǎn)換，都上由當(dāng)前狀態(tài)及一組輸入符號(hào)確定的；可以輸出某些離散的值集。FA：一個(gè)狀態(tài)集合；狀態(tài)間的轉(zhuǎn)換規(guī)則；通過(guò)讀頭來(lái)掃描的一個(gè)輸入符號(hào)串。

讀頭：從左到右掃描符號(hào)串。移動(dòng)（掃描）是由狀態(tài)轉(zhuǎn)換規(guī)則來(lái)決定的。ddd;.dd+;輸入符號(hào)串一個(gè)FA的例子讀頭數(shù)字A數(shù)字+-.SGBH數(shù)字?jǐn)?shù)字..數(shù)字接收：若掃描完輸入串，且在一個(gè)終止?fàn)顟B(tài)上結(jié)束。阻塞：若掃描結(jié)束但未停止在終止?fàn)顟B(tài)上；或者不能掃描完輸入串（如遇不合法符號(hào)）。不完全描述：某些狀態(tài)對(duì)于某些輸入符號(hào)不存在轉(zhuǎn)換。練習(xí)：+34.567.1233.4.5=80;0134256eniL字母字母字母字母數(shù)字?jǐn)?shù)字?jǐn)?shù)字==；；0124563Line=80;id,‘Line’=,num,‘80’;,數(shù)字?jǐn)?shù)字字母字母11==0003;;1輸入符號(hào)串輸出有限控制器讀頭other3.2有窮自動(dòng)機(jī)的形式定義DFA:DeterministicFiniteAutomataNFA:NondeterministicFiniteAutomataDFA的定義定義3.1一個(gè)確定的有窮自動(dòng)機(jī)(DFA)M是一個(gè)五元組： M=(Q,Σ,t,q0,F

)(1)Q是一個(gè)非空有窮集合，它的每一個(gè)元素稱為一個(gè)狀態(tài)；(2)Σ是一個(gè)有窮字母表，它的每一個(gè)元素稱為一個(gè)輸入字符；Σ也稱為輸入符號(hào)字母表確定的有窮自動(dòng)機(jī)DFA的定義（續(xù)）

(3)

t是從Q×Σ到Q的一個(gè)單值映射；

t(q,a)=q’，其中q,q’∈Q

說(shuō)明：當(dāng)前狀態(tài)為q

，輸入字符a時(shí)，將轉(zhuǎn)換到下一個(gè)狀態(tài)q’

，把q’稱為q的一個(gè)后繼狀態(tài)。DFA的確定性就表現(xiàn)在t是單值函數(shù)，即對(duì)任意狀態(tài)q∈Q，輸入符號(hào)a∈Σ，t(q,a)唯一確定一個(gè)狀態(tài)。(4)q0∈Q，是唯一的初態(tài)；(5)F是Q的子集，是一個(gè)終態(tài)集，終態(tài)也稱為可接收狀態(tài)或結(jié)束狀態(tài)。確定的有窮自動(dòng)機(jī)DFA的表示

3.2.1狀態(tài)轉(zhuǎn)換圖設(shè)DFA有m個(gè)狀態(tài)，n個(gè)輸入字符，那么這個(gè)圖含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多有n條箭弧射出和別的結(jié)點(diǎn)相連接，每條弧用Σ中的一個(gè)不同輸入符號(hào)作記號(hào)。整個(gè)圖含有唯一的一個(gè)初態(tài)和若干個(gè)（可以0個(gè)）終態(tài)結(jié)。習(xí)慣上，初態(tài)結(jié)可以用“=>”或“－>”表示，終態(tài)結(jié)用雙圓圈表示或標(biāo)以“+”。對(duì)t(q,a)=q’指從狀態(tài)結(jié)q到狀態(tài)結(jié)q’畫(huà)標(biāo)記a的弧。

例１題：DFAM=({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解：該DFAM的狀態(tài)圖：0123abbaaba,b確定的有窮自動(dòng)機(jī)DFA的表示（續(xù)）3.2.2狀態(tài)轉(zhuǎn)換矩陣

矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)的狀態(tài)行在輸入字符列下的新的狀態(tài)，即t(k,a)的值。例２（題同１）解：該DFAM的矩陣表示狀態(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)=33.2.3有關(guān)自動(dòng)機(jī)術(shù)語(yǔ)(1)道路：對(duì)于Σ*中的任何符號(hào)串α，若存在一條從初態(tài)到某終態(tài)的路徑。(2)識(shí)別：道路上所有弧的標(biāo)記連接成的符號(hào)串等于α，則稱α可為DFAM所識(shí)別（所接受）。即若α∈Σ*,t(q,α)=P，其中q為DFAM的初始狀態(tài)，P∈F（終態(tài)集）。若M的初態(tài)結(jié)同時(shí)也是終態(tài)結(jié)，則空字ε可為M所識(shí)別，即q∈F,f(q,ε)=q(3)運(yùn)行：

t(q,α1α2)=t(t(q,α1),α2)，其中q∈Q，α1α2為輸入字符串，且α1∈Σ，α1α2∈Σ*例３解：∵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的DFAM所識(shí)別（所接受）。0123abbaaba,b3.2.4有關(guān)確定有窮自動(dòng)機(jī)的結(jié)論

把DFAM所能接受的所有符號(hào)串（符號(hào)串的全體）記為L(zhǎng)(M)。Σ上的一個(gè)字集V∈Σ*是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)Σ上的確定有窮自動(dòng)機(jī)M，使得L(M)=V。有限自動(dòng)機(jī)識(shí)別的語(yǔ)言例子

例：下圖中的自動(dòng)機(jī)所能識(shí)別的語(yǔ)言是什么？q0q2q1q3abbaba

定義3.4

一個(gè)不確定的有窮自動(dòng)機(jī)NFAN也是一個(gè)五元組： M=(Q,Σ,t,q0,F

)(1)Q是一個(gè)有窮集合，它的每一個(gè)元素稱為一個(gè)狀態(tài)；(2)Σ是一個(gè)有窮字母表，它的每一個(gè)元素稱為一個(gè)輸入字符；Σ也稱為輸入符號(hào)字母表(3)t是一個(gè)Q×Σ*到Q的子集的映射：

t:Q×Σ*→2Q

(4)q0是Q的子集，是非空的初態(tài)集；(5)F是Q的子集，是一個(gè)終態(tài)集，也稱可接收狀態(tài)或結(jié)束狀態(tài)。3.2.5不確定的有窮自動(dòng)機(jī)(NFA)的定義NFA的表示

用狀態(tài)轉(zhuǎn)換圖（∵t是多值函數(shù)）

由NFA的定義，可把一個(gè)含有m個(gè)狀態(tài)和n個(gè)輸入字符的NFA表示如下：圖中有m個(gè)狀態(tài)節(jié)，對(duì)每個(gè)狀態(tài)節(jié)可射出若干條弧和別的狀態(tài)節(jié)相連，且每條弧用Σ*中的一個(gè)字（不一定要不同的字且可以是空字ε）作標(biāo)記（或稱輸入字）。整個(gè)圖中至少含有一個(gè)初態(tài)節(jié)以及若干個(gè)（可以是0個(gè)）終態(tài)節(jié)。某些節(jié)既可以是初態(tài)節(jié)也可以是終態(tài)節(jié)。例４題：一個(gè)NFAM＝({q0,q1}，{0,1}，t，q0，{q1})，其中

t(q0,0)={q0,q1},t(q0,1)={q1},

t(q1,0)=Φ,t(q1,1)={q0,q1},解：其狀態(tài)圖如下：q00q10111例５如下?tīng)顟B(tài)圖也是一個(gè)NFA0a,b1aabba,b2a,bε有關(guān)非確定有窮自動(dòng)機(jī)的術(shù)語(yǔ)

對(duì)于Σ*中的任何一個(gè)串t可被NFAM識(shí)別是指：若對(duì)這個(gè)字（串）t存在一條從某個(gè)初態(tài)節(jié)到某一個(gè)終態(tài)節(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接起來(lái)的字符串（不理睬那些標(biāo)記為ε的?。┑扔趖，則t可識(shí)別（或可接受）若M的某些節(jié)點(diǎn)既是初態(tài)節(jié)也是終態(tài)節(jié)，或存在一條從某個(gè)初態(tài)節(jié)到某個(gè)終態(tài)節(jié)的ε道路，則空字ε可為M所識(shí)別（所接受）。NFA和DFA的關(guān)系

DFA是NFA的一個(gè)特例。

對(duì)于每個(gè)NFAM，存在一個(gè)DFAM’，使得L(M)=L(M’)

對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)M和M’，如L(M)=L(M’)則稱M和M’是等價(jià)的。如果M僅通過(guò)重新標(biāo)記它的狀態(tài)，就能轉(zhuǎn)換成M’，則M和M’稱為同構(gòu)的。對(duì)于每一個(gè)NFAM，存在一個(gè)等價(jià)的、具有最少狀態(tài)個(gè)數(shù)的DFAM’，對(duì)于其它的DFAM”，若M”的狀態(tài)個(gè)數(shù)與M’相同且等價(jià)于M’，則必然有M”與M’同構(gòu)，即：M’在結(jié)構(gòu)上是唯一的。3.3NFA→DFA的轉(zhuǎn)換（NFA的確定化）

通過(guò)以下步驟，可以將一個(gè)NFA轉(zhuǎn)換為等價(jià)的DFA：1.尋找并消除空移環(huán)路；2.消除余下的空移；3.確定化–子集法、造表法；4.DFA的最小化—構(gòu)造狀態(tài)集合的劃分3.3.1NFA中空移環(huán)路的尋找和消除空移環(huán)路：

一個(gè)空移環(huán)路，是一個(gè)從狀態(tài)A開(kāi)始，并以狀態(tài)A結(jié)束的空移動(dòng)序列。εq1q2εq1q2εq3εq1q2εq3εqnε……ε消除方法：合并環(huán)路上的節(jié)點(diǎn)為新節(jié)點(diǎn)。若含初態(tài)，則新節(jié)點(diǎn)為初態(tài)。若含終態(tài)，則新節(jié)點(diǎn)為終態(tài)。課本P53

例3.43.3.2NFA的消除空移εABa1q1q2qna2an…εABa1q1q2qna2an…a1ana2εε消除方法：刪除ε弧，產(chǎn)生新弧。若A為初態(tài)，則B結(jié)點(diǎn)也為初態(tài)。若B為終態(tài)，則A結(jié)點(diǎn)也為終態(tài)。3.3.3利用狀態(tài)轉(zhuǎn)換表消除空移首先找出直接經(jīng)由一個(gè)空移到達(dá)某個(gè)終態(tài)的所有狀態(tài)。每找到這樣一個(gè)狀態(tài)，標(biāo)記為終態(tài)。然后，考慮消除與未被標(biāo)記為終態(tài)的那些狀態(tài)相關(guān)的空移。對(duì)表中每一個(gè)具有射出?連線的狀態(tài)繼續(xù)按上述方式處理，直到狀態(tài)表不再變動(dòng)為止。從表中刪除?列和沒(méi)有任何元素的空行，便得到一個(gè)不含空移的狀態(tài)轉(zhuǎn)換表。+-.d?SAAAA[B,C]EBBFCDCDDFEGEFGHHHF表3.2圖3.4中NDFA標(biāo)記狀態(tài)后的情況+-.dSAAG[B,C,E]AG[B,C,E]BBCDCDDEGEGHHH表3.3刪除空移后的狀態(tài)轉(zhuǎn)換圖3.3.4NFA的確定化——子集法

一個(gè)例子(無(wú)空移)p55圖3.9

介紹一種稱子集法的算法來(lái)將NFA轉(zhuǎn)換成接收同樣語(yǔ)言的DFA。

算法的基本思想是：把DFA中的每一個(gè)狀態(tài)對(duì)應(yīng)NFA中的一組狀態(tài)。即由于NFA中的t是多值的，所以在讀入一個(gè)輸入符號(hào)后可能達(dá)到的狀態(tài)是集合，而子集法就是用DFA的狀態(tài)記錄該狀態(tài)的集合。將NDFAM=(Q,Σ,t,Q0,F)轉(zhuǎn)換為DFAM’=(Q’,Σ’,t’,q0,F’)的步驟：

M’的狀態(tài)集Q’是由M的狀態(tài)集Q的所有子集組成的。用[p1,p2,…,pi]表示Q’的元素。若p是M的一個(gè)終態(tài)，則M’中的每一個(gè)包含p的狀態(tài)[…,p,…]都是M’的一個(gè)終態(tài)。若S={S1,S2,…,Sj}是M的初態(tài)，則S’=[S1,S2,…,Sj]是M’的初態(tài)。令[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(p1,a)Ut(p2,a)U…Ut(pn,a)={q1,q2,…,qr}b.置t’([p1,p2,…,pn],a)=[q1,q2,…,qr]對(duì)M’每一狀態(tài)和每個(gè)輸入符號(hào)a，重復(fù)步驟4.利用狀態(tài)表將NDFA轉(zhuǎn)換為DFA。以表3.3為例+-.dSAAG[B,C,E]AG[B,C,E]BBCDCDDEGEGHHH[B,C,E][D,G][B,C,E]新?tīng)顟B(tài)[D,G][D,H]新?tīng)顟B(tài)[D,H][D,H]新?tīng)顟B(tài)3.3.5確定化-造表法（2）Move(I,a)——狀態(tài)集合I的a弧轉(zhuǎn)換

假定I是狀態(tài)集的一個(gè)子集，a是Σ中的一個(gè)字符，定義Ia

＝ε_(tái)closure(J)其中J是所有那些可從I中的某一狀態(tài)出發(fā)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)結(jié)的全體。

(3)Ia＝ε_(tái)closure(Move(I,a))（1）ε_(tái)closure(I)——狀態(tài)集合I的ε閉包(等價(jià)狀態(tài)集)

設(shè)I是狀態(tài)集的一個(gè)子集，ε_(tái)closure(I)定義為：a.若S∈I，則S∈ε_(tái)closure(I)；b.若S∈I，那么從S出發(fā)經(jīng)過(guò)任意ε弧而能到達(dá)的任意狀態(tài)S’都屬于ε_(tái)closure(I)；1.有關(guān)定義題：有一個(gè)狀態(tài)圖如下：1526aεε4a7εε3a8ε假定I=ε_(tái)closure(1)＝{1,2}從狀態(tài)集I出發(fā)經(jīng)過(guò)一條a弧而能到達(dá)的狀態(tài)結(jié)全體J為{5,3,4}；而ε_(tái)closure(J)={5,6,2,3,8,4,7}例NFA的確定化

從NFAN＝(Q,Σ,t,q0,F)構(gòu)造一個(gè)DFAM＝(Q’,Σ,t’,q0’,F’)，其中(1)Q’是由Q一些子集組成；(2)M與N的輸入字母表相同，都是Σ；(3)t’定義：t’([q1,q2,…,qj],a)=[q1’,q2’,…,qi’]，其中ε_(tái)closure(move([q1,q2,…,qj],a))=[q1’,q2’,…,qi’](4)q0’=ε_(tái)closure(q0)為M的開(kāi)始符號(hào)（初態(tài)）；(5)F’={[qj’,qk’,…,qe’]，其中[qj’,qk’,…,qe’]Q’且[qj’,qk’,…,qe’]∩F≠Φ

}具體過(guò)程為了方便起見(jiàn)，令Σ中只有a,b兩個(gè)字母，即Σ＝{a,b}（1）構(gòu)造一張表，此表的每一行有三列，第一列為I，第二列為Ia，第二列為Ib。即IIaIbε_(tái)closure(q0)首先置該表的第一列為ε_(tái)closure(q0)。（2）一般而言，若某一行的第一列的狀態(tài)子集已確定，例如記為I，則可以求出Ia和Ib

；具體過(guò)程（續(xù)）

（3）檢查Ia和Ib是否已在表的第一列中出現(xiàn)，把未曾出現(xiàn)者填入到后面空行的第一列位置上。

（4）對(duì)未重復(fù)Ia

、Ib的新行重復(fù)上述過(guò)程(2)、(3)，直到所有第二列和第三列的子集全部在第一列中出現(xiàn)；

上述過(guò)程必定在有限步內(nèi)終止，因?yàn)镹的狀態(tài)子集的個(gè)數(shù)是有限的。我們也可將表看成狀態(tài)轉(zhuǎn)換矩陣，即把其中每個(gè)子集看成一個(gè)狀態(tài)，就可以由這張表唯一刻劃出一個(gè)確定的有窮自動(dòng)機(jī)DFA。其初態(tài)就是該表的第一行第一列的ε_(tái)closure(q0)，終態(tài)就是那些含有F的子集。例題：將下圖NFAN確定化。12εεbεε3a7ε0ε45b6εε8a910bIIaIbSab{0,1,2,4,7}{1,2,3,4,6,7,8}{1,2,4,5,6,7}012{1,2,3,4,6,7,8}{1,2,3,4,6,7,8}{1,2,4,5,6,7,9}113{1,2,4,5,6,7}{1,2,3,4,6,7,8}{1,2,4,5,6,7}212{1,2,4,5,6,7,9}{1,2,3,4,6,7,8}{1,2,4,5,6,7,10}314{1,2,4,5,6,7,10}{1,2,3,4,6,7,8}{1,2,4,5,6,7}412解：(1)構(gòu)造轉(zhuǎn)換矩陣

接上頁(yè)(2)對(duì)表中所有的子集重新命名，其中0是初態(tài)，4是終態(tài)?！鄬?duì)應(yīng)的DFAM：0124ba3aabbabab例題：將下圖確定化：解：(1)構(gòu)造轉(zhuǎn)換矩陣II0I1S01{s,x,y}{w}{s,x,y}ABA{w}{}{y,s,x,z}BC{s,x,y,z}{w,s,x,y}{s,x,y}CDA{w,s,x,y}{w}{s,x,y,z}DBCsyxwz1ε0ε101ε接上頁(yè)∴DFAM為：ABDC0110101例子3.7：求與右圖等價(jià)的DFA=(Q’,Σ,t’,q0’,F’)

Σ={x,y}Q’={[q0],[q1],[q2],[q3],[q0,q1],…,[q0,q1,q2,q3]}F’={[q3],[q0,q3],[q1,q3],[q2,q3],…,…,[q0,q1,q2,q3]}xy[q0][q1,q2][q0][q1,q2][q0,q3][q1,q2,q3][q0,q3][q1,q2,q3][q0,q3][q1,q2,q3][q0,q1,q3][q1,q2,q3][q0,q1,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3].確定化后的狀態(tài)轉(zhuǎn)換矩陣xy[q0’][q1’][q0’][q1’][q2’][q3’][q2’][q3’][q2’][q3’][q4’][q3’][q4’][q5’][q5’][q5’][q5’][q5’]3.3.6消除不可達(dá)狀態(tài)

有窮自動(dòng)機(jī)的多余狀態(tài)：是指這樣的狀態(tài)，從該自動(dòng)機(jī)的開(kāi)始狀態(tài)出發(fā)，任何輸入串也不能達(dá)到的那個(gè)狀態(tài)。

01S0S1S5S1S2S7S2S2S5S3S5S7S4S5S6S5S3S1S6S8S0S7S0S1S8S3S63.3.7DFA的化簡(jiǎn)

對(duì)已求得的DFA，可以進(jìn)一步將其化簡(jiǎn)，即求最小DFA。也就是對(duì)于任意給定的DFAM構(gòu)造另一個(gè)DFAM’，使L(M)=L(M’)，且DFAM’的狀態(tài)個(gè)數(shù)少于DFAM的狀態(tài)個(gè)數(shù)。

消除多余狀態(tài)DFAM狀態(tài)最少化的過(guò)程：

把M的狀態(tài)集分割成一些不相交的子集，使得任何不同的兩個(gè)子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的。有關(guān)分割法所用的概念定義3.7

等價(jià)

設(shè)s,t是M的兩個(gè)不同的狀態(tài)，s,t等價(jià)的意思是：如果從狀態(tài)s出發(fā)能讀出某個(gè)字α而停于終態(tài)，那么同樣從t出發(fā)也能讀出同一個(gè)字α而停于終態(tài)；反之，若能從t出發(fā)讀出某個(gè)字α而停于終態(tài)，那么同樣從s出發(fā)也能讀出字α而停于終態(tài)。

等價(jià)的條件：(1)一致性條件——狀態(tài)t,s必須同時(shí)是可接受狀態(tài)或不可接受狀態(tài)；(2)蔓延性條件——對(duì)于所有輸入符號(hào)，狀態(tài)s和狀態(tài)t必須轉(zhuǎn)換到等價(jià)的狀態(tài)里(注：狀態(tài)s對(duì)應(yīng)有輸入a而狀態(tài)t無(wú)輸入a時(shí)，這兩個(gè)狀態(tài)是不等價(jià)的）。有關(guān)分割法所用的概念定義3.8可區(qū)分

若DFAM中的兩個(gè)狀態(tài)s,t不等價(jià)，則這兩個(gè)狀態(tài)是可區(qū)別的。例如：終態(tài)和非終態(tài)是可區(qū)別的（讀出ε）；

下圖中的狀態(tài)2與狀態(tài)3（讀出b字）；

0124ba3aabbabab分割法(1)把Q的終態(tài)和非終態(tài)分開(kāi)，分成兩個(gè)子集——終態(tài)組和非終態(tài)組，形成基本分劃П；顯然，屬于這兩個(gè)不同子集的狀態(tài)是可區(qū)別的。(2)假定到某個(gè)時(shí)候П含有m個(gè)子集，記П={I(1),I(2),……,I(m)}，若存在一個(gè)輸入字符a使得Ia(i)不全包含在現(xiàn)行П的某個(gè)子集I(j)中，就將I(j)一分為二；至此把I(i)分成兩半，形成新的劃分П

new。分割法（續(xù)）

(3)重復(fù)上述過(guò)程(2)，直到П所含的子集不再增長(zhǎng)為止，此時(shí)得到最后的劃分П

finish；此時(shí)，П中的所有子集已是不可再分的了。也就是說(shuō)，同個(gè)子集中的狀態(tài)都是互相等價(jià)的，而不同子集中的狀態(tài)則是可區(qū)別的。(4)對(duì)于П

finish中的每一個(gè)子集，選取子集中的一個(gè)狀態(tài)代表其它狀態(tài)，這個(gè)代表就是化簡(jiǎn)了的DFAM’的狀態(tài)。例如：假定I={S1,S2,S3}這樣一個(gè)子集，則可選S1代表這個(gè)子集，那么在原自動(dòng)機(jī)中，凡導(dǎo)入到S2,S3的弧都導(dǎo)入到S1,然后把S2,S3結(jié)點(diǎn)從原來(lái)的狀態(tài)集合中刪除，因?yàn)樗鼈円殉闪艘恍┒嘤嗟臓顟B(tài)（從開(kāi)始狀態(tài)出發(fā)，任何輸入串也不能達(dá)到的狀態(tài)）。對(duì)劃分的說(shuō)明例如：假定I(i)中的狀態(tài)S1和S2經(jīng)a弧分別到達(dá)狀態(tài)t1和t2，而t1和t2屬于現(xiàn)行П中的兩個(gè)不同子集，則將П一分為二，使得一半含有S1

：I(i1)={S|S∈I(i1)且S經(jīng)a弧到達(dá)t1}，則另一半含有S2

：I(i2)=I(i)

－I(i1);由于t1和t2是可區(qū)別的，即存在一個(gè)字α，t1將讀出α而停于終態(tài)，而t2或讀不出字α或雖可讀出字α但不到達(dá)終態(tài)，或情況恰好相反。因而字α將S1和S2區(qū)別開(kāi)來(lái)，也就是說(shuō)，I(i1)和I(i2)中的狀態(tài)是可區(qū)別若I中含有原來(lái)的初態(tài)，則S1是新初態(tài)；若含有原來(lái)的終態(tài)，則S1是新終態(tài)。經(jīng)過(guò)消除多余狀態(tài)和合并等價(jià)狀態(tài)而得到的DFAM’，便是最簡(jiǎn)化的（包含最少狀態(tài)的）DFA?；?jiǎn)后初態(tài)和終態(tài)的確定a134267=>5aaaaaabbbbbbb例：化簡(jiǎn)下圖中的DFA解：(1)把M的狀態(tài)分成兩組：{1,2,3,4}、{5,6,7}；例：DFA化簡(jiǎn)(2)考察{5,6,7}，由于{5,6,7}a={4,7}，因此對(duì){5,6,7}一分為二：{5}、{6,7}；(3)考察{1,2,3,4}，由于{1,2,3,4}a={1,4,6,7}，因此對(duì){1,2,3,4}一分為二：{1,2}、{3,4}；(4)考察{3,4}，由于{3,4}a={1,4}，因此將{3,4}一分為二：{3}、{4}；至此，整個(gè)劃分為：{1,2}、{3}、{4}、{5}、{6,7}。用1，3，4，5，6分別來(lái)代替子集{1,2}、{3}、{4}、{5}、{6,7}∴化簡(jiǎn)了的DFAM’為：例：化簡(jiǎn)后的DFA化簡(jiǎn)后的DFAaa1346=>5aabbbbba例思考題：將下列DFAM最小化。0124ba3aabbabab解：整個(gè)劃分為：{0,2}、{1}、{3}、{4}104a3abbabab{0,1,2,3}{4}b:{0,2},{1},{3},{4}例將下圖DFA最小化。解：(1)把M的狀態(tài)分成兩組：終結(jié)組{C}、非終結(jié)組{A,B,D}；(2)考慮{A,B,D}，由于{A,B,D}1={A,C}，因此對(duì){A,B,D}一分為二，分成{A}、{B,D}ABDC0110101ABC011010

例(續(xù))至此，整個(gè)集合含有三組：{A}、{B,D}、{C}。最后，令狀態(tài)B代表{B,D}，將原來(lái)導(dǎo)入到D的弧都導(dǎo)入到B，并刪除D。這樣，所得的化簡(jiǎn)DFAM’為：ABC011010原因：{B,D}0時(shí)B無(wú)出邊，D有出邊，不滿足蔓延性條件正確的劃分：{A}、{B}、{C}、{D}例化簡(jiǎn)如下DFAM1401101002037500161100解：整個(gè)劃分為：{0,1}、{2,5}、{3}、{4,7}、{6}，用0,1,2,3,4分布代替子集{0,1}、{2,5}、{3}、{4,7}、{6}00121004311003.4正規(guī)文法和有窮自動(dòng)機(jī)間的轉(zhuǎn)換3.4.1(1)正規(guī)文法G→NFAM：構(gòu)造規(guī)則：

(a)Σ與G中的VT相同；(b)M中的Q與G中的VN相同，即文法G中的每個(gè)非終結(jié)符生成自動(dòng)機(jī)M中的一個(gè)狀態(tài)，G的開(kāi)始符號(hào)S是M的初態(tài)；增加一個(gè)新的狀態(tài)Z，作為接受狀態(tài)。

(c)對(duì)產(chǎn)生式U→aV，其中a∈VT或ε，U,V∈VN，構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)t(U,a)=V；(d)對(duì)產(chǎn)生式U→a，構(gòu)造M的轉(zhuǎn)換函數(shù)t(U,a)=Z（終態(tài)集）。正規(guī)文法G→NFAM

例3.10

課本P69構(gòu)造正規(guī)文法G[S]等價(jià)的NFAM。G[S]:S→+NS→-NS→dNS→dN→dNN→d解：與文法G等價(jià)的NFAM如下圖：SNF+d-ddt(S,+)=Nt(S,d)=Ft(S,-)=Nt(N,+d=Nt(S,d)=Nt(N,d)=Fd正規(guī)文法G→NFAM

例2構(gòu)造正規(guī)文法G[S]等價(jià)的NFAM。G[S]:S→aAS→bBS→bA→aBA→bAB→aSB→bAB→ε解：與文法G等價(jià)的NFAM如下圖：SaZABbbababε3.4.1左線性文法->NFAM

轉(zhuǎn)換規(guī)則：

(a)文法的開(kāi)始符號(hào)S是M的終態(tài)。(b)引入一個(gè)新的非終結(jié)符R作為初態(tài)結(jié)點(diǎn)。(c)對(duì)于文法中的每一個(gè)形如U->a的產(chǎn)生式，從初態(tài)結(jié)點(diǎn)畫(huà)一條弧到結(jié)點(diǎn)U，且用a標(biāo)記該弧線。(d)對(duì)于文法中的每一個(gè)形如U->Va的產(chǎn)生式，從結(jié)點(diǎn)V畫(huà)一條弧到結(jié)點(diǎn)U，且用a標(biāo)記該弧線。3.4.1左線性文法->NFAM

例：G[S]:S->S1S->A1A->A0A->0

RAS00113.4.2NFAM→正規(guī)文法G

轉(zhuǎn)換規(guī)則：

(a)對(duì)轉(zhuǎn)換函數(shù)t(U,a)=V，寫(xiě)成產(chǎn)生式U→aV；(b)對(duì)終態(tài)Z，增加產(chǎn)生式Z→ε；(c)VN為NFA所有狀態(tài)中的標(biāo)記（Q），VT為NFA的Σ，NFA的初態(tài)就是開(kāi)始符號(hào)S。例例：給出與NFA等價(jià)的正規(guī)文法GAaDBbbaabCb解：與NFA等價(jià)正規(guī)文法G=(VN,VT,P,S)=({A,B,C,D},{a,b},P,A)，其中P為：A→aBA→bDB→bCC→aAC→bDC→εD→aBD→bDD→ε3.5正規(guī)表達(dá)式與FA單詞的描述工具：正規(guī)文法正規(guī)文法（3型文法）的形式定義

設(shè)G=(VN,VT,P,S)為一文法，若G的任何產(chǎn)生式A→α或A→αB，其中A、B∈VN

，α∈VT*

。

正規(guī)文法的例子例：“無(wú)符號(hào)實(shí)數(shù)”定義<無(wú)符號(hào)實(shí)數(shù)>→d<余留無(wú)符號(hào)數(shù)>|.<十進(jìn)小數(shù)>|e<指數(shù)部分><余留無(wú)符號(hào)數(shù)>→d<余留無(wú)符號(hào)數(shù)>|.<十進(jìn)小數(shù)>|e<指數(shù)部分>|ε<十進(jìn)小數(shù)>→d<余留十進(jìn)小數(shù)><余留十進(jìn)小數(shù)>→e<指數(shù)部分>|d<余留十進(jìn)小數(shù)>|ε<指數(shù)部分>→d<余留整指數(shù)>|s<整指數(shù)><整指數(shù)>→d<余留整指數(shù)><余留整指數(shù)>→d<余留整指數(shù)>|ε其中s—正負(fù)符號(hào)+、－3.5.1單詞的描述工具——正規(guī)式的定義正規(guī)式也叫正則表達(dá)式，用于描述稱為正規(guī)集的語(yǔ)言。定義3.9

字母表Σ上的正規(guī)式和正規(guī)集的遞歸定義為：(1)ε和Φ是Σ上的正規(guī)式，它們所代表的正規(guī)集為{ε}{}(Φ)；(2)任何a∈Σ，a是Σ上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a}；(3)假定e1與e2都是Σ上的正規(guī)式，它們所表示的正規(guī)集為L(zhǎng)(e1)和L(e2)，那么(e1)、e1|e2、e1?e2和e1*也是正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1)、L(e1)∪L(e2)、L(e1)L(e2)、(L(e1))*(4)僅用有限次使用上述三步驟而定義的表達(dá)式方是Σ上的正規(guī)式，僅有這些正規(guī)式所表示的字集才是Σ上的正規(guī)集。正規(guī)式運(yùn)算符優(yōu)先關(guān)系①‘|’(或)<‘?’(連接)<‘*’(閉包)②‘*’、‘|’都滿足左結(jié)合注：連接號(hào)可省略例１：正規(guī)式正規(guī)式a|baba*ba*(a|b)(a|b)a(a|b)*(a|b)*(aa|bb)(a|b)*正規(guī)集{a,b}{ab}{ε,a,aa,…任意個(gè)a的串}Σ上所有以b為首后跟任意個(gè)a的字{aa，ab，ba，bb}Σ上所有以a為首的字Σ上所有含有兩個(gè)相繼的a或b的字例2

令Σ={l,d,.,e,+,-}，則Σ上的

正規(guī)式d*(.dd*|ε)(e(+|-|ε)dd*|ε)l(l|d)*dd*正規(guī)集所有無(wú)符號(hào)的數(shù)標(biāo)識(shí)符所有無(wú)符號(hào)整數(shù)定義3.10

正規(guī)式等價(jià)

若兩個(gè)正規(guī)式e1,e2所表示的正規(guī)集相等(即L(e1)=L(e2))，則e1,e2等價(jià)，記為e1=e2。

例如：a|b=b|a，b(ab)*=(ba)*b，(a|b)*=(a*b*)*正規(guī)式的代數(shù)規(guī)律定理3.1設(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εε的恒等式……參考課本P71定理3.13.5.3正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性由以下兩點(diǎn)說(shuō)明：(1)Σ上的非確定自動(dòng)機(jī)M所能識(shí)別的字的全體L(M)是Σ上的一個(gè)正規(guī)集；（或?qū)τ讦?/p>

上的NFAM，可以構(gòu)造一個(gè)Σ

上的正規(guī)式e，使得L(e)=L(M)）(2)對(duì)于Σ上的每個(gè)正規(guī)集V，存在一個(gè)Σ上的確定有窮自動(dòng)機(jī)M，使得V=L(M)；（或?qū)τ讦?/p>

上的每個(gè)正規(guī)式e，可以構(gòu)造一個(gè)NFAM，使得L(M)=L(e)）3.5.4正規(guī)式→NFA從正規(guī)式R構(gòu)造NFA的算法：首先把正規(guī)式R表示成如下圖的拓廣轉(zhuǎn)換圖：xRy然后通過(guò)對(duì)R進(jìn)行分裂和加進(jìn)新結(jié)的方法，逐步把這個(gè)圖轉(zhuǎn)換變成每條弧標(biāo)記為Σ的一個(gè)字符或ε。其轉(zhuǎn)換規(guī)則如下：注：在整個(gè)分裂的過(guò)程中，所有新結(jié)均采用不同的名字，結(jié)點(diǎn)x,y為構(gòu)造成的NFA的唯一的初態(tài)和終態(tài)。正規(guī)式轉(zhuǎn)換系統(tǒng)Φxyεxεya(a∈Σ)xays|t(s,t是正規(guī)式)xsytstxsy1ts*xεy1εs正規(guī)式→NFA（續(xù)）正規(guī)式→NFA（續(xù)）例1e=(a|b)*abb構(gòu)造NFAN，使得L(N)=L(e)。解：x(a|b)*abbyx(a|b)*y2abbxεy1abb2εabxεy1a2εab3b4b正規(guī)式→NFA（續(xù)）例1.構(gòu)造與正規(guī)式e=(+|-|ε)dd*等價(jià)的最簡(jiǎn)DFAM，使得L(M)=L(e)。2.為e=(a|b)*abb構(gòu)造NFAN，使得L(N)=L(e)。3.構(gòu)造與正規(guī)式e=(a*b)ba(a|b)*等價(jià)的最簡(jiǎn)DFAM，使得L(M)=L(e)。3.5.5NFAM→正規(guī)式e把狀態(tài)圖的概念拓廣，令每條弧可用一個(gè)正規(guī)式作標(biāo)記1.添加x,y結(jié)點(diǎn)構(gòu)造NFAM’，其中x與所有的初始結(jié)ε弧連接，y與所有終態(tài)結(jié)ε弧連接。2.反復(fù)使用以下規(guī)則，消去M’中的所有結(jié)，直到只剩下x,y結(jié)；在消結(jié)過(guò)程中逐步用正規(guī)式來(lái)標(biāo)記箭弧，其消結(jié)的規(guī)則如下：1R123R21R1R23NFAM→正規(guī)式R（續(xù)）1R12R21R1|R221R123R21R1R2*R33R3最后，x和y結(jié)點(diǎn)間弧上的標(biāo)記則為所求的正規(guī)式R。例１NFAM的狀態(tài)圖如下，求正規(guī)式e，使得L(e)=L(M)。01a,b342ababa,ba,bxεyεε所求的正規(guī)式e=(a|b)*(aa|bb)(a|b)*xε0a,

b(aa|bb)(a|b)*Yy例２NFAM的狀態(tài)圖如下，求正規(guī)式e，使得L(e)=L(M)。01aa,bbab,baab,baaa,bb解：正規(guī)式R=((aa|bb)|(ab|ba)(aa|bb)*(ab|ba))*0aa,bbxε(ab|ba)(aa|bb)*(ab|ba)ε例３

有些自動(dòng)機(jī)比較復(fù)雜，我們也并不完全按照上述規(guī)則進(jìn)行轉(zhuǎn)換。例如svutabababa,b可分四種走向（要點(diǎn)，劃分圖成多個(gè)子圖,本題4個(gè)）：(1)s→u→t：a(ba)*a(a|b)*(2)s→u→v→t：ab(ab)*b(a|b)*(3)s→v→u→t：ba(ba)*a(a|b)*(4)s→v→t：b(ab)*b(a|b)*(((ε|b)a(ba)*)|((ε|a)b(ab)*))(a|b)(a|b)*綜合題構(gòu)造正規(guī)式e=(a|b)*(aa|bb)(a|b)*相應(yīng)的DFA。解：(1)構(gòu)造NFANx(a|b)*(aa|bb)(a|b)*yx(a|b)*y1aa|bb2(a|b)*aaaaxεy120εbbbε5εbaaxεy130εabbε5εab24b

正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性(2)對(duì)NFAN確定化：構(gòu)造狀態(tài)轉(zhuǎn)換矩陣IIaIbSab{x,0,1}{0,1,3}{0,1,4}012{0,1,3}{0,1,3,2,5,y}{0,1,4}132{0,1,4}{0,1,3}{0,1,4,2,6,y}214{0,1,2,3,5,y}{0,1,3,2,5,y}{0,1,4,5,y}335{0,1,2,4,5,y}{0,1,3,5,y}{0,1,4,2,5,y}464{0,1,4,5,y}{0,1,3,5,y}{0,1,4,2,5,y}564{0,1,3,5,y}{0,1,3,2,5,y}{0,1,4,5,y}635

正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性∴DFAM為：0a312baba4ba5b6baabab(3)對(duì)DFAM進(jìn)行化簡(jiǎn)0a312bababa,b整個(gè)劃分為：{0},{1},{2},{3,4,5,6}§3.5.6正規(guī)文法和正規(guī)式間的轉(zhuǎn)換

一個(gè)正規(guī)語(yǔ)言，可以由正規(guī)文法來(lái)定義，也可以由正規(guī)式定義。任意正規(guī)文法，存在一個(gè)對(duì)應(yīng)的正規(guī)式；反之亦然。方法：1.直接轉(zhuǎn)換2.間接轉(zhuǎn)換正規(guī)文法→有窮自動(dòng)機(jī)→正規(guī)式正規(guī)式→有窮自動(dòng)機(jī)→正規(guī)文法§3.5.6正規(guī)式->正規(guī)文法將Σ上的一個(gè)正規(guī)式r，轉(zhuǎn)換為正規(guī)文法G=(VN,VT,P,S).1.令VT=

Σ2.S->r,S為開(kāi)始符號(hào)3.若x和y都是正規(guī)式，則 產(chǎn)生式 重寫(xiě)為：r1. A->xy A->xBB->yr2. A->x*y A->xAA->yr3. A->x|y A->xA->y不斷做變換，直到每個(gè)產(chǎn)生式右端最多只含一個(gè)VN

§3.5.6正規(guī)式->正規(guī)文法例 將正規(guī)式R=a(ad) 轉(zhuǎn)換為相應(yīng)的正規(guī)文法。

VT={a,d} Sa(ad)

r3. SaA AaA AdA

A

VN={S,A}r1.SaA A(ad)r2.A(ad)A A §3.5.6正規(guī)文法->正規(guī)式對(duì)G=(VN,VT,P,S),存在一個(gè)Σ=VT上的正規(guī)式e，使得L(R)=L(e)。在此介紹2種轉(zhuǎn)換方法：一：1.令Σ=VT2.轉(zhuǎn)換規(guī)則 文法產(chǎn)生式 正規(guī)式 AxBBy A=xy AxAyA=xy Axy A=xy不斷做變換，直到只剩下一個(gè)開(kāi)始符號(hào)定義的產(chǎn)生式，且該產(chǎn)生式右端不含VN

§3.5.6正規(guī)文法->正規(guī)式例子例文法G[s]:SaA AaA AdA Sa Aa Ad⑤

S=a(ad)(ad)a =a((ad)(ad)) =a((ad))所以，t=a(ad)解答：SaAaAaAadAdA(ad)A(ad) A(ad)(ad)§3.5.6正規(guī)文法->正規(guī)式二.方程組求解法p78例3.19

S->0A|1B|0|1A->0S|1B|1B->1S+0A解：寫(xiě)出關(guān)于變量S、A、B的正規(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+1)+(0+10)A+11S(6)A=1+0S+1(1S+0A)=1+10A+(0+11)S(7)

將(7)重寫(xiě)為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)+11SS=((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)

3.6DFA在計(jì)算機(jī)中的表示要在計(jì)算機(jī)中表示一個(gè)DFA，只需表示它的映射3.6.1矩陣表示法例3.21映射t(q0,x1)=q1,t(q0,x2)=q3,t