第三章有窮自動(dòng)機(jī)

第三章有窮自動(dòng)機(jī)第1頁(yè)，共74頁(yè)，2023年，2月20日，星期三§3.1有窮自動(dòng)機(jī)的形式定義

有窮狀態(tài)自動(dòng)機(jī)(Finite-stateAutomata或簡(jiǎn)稱(chēng)FA)在識(shí)別功能上與正規(guī)文法類(lèi)等價(jià)，而且也等價(jià)于一個(gè)特殊類(lèi)型的語(yǔ)言產(chǎn)生器——正規(guī)表達(dá)式(RegularExpression)。因此許多簡(jiǎn)單的程序語(yǔ)言都可由FA所識(shí)別。事實(shí)上，它是描述詞法的有效工具，也是進(jìn)行詞法分析的主要理論基礎(chǔ)。

第2頁(yè)，共74頁(yè)，2023年，2月20日，星期三有窮自動(dòng)機(jī)分為兩類(lèi)：（1）確定的有窮自動(dòng)機(jī)(DeterministicFiniteAutomata簡(jiǎn)稱(chēng)DFA)（2）不確定的有窮自動(dòng)機(jī)(NondeterministicFiniteAutomata簡(jiǎn)稱(chēng)NFA)。

第3頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.1.1確定有窮自動(dòng)機(jī)的形式定義

一個(gè)DFAM＝(K，Σ，f，S，Z)，其中(ａ)K是一個(gè)有限狀態(tài)集合。(ｂ)Σ是一個(gè)字母表，它的每個(gè)元素稱(chēng)為一個(gè)輸入字符。(ｃ)S∈K，S稱(chēng)為初始狀態(tài),唯一。(ｄ)ZK，Z稱(chēng)為終態(tài)集合,終態(tài)也稱(chēng)可接受狀態(tài)或結(jié)束狀態(tài)。(ｅ)f是轉(zhuǎn)換函數(shù)，是一個(gè)從K×Σ到K的單值映射。f(ki，a)＝kj（ki,kj∈K,a∈Σ）kj稱(chēng)為ki的一個(gè)后繼狀態(tài)。第4頁(yè)，共74頁(yè)，2023年，2月20日，星期三確定性的體現(xiàn)：初始狀態(tài)唯一；轉(zhuǎn)換函數(shù)為單值映射。例：設(shè)DFAM=({S,U,V,Q}，{a,b}，f，S，｛Q｝)其中

f(S,a)＝U，f(S,b)＝V

f(U,a)＝Q，f(U,b)＝V

f(V,a)＝U，f(V,b)＝Q

f(Q,a)＝Q，f(Q,b)＝Q因?yàn)椋?）初始狀態(tài)唯一是S，（2）每個(gè)轉(zhuǎn)換函數(shù)均為單值映射。所以該FA為確定有窮自動(dòng)機(jī)。

第5頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.1.2狀態(tài)轉(zhuǎn)換表

DFA的映射關(guān)系可以由一個(gè)矩陣表示，矩陣的行標(biāo)表示狀態(tài)，列標(biāo)表示輸入字符，矩陣元素表示f(s,a)的值，這個(gè)矩陣稱(chēng)為狀態(tài)轉(zhuǎn)換表。

f(S,a)＝U

f(S,b)＝Vf(U,a)＝Q

f(U,b)＝Vf(V,a)＝U

f(V,b)＝Qf(Q,a)＝Q

f(Q,b)＝QabSUVUQVVUQQQQ第6頁(yè)，共74頁(yè)，2023年，2月20日，星期三q1aaabbabbq2q3q03.1.3狀態(tài)轉(zhuǎn)換圖圖中標(biāo)有的為開(kāi)始狀態(tài)，標(biāo)有雙圈的狀態(tài)為終止?fàn)顟B(tài)。若f(Ki,a)=Kj，則從狀態(tài)結(jié)點(diǎn)Ki到狀態(tài)Kj畫(huà)標(biāo)記為a的弧。第7頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.1.4自動(dòng)機(jī)的等價(jià)性為了討論自動(dòng)機(jī)的等價(jià)性，先對(duì)DFA中的映射進(jìn)行擴(kuò)充。擴(kuò)充的轉(zhuǎn)換函數(shù)f設(shè)QK，函數(shù)f(Q,)=Q，即如果輸入字符是空串，則仍停留在原來(lái)的狀態(tài)上。對(duì)QK,T,t1*,f(Q,Tt1)=f(f(Q,T),t1)該定義是一個(gè)遞歸定義，說(shuō)明當(dāng)自動(dòng)機(jī)處在狀態(tài)Q且面臨某個(gè)輸入串Tt1時(shí)，則先應(yīng)用函數(shù)f(Q,T)=P，然后應(yīng)用函數(shù)f(P,t1)。第8頁(yè)，共74頁(yè)，2023年，2月20日，星期三DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)f：KK是一個(gè)單值函數(shù)，即對(duì)任何狀態(tài)kK和輸入符號(hào)a，f(k,a)唯一地確定了下一個(gè)狀態(tài)，從狀態(tài)轉(zhuǎn)換圖來(lái)看，若字母表含有n個(gè)輸入字符，那么任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條弧射出，且每條弧以一個(gè)不同的輸入字符標(biāo)記。

第9頁(yè)，共74頁(yè)，2023年，2月20日，星期三自動(dòng)機(jī)接受字符串x如果對(duì)于某一自動(dòng)機(jī)M=(K,,f,S,Z)，x*，有f(S,x)=P，且PZ，則x為該自動(dòng)機(jī)M所接受（識(shí)別），即自動(dòng)機(jī)從開(kāi)始狀態(tài)開(kāi)始，在讀完全部輸入串以后，自動(dòng)機(jī)恰恰到達(dá)終止?fàn)顟B(tài)，則該輸入串能被該自動(dòng)機(jī)所接受。

第10頁(yè)，共74頁(yè)，2023年，2月20日，星期三例：DFAM=({S,A,B,C},{0,1},,S,{S})，且定義為(S,0)=B，(S,1)=A，(A,0)=C，(A,1)=S，(B,0)=S，(B,1)=C，(C,0)=A，(C,1)=B狀態(tài)圖表示，矩陣表示：第11頁(yè)，共74頁(yè)，2023年，2月20日，星期三自動(dòng)機(jī)處理字符串110101和11101的軌跡(S,110101)=((S,1),10101)=(A,10101)=((A,1),0101)=(S,0101)=((S,0),101)=(B,101)=((B,1),01)=(C,01)=((C,0),1)=(A,1)=S(接受)(S,11101)=((S,1),1101)=(A,1101)=((A,1),101)=(S,101)=((S,1),01)=(A,01)=((A,0),1)=(C,1)=B(拒絕)第12頁(yè)，共74頁(yè)，2023年，2月20日，星期三所有為自動(dòng)機(jī)M所能接受的串組成一個(gè)集合，稱(chēng)這個(gè)集合為自動(dòng)機(jī)M所能接受的語(yǔ)言，用L(M)表示：L(M)={t|f(S,t)Z，t*}對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)M和M’，如果L(M)=L(M’)，則稱(chēng)M與M’是等價(jià)的。第13頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.1.5非確定有窮自動(dòng)機(jī)NFA定義一個(gè)不確定的有窮自動(dòng)機(jī)NFAM’是一個(gè)五元組：M’=(K,,f,S,Z)一個(gè)含有m個(gè)狀態(tài)和n個(gè)輸入字符的NFA可表示為一張狀態(tài)轉(zhuǎn)換圖，該圖含有m個(gè)狀態(tài)結(jié)，每個(gè)結(jié)可射出若干條箭弧與別的結(jié)點(diǎn)相連接，每條弧用*中的一個(gè)字（不一定要不同的字，且可以為空字）作標(biāo)記（稱(chēng)輸入字），整個(gè)圖至少含有一個(gè)初態(tài)結(jié)以及若干個(gè)終態(tài)結(jié)。第14頁(yè)，共74頁(yè)，2023年，2月20日，星期三NFA與DFA的區(qū)別NFA有一個(gè)開(kāi)始狀態(tài)集，而DFA只有一個(gè)開(kāi)始狀態(tài)。NFA的映射是QQ的子集，是一個(gè)多值映射，而DFA的映射是QQ，是一個(gè)單值映射。DFA是NFA的特例，對(duì)于每個(gè)NFAM，存在一個(gè)DFAM’，使得L(M)=L(M’)。第15頁(yè)，共74頁(yè)，2023年，2月20日，星期三對(duì)于*中的任何一個(gè)串t，如果存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上的所有弧的標(biāo)記依序連接成的串等于t，則稱(chēng)t可為NFAM所識(shí)別（讀出或接受）。若M的某些結(jié)既是初態(tài)結(jié)，又是終態(tài)結(jié)，或者存在一條從某個(gè)初態(tài)結(jié)到某個(gè)終態(tài)結(jié)的道路，則空字可為M所接受。

第16頁(yè)，共74頁(yè)，2023年，2月20日，星期三例：NFAM=({0,1,2,3,4},{a,b},f,{0},{2,4})f(0,a)={0,3} f(2,b)={2} f(0,b)={0,1}f(3,a)={4} f(1,b)={2} f(4,a)={4}f(2,a)={2} f(4,b)={4}可用狀態(tài)圖或矩陣表示：03412aabba,ba,ba,b第17頁(yè)，共74頁(yè)，2023年，2月20日，星期三§3.2NFA到DFA的轉(zhuǎn)換通過(guò)下述步驟可將一個(gè)NFA轉(zhuǎn)換成等價(jià)的DFA：①尋找并消除空移環(huán)路；②消除余下的空移；③確定化。

第18頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.2.1空移環(huán)路的尋找和消除第19頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.2.2消除空移

下面給出一個(gè)消除空移的算法。給定從狀態(tài)A到B的一個(gè)空移(即從狀態(tài)A到B經(jīng)由連線的一個(gè)轉(zhuǎn)換，換言之，t(A,)={…，B，…})。置t(A,)=，對(duì)每個(gè)a和Q，如果Qt(B,a)，則將Q加到t(A,a)。如果A是開(kāi)始狀態(tài)，則將B也加入開(kāi)始狀態(tài)集。如果B是終止?fàn)顟B(tài)，則將A也加入終止?fàn)顟B(tài)集。

第20頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.2.3利用狀態(tài)轉(zhuǎn)換表消除空移

利用FA的狀態(tài)轉(zhuǎn)換表，可以很容易地消除空移。這種方法的基本步驟是：首先，找出直接經(jīng)由一個(gè)空移到達(dá)某個(gè)終態(tài)的所有狀態(tài)。每當(dāng)找到這樣一個(gè)狀態(tài)，便將它標(biāo)記為終態(tài)。然后，考慮消除與未被標(biāo)記為終態(tài)的那些狀態(tài)相關(guān)的空移。對(duì)表中每一個(gè)具有射出ε連線的狀態(tài)繼續(xù)按上述方式處理，直到狀態(tài)轉(zhuǎn)換表不再變動(dòng)為止。最后從表中刪除ε列和沒(méi)有任何元素的空行，便得到一個(gè)不含空移的狀態(tài)轉(zhuǎn)換表。

第21頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.2.4確定化——造表法

造表法是一種簡(jiǎn)單而有效的確定化方法。定義：設(shè)NFAM=(Q,∪{},t,Q0,F)，假定I是M中狀態(tài)集的一個(gè)子集，定義_closure(I)如下：若qI，則q_closure(I)；若q_closure(I)，q是由q出發(fā)經(jīng)多條弧到達(dá)的狀態(tài)，則q_closure(I)。第22頁(yè)，共74頁(yè)，2023年，2月20日，星期三定義：假定I是NFAM中狀態(tài)集的一個(gè)子集，a，定義Ia=_closure(J)其中J是所有那些可從子集I中的任一狀態(tài)出發(fā)，經(jīng)過(guò)一條a連線(跳過(guò)a連線前的ε連線)而到達(dá)的狀態(tài)(結(jié))的全體。造表法的具體步驟：假定給定的NFAM中僅含兩個(gè)符號(hào)a，b?？捎萌缦路椒▽確定化：采用造表的方式，該表的每一行有三列(若中含有n個(gè)符號(hào)，則該表有n+1列)，第一列記為I，第二、三列分別記為Ia,Ib。

第23頁(yè)，共74頁(yè)，2023年，2月20日，星期三①置該表的第一行第一列為_(kāi)closure(Q0)，即一列包含M初態(tài)集Q0的ε_(tái)閉包。然后計(jì)算它的Ia和Ib,分別填入第二、三列上，一般，若某一行的第一列上的I已確定，便可根據(jù)前述定義求出這一行的第二、第三列上的Ia和Ib。②檢查Ia和Ib，看它們是否已在表的第一列中出現(xiàn)，把未曾出現(xiàn)者之一填入下一空行的第一列上，再計(jì)算該行的第二、第三列上的Ia和Ib。

第24頁(yè)，共74頁(yè)，2023年，2月20日，星期三③重復(fù)第二步，直至表中所有第二、第三列上的元素全部再第一列出現(xiàn)為止。因?yàn)镸中的狀態(tài)(子集)的個(gè)數(shù)是有限的，所以上述三步必定在有限步驟內(nèi)終止。④將由上述過(guò)程得到的最終形式的表看作一個(gè)狀態(tài)轉(zhuǎn)換表，即把其中第一列中的元素作為狀態(tài)，把Ia,Ib分別看作是輸入符號(hào)a，b，把其余信息看作是狀態(tài)轉(zhuǎn)換函數(shù)之值。這個(gè)表唯一地刻畫(huà)了一個(gè)確定的有窮狀態(tài)自動(dòng)機(jī)M，其初態(tài)是該表第一行第一列的元素，其終態(tài)是該表中所有那些含有原終態(tài)的元素?？梢宰C明，這個(gè)DFAM和NFAM是等價(jià)的。

第25頁(yè)，共74頁(yè)，2023年，2月20日，星期三例：有一NFAM，用造表法使其確定化。bbaab01253467891001234bbbbbaaaaa第26頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.2.5確定的有窮自動(dòng)機(jī)的化簡(jiǎn)

所謂一個(gè)確定的有窮自動(dòng)機(jī)M的化簡(jiǎn)是指：尋找一個(gè)狀態(tài)數(shù)比M少的DFAM’，使得L(M)=L(M’)，可通過(guò)消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī)。消除多余狀態(tài)多余狀態(tài)是指從該自動(dòng)機(jī)的開(kāi)始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的狀態(tài)。

第27頁(yè)，共74頁(yè)，2023年，2月20日，星期三ABC第28頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.2.6合并等價(jià)狀態(tài)

等價(jià)狀態(tài)若s和t是M的兩個(gè)不同狀態(tài)，稱(chēng)s和t等價(jià)：如果從狀態(tài)s出發(fā)能讀出某個(gè)字而停于終態(tài)，同樣從t出發(fā)也能讀出同一個(gè)字而停于終態(tài)；反之若從t出發(fā)能讀出某個(gè)字而停于終態(tài)，則從s出發(fā)也能讀出同一個(gè)字而停于終態(tài)。如果DFAM的兩個(gè)狀態(tài)s和t不等價(jià)，則稱(chēng)這兩個(gè)狀態(tài)是可區(qū)別的。

第29頁(yè)，共74頁(yè)，2023年，2月20日，星期三DFA中，狀態(tài)s和t等價(jià)的條件是：一致性條件：狀態(tài)s和t必須同時(shí)為可接受狀態(tài)(終態(tài))或不可接受狀態(tài)(非終態(tài))。蔓延性條件：對(duì)于所有輸入符號(hào)，狀態(tài)s和t必須轉(zhuǎn)換到等價(jià)的狀態(tài)里。分割法合并等價(jià)狀態(tài)一個(gè)DFAM的狀態(tài)化簡(jiǎn)過(guò)程就是把M的狀態(tài)集劃分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)分的，而同一子集的任何兩個(gè)狀態(tài)都是等價(jià)的。最后，從每個(gè)子集選出一個(gè)代表(代表該子集)，同時(shí)消去其它等價(jià)狀態(tài)。第30頁(yè)，共74頁(yè)，2023年，2月20日，星期三對(duì)M的狀態(tài)集S進(jìn)行劃分的步驟：①把S的終態(tài)與非終態(tài)分開(kāi)，分成兩個(gè)子集，形成基本劃分，屬于這兩個(gè)不同子集的狀態(tài)是可區(qū)別的。②假定某個(gè)時(shí)候已含m個(gè)子集，記={I(1),I(2),…,I(m)}且屬于不同子集的狀態(tài)是可區(qū)別的，再檢查中的每個(gè)I能否進(jìn)一步劃分，對(duì)于某個(gè)I(i)，令I(lǐng)(i)={S1,S2,…,Sk}，若存在一個(gè)輸入字符使得move(I(i),a)不包含在現(xiàn)行的某一子集I(i)中，則將I(i)一分為二。第31頁(yè)，共74頁(yè)，2023年，2月20日，星期三例：將圖示的DFAM最小化。1362457aaaaaaabbbbbbb第32頁(yè)，共74頁(yè)，2023年，2月20日，星期三1、將M狀態(tài)分為兩個(gè)子集： P0=({1,2,3,4},{5,6,7})2、{1,2,3,4}讀入a后劃為： P1=({1,2},{3,4},{5,6,7})3、進(jìn)一步劃分： P2=({1,2},{3},{4},{5,6,7})4、考察{5,6,7},將P2劃分為： P3=({1,2},{3},{4},{5},{6,7}) P3不可再劃分，從而1與2，6與7等價(jià)。第33頁(yè)，共74頁(yè)，2023年，2月20日，星期三13645aaabbbbba第34頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.2.7從化簡(jiǎn)后的DFA到程序表示

識(shí)別標(biāo)識(shí)符的DFA（見(jiàn)圖(a)）需改為圖(b)所示狀態(tài)，其中，l代表字母，d代表數(shù)字。

圖(a)圖(b)第35頁(yè)，共74頁(yè)，2023年，2月20日，星期三如果賦予狀態(tài)q0、q1與q2一定的操作，則可得識(shí)別單詞標(biāo)識(shí)符的程序流程圖(見(jiàn)下圖)。

第36頁(yè)，共74頁(yè)，2023年，2月20日，星期三§3.3正規(guī)文法與有窮自動(dòng)機(jī)正規(guī)文法與有窮自動(dòng)機(jī)FA有著特殊的關(guān)系?？梢宰C明：對(duì)任何正規(guī)文法G，可以構(gòu)造一個(gè)FA，它能而且只能識(shí)別語(yǔ)言L(G)；反過(guò)來(lái)，對(duì)任何FA，可以構(gòu)造一個(gè)相應(yīng)的正規(guī)文法G，它能生成由該FA所識(shí)別的語(yǔ)言。第37頁(yè)，共74頁(yè)，2023年，2月20日，星期三2.3.1從正規(guī)文法到FA

設(shè)正規(guī)文法G有形如U→aV(aVT,VVN或V=)的產(chǎn)生式。由正規(guī)文法G可以直接構(gòu)造一個(gè)有窮自動(dòng)機(jī)A(簡(jiǎn)稱(chēng)自動(dòng)機(jī)A)，使L(A)=L(G)。構(gòu)造步驟如下：①令正規(guī)文法G的終結(jié)符號(hào)集作為有窮自動(dòng)機(jī)A的字母表；②文法G的每一個(gè)非終結(jié)符都作為自動(dòng)機(jī)A的一個(gè)狀態(tài)，特別是文法G的開(kāi)始符作為自動(dòng)機(jī)A的開(kāi)始狀態(tài)；第38頁(yè)，共74頁(yè)，2023年，2月20日，星期三③在自動(dòng)機(jī)A中增加一個(gè)新?tīng)顟B(tài)z作為自動(dòng)機(jī)的終止?fàn)顟B(tài)；④對(duì)于文法G的形如U→aV(aVT或a=,VVN)的產(chǎn)生式，在自動(dòng)機(jī)A中構(gòu)造形如t(U,a)=V的映射；⑤對(duì)文法G的形如U→a(aVT)的產(chǎn)生式，在自動(dòng)機(jī)A中構(gòu)造形如t(U,a)=z的映射。第39頁(yè)，共74頁(yè)，2023年，2月20日，星期三2.3.2從FA到正規(guī)文法從自動(dòng)機(jī)也可直接構(gòu)造其正規(guī)文法。構(gòu)造步驟如下：①自動(dòng)機(jī)每一個(gè)狀態(tài)的標(biāo)記，均作為正規(guī)文法的非終結(jié)符，其中，自動(dòng)機(jī)開(kāi)始狀態(tài)的標(biāo)記將作為正規(guī)文法的開(kāi)始符號(hào)。自動(dòng)機(jī)的輸入字母表中的所有符號(hào)，作為正規(guī)文法的終結(jié)符。第40頁(yè)，共74頁(yè)，2023年，2月20日，星期三②對(duì)于自動(dòng)機(jī)的映射t(U,a)=V（其中，U、V為自動(dòng)機(jī)的狀態(tài)標(biāo)記；a為輸入符號(hào)），構(gòu)造文法的一條產(chǎn)生式 U→aVU、V為文法的非終結(jié)符，a為終結(jié)符。③對(duì)于自動(dòng)機(jī)的終止?fàn)顟B(tài)Z，在正規(guī)文法中增加一條產(chǎn)生式Z→

第41頁(yè)，共74頁(yè)，2023年，2月20日，星期三§3.4正規(guī)表達(dá)式與FA

正規(guī)式也稱(chēng)正規(guī)則式、正規(guī)表達(dá)式，與正規(guī)文法的功能一樣，正規(guī)式也可用以描述程序設(shè)計(jì)語(yǔ)言的單詞符號(hào)。3.4.1

正規(guī)表達(dá)式的操作符連接假定有兩個(gè)正規(guī)表達(dá)式e1和e2，它們分別產(chǎn)生語(yǔ)言L1和L2，于是定義正規(guī)表達(dá)式的連接操作為e1e2={xy|xL1，yL2}其中可省略第42頁(yè)，共74頁(yè)，2023年，2月20日，星期三選擇可用|或+表示，定義為e1|e2={x|xL1或xL2}重復(fù)用*表示，表示*中的表達(dá)式的0次到若干次的自重復(fù)連接，即e*={x|xL1*}第43頁(yè)，共74頁(yè)，2023年，2月20日，星期三例：正規(guī)表達(dá)式110由數(shù)字1，1，0連接在一起組成，且表示的語(yǔ)言為L(zhǎng)={110}表達(dá)式0|1所表示的語(yǔ)言為L(zhǎng)={0，1}表達(dá)式1*所表示的語(yǔ)言為L(zhǎng)={1i|i=0，1，2...}例：用正則表達(dá)式表示

{標(biāo)識(shí)符}=字母(字母|數(shù)字)*

{實(shí)數(shù)}=(e|+|-)(數(shù)字*

.數(shù)字?jǐn)?shù)字*)第44頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.4.2正規(guī)表達(dá)式的定義所有正規(guī)表達(dá)式都可以由下列規(guī)則構(gòu)造出來(lái)：①是一個(gè)表示空集的正規(guī)表達(dá)式②是一個(gè)正規(guī)表達(dá)式，它所表示的語(yǔ)言?xún)H包含一個(gè)空符號(hào)串，即{}③a是一個(gè)正規(guī)表達(dá)式，aVT它所表示的語(yǔ)言（它所表示的正規(guī)集）是單個(gè)符號(hào)a所組成，即{a}第45頁(yè)，共74頁(yè)，2023年，2月20日，星期三④如果e1和e2是正規(guī)表達(dá)式，其表示的語(yǔ)言分別為L(zhǎng)1和L2，(e1)|(e2)是一個(gè)表示語(yǔ)言L1L2的正規(guī)表達(dá)式(e1)(e2)是一個(gè)表示語(yǔ)言L1L2的正規(guī)表達(dá)式(e1)*是一個(gè)表示語(yǔ)言L1*的正規(guī)表達(dá)式⑤正規(guī)表達(dá)式中操作符的優(yōu)先級(jí)順序?yàn)?，連接，|第46頁(yè)，共74頁(yè)，2023年，2月20日，星期三例：正規(guī)表達(dá)式a*b*表示的正規(guī)集是 {ambn|m0,n0}正規(guī)表達(dá)式(ab)*表示的正規(guī)集是 {(ab)m|m0}正規(guī)表達(dá)式(a|b)*表示的正規(guī)集是 {x|x{a,b}*}表達(dá)式(aa|ab|ba|bb)* 表示在VT={a,b}上的所有偶長(zhǎng)度的串第47頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.4.3正規(guī)表達(dá)式的等價(jià)性如果兩個(gè)正規(guī)表達(dá)式表示相同的語(yǔ)言，則這兩個(gè)正規(guī)表達(dá)式相等或等價(jià)，故有00*=000*|03.4.4正規(guī)表達(dá)式的性質(zhì)r|s=s|r 或滿(mǎn)足交換律r|(s|t)=(r|s)|t 或滿(mǎn)足結(jié)合律(rs)t=r(st) 連接滿(mǎn)足結(jié)合律r(s|t)=rs|rt(s|t)r=sr|tr 分配律r=r，r=r 是連接的恒等元素第48頁(yè)，共74頁(yè)，2023年，2月20日，星期三例：程序設(shè)計(jì)語(yǔ)言中的單詞都能用正規(guī)式來(lái)定義，如：={字母,數(shù)字}上的正規(guī)式e1=字母(字母|數(shù)字)*表示的是所有標(biāo)識(shí)符的集合正規(guī)式e=dd*定義了無(wú)符號(hào)整數(shù)令={d,.,e,+,-}，則上的正規(guī)式 (d*.dd*|dd*)(e(+|-|)dd*|)表示的是無(wú)符號(hào)數(shù)。第49頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.4.5正規(guī)文法與正規(guī)式

一個(gè)正規(guī)語(yǔ)言可以由正規(guī)文法定義，也可以由正規(guī)式定義，對(duì)任意一個(gè)正規(guī)文法，存在一個(gè)定義同一個(gè)語(yǔ)言的正規(guī)式；反之，對(duì)每個(gè)正規(guī)式，存在一個(gè)生成同一語(yǔ)言的正規(guī)文法。正規(guī)式轉(zhuǎn)換成正規(guī)文法將上的一個(gè)正規(guī)式轉(zhuǎn)換成文法G=(VN,VT,P,S)，令其中的VT=，確定產(chǎn)生式和VN的元素用如下方法：第50頁(yè)，共74頁(yè)，2023年，2月20日，星期三對(duì)任何正規(guī)式r，選擇一個(gè)非終結(jié)符S，生成產(chǎn)生式Sr，并將S定為G的識(shí)別符號(hào)。若x和y都是正規(guī)式，對(duì)形如Axy的產(chǎn)生式，重寫(xiě)為AxB，By兩產(chǎn)生式，其中B是新選擇的非終結(jié)符，即BVN。對(duì)已轉(zhuǎn)換的文法中的形如Ax*y的產(chǎn)生式，重寫(xiě)為AxA,Ay對(duì)形如Ax|y的產(chǎn)生式重寫(xiě)為Ax，Ay不斷利用上述規(guī)則作變換，直到每個(gè)產(chǎn)生式最多含有一個(gè)VN為止。第51頁(yè)，共74頁(yè)，2023年，2月20日，星期三例：將R=a(a|d)*轉(zhuǎn)換成相應(yīng)的正規(guī)文法。 令S是識(shí)別符號(hào)，首先形成Sa(a|d)*，下一步，SaA,A(a|d)*，重寫(xiě)為： A(a|d)A，A 進(jìn)而轉(zhuǎn)變?yōu)椋篠aA，AaA，AdA，A第52頁(yè)，共74頁(yè)，2023年，2月20日，星期三正規(guī)文法轉(zhuǎn)換成正規(guī)式 上述過(guò)程的逆過(guò)程，最后只剩下一個(gè)開(kāi)始符號(hào)定義的產(chǎn)生式，并且該產(chǎn)生式的右部不含非終結(jié)符，轉(zhuǎn)換規(guī)則：第53頁(yè)，共74頁(yè)，2023年，2月20日，星期三例：文法G[S]：SaA，Sa，AaA，AdA，Aa，AdS=aA|a，A=aA|dA|a|d=(a|d)A|(a|d)A=(a|d)*(a|d)S=a(a|d)*(a|d)|a=a((a|d)*(a|d)|)=a(a|d)*練習(xí)：有文法G[S]：SaS，SaB，BbC，CaC，Ca第54頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.4.6正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性正規(guī)表達(dá)式與有窮自動(dòng)機(jī)等價(jià)，是指若給定一正則表達(dá)式，也即相應(yīng)地給定了正則集合L(e)，那么就可構(gòu)造NFAM，并有L(M)=L(e)；反之，若給定一個(gè)DFAM，M接受的語(yǔ)言為L(zhǎng)(M)，則必然存在一正則表達(dá)式e，且L(e)=L(M)。正規(guī)表達(dá)式和FA是定義語(yǔ)言（符號(hào)串集）的兩種不同形式。同一個(gè)語(yǔ)言，既可用FA描述，也可用正規(guī)表達(dá)式描述。第55頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.4.7正規(guī)表達(dá)式到NFA的轉(zhuǎn)換先構(gòu)造一個(gè)NFAM的一個(gè)廣義轉(zhuǎn)換圖，其中，只有S與Z兩個(gè)狀態(tài)，S是開(kāi)始狀態(tài)，Z是終止?fàn)顟B(tài)，弧上是正規(guī)表達(dá)式e。然后，按照下圖所示的替換規(guī)則對(duì)正規(guī)表達(dá)式e逐步進(jìn)行分解，直到轉(zhuǎn)換圖中所有的弧上都是S中的單個(gè)符號(hào)或e為止。第56頁(yè)，共74頁(yè)，2023年，2月20日，星期三替換成替換成替換成第57頁(yè)，共74頁(yè)，2023年，2月20日，星期三例：有={a,b}上的正規(guī)式R=(a|b)*abb，構(gòu)造NFAM使L(M)=L(e)。練習(xí)：構(gòu)造與={a,b}上的正規(guī)式(a|b)*(aa|bb)(a|b)*等價(jià)的自動(dòng)機(jī)。第58頁(yè)，共74頁(yè)，2023年，2月20日，星期三3.4.8NFA到正規(guī)表達(dá)式的轉(zhuǎn)換一個(gè)輸入字母表為的NFAM，可構(gòu)造正規(guī)表達(dá)式e，使L(e)=L(M)。具體操作如下：①首先對(duì)NFAM進(jìn)行拓廣，在M的狀態(tài)轉(zhuǎn)換圖中，設(shè)置一個(gè)唯一的開(kāi)始狀態(tài)S和唯一的終止?fàn)顟B(tài)Z，并允許狀態(tài)轉(zhuǎn)換圖中弧上可以為正規(guī)表達(dá)式。②然后從開(kāi)始狀態(tài)S到原來(lái)所有的開(kāi)始狀態(tài)連接弧，再?gòu)脑瓉?lái)所有的終止?fàn)顟B(tài)到Z狀態(tài)也連接弧。修改后構(gòu)成了一個(gè)新的NFA，它只有一個(gè)初態(tài)結(jié)點(diǎn)S和一個(gè)終態(tài)結(jié)點(diǎn)Z，這個(gè)新的NFAM′顯然和原NFAM等價(jià)。第59頁(yè)，共74頁(yè)，2023年，2月20日，星期三③接著，利用下圖所示的替換規(guī)則，逐步消去M′中屬于M的所有結(jié)點(diǎn)和有關(guān)連線，直到狀態(tài)轉(zhuǎn)換圖中只剩下?tīng)顟B(tài)S和Z為止(這個(gè)過(guò)程稱(chēng)為消結(jié))。在消結(jié)過(guò)程中，用相應(yīng)的正規(guī)表達(dá)式標(biāo)記連線。第60頁(yè)，共74頁(yè)，2023年，2月20日，星期三替換成替換成替換成第61頁(yè)，共74頁(yè)，2023年，2月20日，星期三例：NFAM=({0,1,2,3,4},{a,b},f,{0},{2,4}),狀態(tài)圖如下，構(gòu)造正規(guī)式R使L(R)=L(M)。03412aabba,ba,ba,b第62頁(yè)，共74頁(yè)，2023年，2月20日，星期三§3.5DFA在計(jì)算機(jī)中的表示

矩陣表示法設(shè)M是一個(gè)二維數(shù)組，若t(qi,qj)=qk，則令M[i,j]=k，其中i,k=0,1,2,…,n；j=1,2,…,m。表結(jié)構(gòu)DFA的映射t:QQ在計(jì)算機(jī)中可表示成一種表結(jié)構(gòu)。在這個(gè)表結(jié)構(gòu)中，每一個(gè)狀態(tài)對(duì)應(yīng)一個(gè)表，表中包括該狀態(tài)的狀態(tài)名、從該狀態(tài)發(fā)出的弧數(shù)、每條弧上的標(biāo)記以及弧達(dá)到的狀態(tài)所在表的首地址。第63頁(yè)，共74頁(yè)，2023年，2月20日，星期三DFA在計(jì)算機(jī)中的表結(jié)構(gòu)

第64頁(yè)，共74頁(yè)，2023年，2月20日，星期三程序表示法我們也可以用程序來(lái)表示DFA。例：C語(yǔ)言的注釋/*…*/，其有窮自動(dòng)機(jī)12345/**/*otherother第65頁(yè)，共74頁(yè)，2023年，2月20日，星期三{State1}ifthenextcharacterris“/”thenadvancetheinput;{State2}ifthenextcharacteris“*”thenadvancetheinput;{State3}done:=false;whilenotdonedowhilethenextinputcharacterisnot“*”doadvancetheinput;endwhile;advancetheinput;{State4}第66頁(yè)，共74頁(yè)，2023年，2月20日，星期三whilethenextinputcharacteris“*”doadvancetheinput;endwhile;ifthenextinputcharacteris“/”thendone:=true;endif;advancetheinput;endwhile;accept;{State5}else{otherprocessing}endifelse{otherprocessing}endifState:=1;{Start}第67頁(yè)，共74頁(yè)，2023年，2月20日，星期三whilestate=1,2,3or4docasestateof1:caseinputcharacterof“/”:advancetheinputstate:=2;elsestate:=…{ErrororOther}endcase2:caseinputcharacterof“*”:advancetheinput;state:=3;