形式語言與自動機(jī).ppt

《形式語言與自動機(jī).ppt》由會員分享，可在線閱讀，更多相關(guān)《形式語言與自動機(jī).ppt（89頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第2章 形式語言與自動機(jī)基礎(chǔ),知識點(diǎn)：文法的形式定義 上下文無關(guān)文法、正規(guī)文法 推導(dǎo)、短語、分析樹、二義性 有限自動機(jī)的形式定義 自動機(jī)、文法、表達(dá)式等價(jià)性 NFA的確定化、DFA的最小化,2,形式語言與自動機(jī)基礎(chǔ),2.1 語言和文法 2.2 有限自動機(jī) 2.3 正規(guī)文法與有限自動機(jī)的等價(jià)性 2.4 正規(guī)表達(dá)式與有限自動機(jī)的等價(jià)性 2.5 正規(guī)表達(dá)式與正規(guī)文法的等價(jià)性 小 結(jié),3,2.1 語言和文法,一、字母表和符號串 二、語言 三、文法及其形式定義 四、推導(dǎo)和短語 五、分析樹及二義性 六、文法的變換,4,一、字母表和符號串,字母表 符號的非空有限集合 典型的符號是字母、數(shù)字、各種

2、標(biāo)點(diǎn)和運(yùn)算符等。 符號串 定義在某一字母表上 由該字母表中的符號組成的有限符號序列 同義詞：句子、字 符號串有關(guān)的幾個概念 長度 符號串的長度是指中出現(xiàn)的符號的個數(shù)，記作||。 空串的長度為0，常用表示。,5,前綴 符號串的前綴是指從符號串的末尾刪除0個或多個符號后得到的符號串。如：univ 是 university 的前綴,后綴 符號串的后綴是指從符號串的開頭刪除0個或多個符號后得到的符號串。如：sity 是 university 的后綴 子串 符號串的子串是指刪除了的前綴和/或后綴后得到的符號串。如：ver 是 university 的子串 真前綴、真后綴、真子串 如果非空符號串是的前綴、

3、后綴或子串，并且，則稱是的真前綴、真后綴、或真子串。 子序列 符號串的子序列是指從中刪除0個或多個符號(這些符號可以是不連續(xù)的)后得到的符號串。如：nvst,6,連接,符號串和符號串的連接是把符號串加在符號串之后得到的符號串 若=ab，=cd，則=abcd，=cdba。 對任何符號串來說，都有== 冪 若是符號串，的n次冪n 定義為：,當(dāng)n=0時(shí)，0是空串。 假如=ab，則有： 0= 1=ab 2=abab ,7,二、語言,語言：在某一確定字母表上的符號串的集合。 空集，集合也是符合此定義的語言。 這個定義并沒有把任何意義賦予語言中的符號串。 語言的運(yùn)算：假設(shè)L和M表示兩個語言 L和M的并

4、記作LM：LM=s|sL 或 sM L和M的連接記作LM：LM=st|sL 并且 tM L的閉包記作L*：即L的0次或若干次連接。,= L0L1L2L3 ,L的正閉包記作L+：即L的1次或若干次連接。,= L1L2L3L4 ,8,L=A,B, ,Z,a,b, ,z，D=0,1, ,9 可以把L和D看作是字母表 可以把L和D看作是語言 語言運(yùn)算舉例：,把冪運(yùn)算推廣到語言 L0=，Ln=Ln-1L，于是Ln是語言L與其自身的n-1次連接。,9,三、文法及其形式定義,文法：所謂文法就是描述語言的語法結(jié)構(gòu)的形式規(guī)則。 任何一個文法都可以表示為一個四元組G=(VT,VN,S, ) VT是一個非空的有限集

5、合，它的每個元素稱為終結(jié)符號。 VN是一個非空的有限集合，它的每個元素稱為非終結(jié)符號。 VTVN = S是一個特殊的非終結(jié)符號，稱為文法的開始符號。 是一個非空的有限集合，它的每個元素稱為產(chǎn)生式。 產(chǎn)生式的形式為： “” 表示 “定義為”（或“由組成”） 、(VTVN)* ， 左部相同的產(chǎn)生式1、2、、n可以縮寫 1|2||n “|” 表示 “或”， 每個i(i=1,2,,n)稱為的一個候選式,10,,,文法的分類 根據(jù)對產(chǎn)生式施加的限制不同，定義了四類文法和 相應(yīng)的四種形式語言類。,11,上下文無關(guān)文法及相應(yīng)的語言,所定義的語法單位(或稱語法實(shí)體)完全獨(dú)立于這種語法單位可能出現(xiàn)的上下文環(huán)

6、境 現(xiàn)有程序設(shè)計(jì)語言中，許多語法單位的結(jié)構(gòu)可以用上下文無關(guān)文法來描述。 例：描述算術(shù)表達(dá)式的文法G： G=(i,+,-,*,/,(,),,,,,) 其中： + | - | * | / | () | i 語言L(G)是所有包括加、減、乘、除四則運(yùn)算的算術(shù)表達(dá)式的集合。,12,如果用“::=”代替“”，這組產(chǎn)生式可以寫為： ::= + | - | ::= * | / | ::= () | i 元語言： ::= 表示 “定義為” 或 “由組成” 表示非終結(jié)符號 | 表示“或”,BNF（Backus-Normal Form）表示法,,13,文法書寫約定,終結(jié)符號 次序靠前的小寫字母，如：a、b

7、、c 運(yùn)算符號，如：+、-、*、/ 各種標(biāo)點(diǎn)符號，如：括號、逗號、冒號、等于號 數(shù)字1、2、、9 黑體字符串，如：id、begin、if、then 非終結(jié)符號 次序靠前的大寫字母，如：A、B、C 大寫字母S常用作文法的開始符號 小寫的斜體符號串，如：expr、term、factor、stmt,14,終結(jié)符號串 次序靠后的小寫字母，如：u、v、、z 文法符號串 小寫的希臘字母，如：、、、 可以直接用產(chǎn)生式的集合代替四元組來描述文法，第一個產(chǎn)生式的左部符號是文法的開始符號。,文法符號 次序靠后的大寫字母，如：X、Y、Z,15,四、推導(dǎo)和短語,例：考慮簡單算術(shù)表達(dá)式的文法G： G=(+，*，（，），

8、i,E，T，F(xiàn),E,) ： E E + T | T T T * F | F F（E）| i 文法所產(chǎn)生的語言 從文法的開始符號出發(fā)，反復(fù)連續(xù)使用產(chǎn)生式對非終結(jié)符號進(jìn)行替換和展開，就可以得到該文法定義的語言。,16,推導(dǎo),假定A是一個產(chǎn)生式，和是任意的文法符號串，則有： A “” 表示 “一步推導(dǎo)” 即利用產(chǎn)生式對左邊符號串中的一個非終結(jié)符號進(jìn)行替換，得到右邊的符號串。 稱A直接推導(dǎo)出 也可以說是A的直接推導(dǎo) 或說直接歸約到A,17,從文法開始符號E推導(dǎo)出符號串i+i的詳細(xì)過程,稱這個序列是從1到n的長度為n的推導(dǎo),E E+T T+T F+T i+T i+F i+i,18,最左推導(dǎo),最右

9、推導(dǎo),最右推導(dǎo)也稱為規(guī)范推導(dǎo),E E+T T+T F+T i+T i+F i+i,E E+T E+F E+i T+i F+i i+i,19,句型,句子 僅含有終結(jié)符號的句型是文法的一個句子。 語言 文法G產(chǎn)生的所有句子組成的集合是文法G所定義的語言，記作L(G)。,20,對于文法G=(VT,VN,S,)，假定是文法G的一個句型，如果存在：,短語,則稱是句型關(guān)于非終結(jié)符號A的短語。 如果存在：,則稱是句型關(guān)于非終結(jié)符號A的直接短語。 一個句型的最左直接短語稱為該句型的句柄。 例:,ETT*FT*(E)F*(E)i*(E)i*(E+T)i*(T+T)i*(F+T)i*(i+T)

10、 ,21,五、分析樹及二義性,分析樹 子樹 子樹與短語之間的關(guān)系 二義性,22,分析樹,推導(dǎo)的圖形表示，又稱推導(dǎo)樹。 一棵有序有向樹，因此具有樹的性質(zhì)； 自己的特點(diǎn)：每一個結(jié)點(diǎn)都有標(biāo)記。 根結(jié)點(diǎn)由文法的開始符號標(biāo)記； 每個內(nèi)部結(jié)點(diǎn)由非終結(jié)符號標(biāo)記，它的子結(jié)點(diǎn)由這個非終結(jié)符號的這次推導(dǎo)所用產(chǎn)生式的右部各符號從左到右依次標(biāo)記； 葉結(jié)點(diǎn)由非終結(jié)符號或終結(jié)符號標(biāo)記，它們從左到右排列起來，構(gòu)成句型。 ETT*FT*(E)F*(E)i*(E) i*(E+T)i*(T+T)i*(F+T)i*(i+T),ETT*FF*Fi*Fi*(E) i*(E+T)i*(T+T)i*(F+T)i*(i+T),23,子樹

11、,分析樹中一個特有的結(jié)點(diǎn)、連同它的全部后裔結(jié)點(diǎn)、連接這些結(jié)點(diǎn)的邊、以及這些結(jié)點(diǎn)的標(biāo)記。 子樹的根結(jié)點(diǎn)的標(biāo)記可能不是文法的開始符號。 如果子樹的根結(jié)點(diǎn)標(biāo)記為非終結(jié)符號A，則可稱該子樹為A-子樹。,24,,子樹與短語的關(guān)系,一棵子樹的所有葉結(jié)點(diǎn)自左至右排列起來，形成此句型相對于該子樹根的短語； 分析樹中只有父子兩代的子樹的所有葉結(jié)點(diǎn)自左至右排列起來，形成此句型相對于該子樹根的直接短語； 分析樹中最左邊的那棵只有父子兩代的子樹的所有葉結(jié)點(diǎn)自左至右排列起來，就是該句型的句柄。,25,二義性,如果一個文法的某個句子有不止一棵分析樹，則這個句子是二義性的。 含有二義性句子的文法是二義性的文法。 例：考慮文

12、法 G=(+,*,（,）,i,E,E,) ： E E+E | E*E | (E) | id 句子 id+id*id 存在兩個不同的最左推導(dǎo)： EE+Eid+Eid+E*Eid+id*Eid+id*id EE*EE+E*Eid+E*Eid+id*Eid+id*id 有兩棵不同的分析樹,26,文法的二義性和語言的二義性,如果兩個文法產(chǎn)生的語言相同，即L(G)=L(G)，則稱這兩個文法是等價(jià)的。 有時(shí)，一個二義性的文法可以變換為一個等價(jià)的、無二義性的文法。 有些語言，根本就不存在無二義性的文法，這樣的語言稱為二義性的語言。 二義性問題是不可判定的 不存在一種算法，它能夠在有限的步驟內(nèi)確切地判定出一個

13、文法是否是二義性的。 可以找出一些充分條件（未必是必要條件），當(dāng)文法滿足這些條件時(shí)，就可以確信該文法是無二義性的。,27,六、文法的變換,文法二義性的消除 左遞歸的消除 提取左因子,28,文法二義性的消除,映射程序設(shè)計(jì)語言中IF語句的文法： stmt if expr then stmt | if expr then stmt else stmt | other 句子if E1 then if E2 then S1 else S2有兩棵不同的分析樹：,29,最近最后匹配原則,else必須匹配離它最近的那個未匹配的then 出現(xiàn)在then和else之間的語句必須是“匹配的”。 所謂匹配的語句是

14、不包含不匹配語句的if-then-else語句，或是其他任何非條件語句。 改寫后的文法： stmtmatched_stmt | unmatched_stmt matched_stmtif expr then matched_stmt else matched_stmt | other unmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt,30,句子if E1 then if E2 then S1 else S2的分析樹,31,左遞歸的消除,一個文法是左遞歸的，如果它有非終結(jié)符

15、號A，對某個文法符號串，存在推導(dǎo)：,消除左遞歸的方法： 簡單情況：如果文法G有產(chǎn)生式：AA| 可以把A的這兩個產(chǎn)生式改寫為：AA AA| 這兩組產(chǎn)生式是等價(jià)的 由于從A推導(dǎo)出的符號串是相同的，即都是,若存在某個=，則稱該文法是有環(huán)路的。,32,例：消除表達(dá)式文法中的左遞歸： EE+T|T TT*F|F F(E)|id,利用消除直接左遞歸的方法，可以改寫為: ETE E+TE | TFT T*FT | F(E) | id,33,一般情況：假定關(guān)于A的全部產(chǎn)生式是：,AA1|A2||Am|1|2||n 產(chǎn)生式可以改寫為：

16、 A1A|2A||nA A1A|2 A||mA| 例如有間接左遞歸文法： SAa|b AAc|Sd|,34,算法：消除左遞歸,輸入：無環(huán)路、無-產(chǎn)生式的文法G 輸出：不帶有左遞歸的、與G等價(jià)的文法G 方法： (1)把文法G的所有非終結(jié)符號按某種順序排列成A1,A2,,An (2)for (i=1; i<=n; i++) for (j=1; j<=i-1; j++) if (Aj1|2||k是關(guān)于當(dāng)前Aj的所有產(chǎn)生式) 把每個形如AiAj的產(chǎn)生式改寫為：Ai1|2||k； 消除關(guān)于Ai的產(chǎn)生式中的直接左遞歸; (3)化簡第(2)步得到的文法，即去除無用的非終結(jié)符號

17、和產(chǎn)生式。 這種方法得到的非遞歸文法可能含有-產(chǎn)生式。,35,為含有-產(chǎn)生式的文法G=(VT,VN,S,) 構(gòu)造不含-產(chǎn)生式的文法G=(VT,VN,S,)的方法,若產(chǎn)生式AX1X2Xn則把產(chǎn)生式A12n加入 其中：Xi、i為文法符號，即Xi、i(VTVN) 若Xi不能產(chǎn)生，則i=Xi 若Xi能產(chǎn)生，則i=Xi 或 i= 不能所有的i都取 文法G滿足：,一個文法是-無關(guān)的， 如果它沒有-產(chǎn)生式（即形如A的產(chǎn)生式），或者 只有一個-產(chǎn)生式，即S，并且文法的開始符號S不出現(xiàn)在任何產(chǎn)生式的右部。,36,例：消除下面文法中的左遞歸 SAa|b AAc|Sd|,首先，必須保證此文法中無環(huán)路、無-

18、產(chǎn)生式。 改寫為無-產(chǎn)生式的文法： SAa|a|b AAc|c|Sd 消除其中的左遞歸： 第一步，把文法的非終結(jié)符號排列為S、A； 第二步，由于S不存在直接左遞歸，所以算法第2步在i=1時(shí)不做工作； 在i=2時(shí)，把產(chǎn)生式SAa|a|b代入A的有關(guān)產(chǎn)生式中，得到： AAc|c|Aad|ad|bd 消除A產(chǎn)生式中的直接左遞歸，得到文法： SAa|a|b AcA|adA|bdA AcA|adA|,37,提取左因子,如有產(chǎn)生式 A1|2 提取左公因子，則原產(chǎn)生式變?yōu)椋? AA A1|2 若有產(chǎn)生式 A1|2||n| 可用如下的產(chǎn)生式代替： AA| A1|2||n

19、,38,例：映射程序設(shè)計(jì)語言中IF語句的文法 stmt if expr then stmt | if expr then stmt else stmt | a exprb,左公因子 if expr then stmt 提取左公因子，得到文法： stmtif expr then stmt S | a S else stmt | exprb,39,2.2 有限自動機(jī),有限自動機(jī)是具有離散輸入與輸出的系統(tǒng)的一種數(shù)學(xué)模型 系統(tǒng)可處于有限個內(nèi)部狀態(tài)的任何一個之中 系統(tǒng)的當(dāng)前狀態(tài)概括了有關(guān)過去輸入的信息 例：自動電梯的控制機(jī)構(gòu) “確定的有限自動機(jī)”指，在當(dāng)前狀態(tài)下，輸入一個符號，有限

20、自動機(jī)轉(zhuǎn)換到唯一的下一個狀態(tài)，稱為后繼狀態(tài)。 “非確定的有限自動機(jī)”指，在當(dāng)前狀態(tài)下輸入一個符號，可能有兩種以上可選擇的后繼狀態(tài)，并且非確定的有限自動機(jī)所對應(yīng)的狀態(tài)轉(zhuǎn)換圖可以有標(biāo)記為的邊。,40,有限自動機(jī),一、確定的有限自動機(jī)（DFA） 二、非確定的有限自動機(jī)（NFA） 三、具有-轉(zhuǎn)移的非確定的有限自動機(jī) 四、DFA的化簡,41,一、確定的有限自動機(jī)（DFA）,一張有限的方向圖 圖中結(jié)點(diǎn)代表狀態(tài)，用圓圈表示 只含有限個狀態(tài)，有一個初始狀態(tài)，可以有若干個終結(jié)狀態(tài)，終態(tài)用雙圓圈表示。 狀態(tài)之間用有向邊連接 邊上的標(biāo)記表示在射出結(jié)點(diǎn)狀態(tài)下可能出現(xiàn)的輸入符號,狀態(tài)轉(zhuǎn)換圖,42,利用狀態(tài)轉(zhuǎn)換圖，識別符

21、號串,識別方法： (1) 起點(diǎn)為初態(tài)S，從w的最左符號開始，重復(fù)步驟(2)，直到達(dá)到w的最右符號為止。 (2) 掃描w的下一個符號，在當(dāng)前狀態(tài)的所有射出邊中找出標(biāo)記為該字符的邊，沿此邊過度到下一個狀態(tài)。 狀態(tài)轉(zhuǎn)換圖所能識別的符號串的全體稱為該狀態(tài)轉(zhuǎn)換圖所識別的語言。,L(M)=10,110,111,01,000,001,43,確定的有限自動機(jī)的定義,一個確定的有限自動機(jī)M(記作：DFA M)是一個五元組： M=(，Q，q0，F(xiàn)，) 其中 ：是一個字母表，它的每個元素稱為一個輸入符號 Q：是一個有限的狀態(tài)集合 q0Q：q0稱為初始狀態(tài) FQ：F稱為終結(jié)狀態(tài)集合 ：是一個從Q到Q的

22、單值映射 轉(zhuǎn)換函數(shù)(q,a)=q (其中q,qQ,a）表示當(dāng)前狀態(tài)為q，輸入符號為a時(shí)，自動機(jī)將轉(zhuǎn)換到下一個狀態(tài)q，q稱為q的一個后繼。 若Q=q1,q2,,qn, =a1,a2,,am，則Q=((qi,aj))nm 是一個n行m列的矩陣，它稱為DFA M的狀態(tài)轉(zhuǎn)換矩陣，也稱為轉(zhuǎn)換表。,44,例 有 DFA M=(0,1,A,B,C,S,f,S,f,) 其中 (S,0)=B (A,0)=f (B,0)=C (C,0)=f (S,1)=A (A,1)=C (B,1)=f (C,1)=f,狀態(tài)轉(zhuǎn)換矩陣： 5行2列的矩陣 每一行對應(yīng)M的一個狀態(tài) 每一列對應(yīng)M的一個輸入符號,DFA M可用一張狀態(tài)轉(zhuǎn)

23、換圖來表示： 若DFA M有n個狀態(tài)，m個輸入符號，則狀態(tài)轉(zhuǎn)換圖有n個狀態(tài)結(jié)點(diǎn)，每個結(jié)點(diǎn)最多有m條射出邊。 若q、qQ,a，并且(q,a)=q，則從q到q有一條標(biāo)記為a的有向邊。 整個圖含有唯一的一個初態(tài)。,45,DFA M所識別的語言,對上的任何符號串*，若存在一條從初態(tài)結(jié)點(diǎn)到終態(tài)結(jié)點(diǎn)的路徑，該路徑上每條邊的標(biāo)記連接成的符號串恰好是，則稱為DFA M所識別。 DFA M所能識別的符號串的全體記為L(M)，稱為 DFA M 所識別的語言。 如果我們對所有*，遞歸地?cái)U(kuò)張的定義： 對任何a，qQ 定義：(q,)=q (q,a)=((q,),a) L(M)= | *，并且存在qF，使(q0,)=q

24、 ,46,二、非確定的有限自動機(jī)（NFA）,所接受的語言是 L(M)=a+b+,NFA的定義： 一個非確定的有限自動機(jī)M(記作：NFA M)是一個五元組 M=(，Q，q0，F(xiàn)，) 其中 ：是一個字母表，它的每個元素稱為一個輸入符號 Q：是一個有限狀態(tài)集合 q0Q：q0稱為初始狀態(tài) FQ：F稱為終結(jié)狀態(tài)集合 ：是一個從Q到Q的子集的映射， 即：Q2Q 其中2Q是Q的冪集，也就是Q的所有子集組成的集合。,47,有限自動機(jī)的狀態(tài)轉(zhuǎn)換圖及識別的語言,狀態(tài)轉(zhuǎn)換圖 NFA M含有n個狀態(tài)，m個輸入符號 圖中含有n個狀態(tài)結(jié)點(diǎn)，每個結(jié)點(diǎn)可射出若干條邊 圖中有唯一的一個初態(tài)結(jié)點(diǎn) 對上的任何符號串*，

25、若存在一條從初態(tài)結(jié)點(diǎn)到終態(tài)結(jié)點(diǎn)的路徑，該路徑上每條邊的標(biāo)記連接成的符號串恰好是，則稱為NFA M所識別。 NFA M所能識別的符號串的全體記為L(M)，稱為NFA M所識別的語言。 如果q0F 存在一條從初態(tài)結(jié)點(diǎn)到終態(tài)結(jié)點(diǎn)的-道路 空串可為該NFA M所識別，即 L(M),48,例：設(shè)有 NFA M=(a,b,0,1,2,3,0,3, ) 其中 (0,a)=0,1 (0,b)=0 (1,b)=2 (2,b)=3,狀態(tài)轉(zhuǎn)換矩陣：,狀態(tài)轉(zhuǎn)換圖：,NFA M所識別的語言：,L(M)=(a|b)*abb,49,定理：對任何一個NFA M，都存在一個與之等價(jià)的 DFA D，即L(M)=L(D)。,例：

26、構(gòu)造與下面的NFA M等價(jià)的DFA D NFA M=（a,b，A,B，A，B，） 其中：(A,a)=A,B (A,b)=B (B,b)=A,B 首先，畫出該NFA M的狀態(tài)轉(zhuǎn)換圖,假設(shè)DFA D=（a,b,Q,q0,F,） Q：Q的所有子集組成的集合，即Q=2Q Q=,A,B,A.B q0=q0 q0=A F：所有含有原NFA M終態(tài)的Q的子集組成的集合 F=B，A，B,50,的構(gòu)成 (q1,q2,,qk,a)= (q1,a)(q2,a)(qk,a),(,a)= (,b)= (A,a)=(A,a)=A,B (A,b)=(A,b)=B (B,a)=(B,a)= (B,b)=(B,

27、b)=A,B (A,B,a)=(A,a)(B,a)=A,B=A,B (A,B,b)=(A,b)(B,b)=BA,B=A,B,DFA D的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖,51,子集構(gòu)造法：構(gòu)造與NFA M等價(jià)的DFA D,列出NFA M的每個子集及該子集相對于每個輸入符號的后繼子集 對所有子集重新命名，得到DFA D的狀態(tài)轉(zhuǎn)換矩陣。,NFA M的狀態(tài)轉(zhuǎn)換矩陣,DFA D的狀態(tài)轉(zhuǎn)換矩陣,52,三、具有-轉(zhuǎn)移的非確定有限自動機(jī),定義：一個具有-轉(zhuǎn)移的非確定有限自動機(jī)M(記作：NFA M) 是一個五元組 M=(，Q，q0，F(xiàn)，) 其中 ：是一個字母表，它的每個元素稱為一個輸入符號 Q：是一個有限的狀態(tài)集

28、合 q0Q：q0稱為初始狀態(tài) FQ：F稱為終結(jié)狀態(tài)集合 ：是一個從Q()到Q的子集的映射，即：Q()2Q,對任何qQ及a()，轉(zhuǎn)移函數(shù)的值具有如下的形式 (q,a)=q1,q2,,qk 其中 qiQ (i=1,2,,k) NFA 的狀態(tài)轉(zhuǎn)換圖 圖中可能有標(biāo)記為的邊 當(dāng)(q,)=q1,q2,,qk時(shí)，從q出發(fā)有k條標(biāo)記為的邊分別指向q1,q2,,qk。,53,例：NFA M=(a,b,0,1,2,3,4,0,2,4, ) 其中 (0,)=1,3 (1,a)=1,2 (3,b)=3,4,NFA M的狀態(tài)轉(zhuǎn)換矩陣,NFA M的狀態(tài)轉(zhuǎn)換圖,NFA M所識別的語言為L(M)= a+|b+ 。,5

29、4,假設(shè) NFA N=(a,b,0,1,2,3,4,0,F,) _closure(q)：從狀態(tài)q出發(fā)，經(jīng)過-道路可以到達(dá)的所有狀態(tài)的集合。 F的構(gòu)成：,定理：對任何一個具有-轉(zhuǎn)移的NFA M，都存在一個 等價(jià)的不具有-轉(zhuǎn)移的NFA N，即L(M)=L(N)。,例：構(gòu)造與NFA M 等價(jià)的不具有-轉(zhuǎn)移的NFA N NFA M=(a,b,0,1,2,3,4,0,2,4, ) 其中 (0,)=1,3 (1,a)=1,2 (3,b)=3,4 狀態(tài)轉(zhuǎn)換圖如右：,由于_closure(0)=0,1,3，不包含NFA M的終態(tài)，因此F=F=2,4,55,的構(gòu)成：,(q,a)=q| q為從q出發(fā),經(jīng)過標(biāo)記

30、為a的道路所能到達(dá)的狀態(tài),(0,a)=1,2 (0,b)=3,4 (1,a)=1,2 (1,b)= (2,a)= (2,b)= (3,a)= (3,b)=3,4 (4,a)= (4,b)=,NFA N的狀態(tài)轉(zhuǎn)換矩陣 和狀態(tài)轉(zhuǎn)換圖如下：,56,推論：對于任何一個具有-轉(zhuǎn)移的NFA M，都存在 一個與之等價(jià)的DFA D，即L(M)=L(D)。,DFA D的每個狀態(tài)對應(yīng)NFA M的一個狀態(tài)子集。 對給定的輸入符號串，為了使D“并行地”模擬M所能產(chǎn)生的所有可能的轉(zhuǎn)換，令q為NFA M的狀態(tài)，T為 NFA M 的狀態(tài)子集，引入以下操作： _closure(q)=q |從q出發(fā)，經(jīng)過-道路可以到

31、達(dá)狀態(tài)q,從T中任一狀態(tài)出發(fā)，經(jīng)過-道路后可以到達(dá)的狀態(tài)集合。 move(T,a)=q | (qi,a)=q，其中qiT 從某個狀態(tài)qiT出發(fā)，經(jīng)過輸入符號a之后可到達(dá)的狀態(tài)集合。,57,算法：計(jì)算_closure(T),把T中所有狀態(tài)壓入棧； _closure(T)的初值置為T； while 棧不空 彈出棧頂元素t； for (each q_closure(t)) if (q_closure(T)) 把q加入_closure(T); 把q壓入棧; ,58,算法：為NFA構(gòu)造等價(jià)的DFA,輸入：一個NFA M 輸出：一個與NFA M等價(jià)（即接受同樣語言）的DFA D 方法：為D

32、FA D構(gòu)造狀態(tài)轉(zhuǎn)換表DTT 初態(tài)：_closure(q0)是DQ中唯一的狀態(tài)，且未標(biāo)記。 while (DQ中存在一個未標(biāo)記的狀態(tài)T) 標(biāo)記 T； for (each a) U=_closure(move(T,a))； if (UDQ) 把U做為一個未標(biāo)記的狀態(tài)加入DQ； DTTT,a：=U; ,59,例：構(gòu)造與下面的NFA M等價(jià)的DFA D。,字母表=a,b 初態(tài)為A，則A=_closure(0)=0,1,2,4,7 DTTA,a = _closure( move(A,a) ) = _closure( move(0,a)move(1,

33、a)move(2,a)move(4,a)move(7,a) ) = _closure(3,8) = _closure(3)_closure(8) = 1,2,3,4,6,7,8 = B DTTA,b = -closure(move(A,b)) = -closure(5) = 1,2,4,5,6,7 = C DTTB,a = -closure(move(B,a)) = -closure(3,8) = B DTTB,b = -closure(move(B,b)) = -closure(5,9) = 1,2,4,5,6,7,9 = D,60,DTTC,b = -closure(move(C,b

34、)) = -closure(5) = C DTTD,a = -closure(move(D,a)) = -closure(3,8) = B DTTD,b = -closure(move(D,b)) = -closure(5,10) = 1,2,4,5,6,7,10 = E DTTE,a = -closure(move(E,a)) = -closure(3,8) = B DTTE,b = -closure(move(E,b)) = -closure(5) = C,DFA D有5個狀態(tài)，即A、B、C、D、E， 其中A為初態(tài) E為終態(tài)，因?yàn)镋的狀態(tài)集合中包括原NFA M的終態(tài)10。

35、 DFA D的狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖,DTTC,a = -closure(move(C,a)) = -closure(3,8) = B,61,四、DFA的化簡,狀態(tài)D是一個“死狀態(tài)”，是一個無用的狀態(tài)。 去掉狀態(tài)D及與之相連接的邊，可以得到等價(jià)的狀態(tài)轉(zhuǎn)換圖,L(M)=0(10)* 對于任何一個含有n個狀態(tài)的DFA，都存在含有m(mn)個狀態(tài)的DFA與之等價(jià)。 DFA D的化簡，指尋找一個狀態(tài)數(shù)比較少的DFA D，使L(D)=L(D)。 可以證明，存在一個最少狀態(tài)的DFA D，使L(D)=L(D)，并且這個D是唯一的。,62,,DFA D的最小化過程,定義：設(shè)s,tQ，若對任何*， (s,)F

36、 當(dāng)且僅當(dāng) (t,)F，則稱狀態(tài)s和t是等價(jià)的。 否則稱狀態(tài)s和t是可區(qū)分的。 DFA D的最小化過程： 把D的狀態(tài)集合分割成一些互不相交的子集，使每個子集中的任何兩個狀態(tài)是等價(jià)的，而任何兩個屬于不同子集的狀態(tài)是可區(qū)分的。 在每個子集中任取一個狀態(tài)作“代表”，刪去該子集中其余的狀態(tài)，并把射向其它結(jié)點(diǎn)的邊改為射向“代表”結(jié)點(diǎn)。 如果得到的DFA中有死狀態(tài)、或從初態(tài)無法到達(dá)的狀態(tài)，則把它們刪除。,63,把狀態(tài)集合Q分割成滿足要求的子集,把狀態(tài)集合Q劃分成兩個子集：終態(tài)子集F和非終態(tài)子集G。 對每個子集進(jìn)行劃分： 取某個子集A=s1,s2,,sk 取某個輸入符號a，檢查A中的每個狀態(tài)對該輸入符號的轉(zhuǎn)

37、換。 如果A中的狀態(tài)相對于a，轉(zhuǎn)換到不同子集中的狀態(tài)，則要對A進(jìn)行劃分。使A中能夠轉(zhuǎn)換到同一子集的狀態(tài)作為一個新的子集。 重復(fù)上述過程，直到每個子集都不能再劃分為止。,64,例：對狀態(tài)轉(zhuǎn)換圖所描述的DFA D最小化,第一步：把DFA D的狀態(tài)集合劃分為子集，使每個子集中的狀態(tài)相互等價(jià)，不同子集中的狀態(tài)可區(qū)分。,把D的狀態(tài)集合劃分為兩個子集：A,B,C,D和E 考察非終態(tài)子集A,B,C,D - 對于a，狀態(tài)A,B,C,D都轉(zhuǎn)換到狀態(tài)B，所以對輸入符號a而言，該子集不能再劃分。 - 對于b，狀態(tài)A,B,C都轉(zhuǎn)換到子集A,B,C,D中的狀態(tài)，而狀態(tài)D則轉(zhuǎn)換到子集E中的狀態(tài)。 - 應(yīng)把子集A,B,C,

38、D劃分成兩個新的子集A,B,C和D。,65,D的狀態(tài)集合被劃分為：A,B,C、D和E,考察子集A,B,C - 對于a，狀態(tài)A,B,C都轉(zhuǎn)換到狀態(tài)B，所以對輸入符號a而言，該子集不能再劃分。 - 對于b，狀態(tài)A,C轉(zhuǎn)換到C，狀態(tài)B轉(zhuǎn)換到D。狀態(tài)C和D分屬于不同的子集。 - 應(yīng)把子集A,B,C劃分成兩個新的子集A,C和B。 D的狀態(tài)集合被劃分為：A,C、B、D和E 考察子集A,C - 對于a，狀態(tài)A,C都轉(zhuǎn)換到狀態(tài)B。 - 對于b，狀態(tài)A,C都轉(zhuǎn)換到狀態(tài)C。 - 該子集不可再劃分。 D的狀態(tài)集合最終被劃分為：A,C、B、D和E,66,構(gòu)造最小DFA D,第二步：為每個子集選擇一個代表狀態(tài)。 選擇A

39、為子集A,C的代表狀態(tài) D的狀態(tài)轉(zhuǎn)換圖,D的狀態(tài)轉(zhuǎn)換矩陣,67,2.3 正規(guī)文法與有限自動機(jī)的等價(jià)性,如果對于某個正規(guī)文法G和某個有限自動機(jī)M，有L(G)=L(M)，則稱G和M是等價(jià)的。 定理：對每一個右線性文法G或左線性文法G，都存在一個等價(jià)的有限自動機(jī)M。 證明：首先考慮右線性正規(guī)文法 設(shè)給定的一個右線性文法G為：G=(VT，VN，S，) 與G等價(jià)的有限自動機(jī)M為：M=(，Q，q0，F(xiàn)，) =VT，q0=S，F(xiàn)=f，f為新增加的一個終態(tài)符號，fVN ，Q=VNf 的定義為： 若文法G有產(chǎn)生式Aa，其中AVN，aVT，則(A,a)=f。 若文法G有產(chǎn)生式AaA1|aA2||aAk，

40、其中A,AiVN,(i=1,2,,k),aVT，則(A,a)=A1,A2,,Ak。,68,L(G)的充要條件是L(M)，所以L(G)=L(M),在正規(guī)文法G中，開始符號S推導(dǎo)出的充分必要條件為：在自動機(jī)M中，從初態(tài)S到終態(tài)f有一條路徑，該路徑上所有邊的標(biāo)記依次連接起來恰好是。 現(xiàn)在考慮左線性正規(guī)文法 設(shè)給定的一個左線性文法G為：G=(VT，VN，S，) 與G等價(jià)的有限自動機(jī)M為：M=(，Q，q0，F(xiàn)，) =VT，F(xiàn)=S，新增加一個初態(tài)符號q0，q0VN，Q=VNq0 的定義為： 若文法G有產(chǎn)生式Aa，其中AVN，aVT，則(q0,a)=A。 若文法G有產(chǎn)生式A1Aa，A2Aa，，AkA

41、a， 其中A,AiVN,(i=1,2,,k),aVT，則(A,a)=A1,A2,,Ak 可以證明L(G)=L(M)，即 有限自動機(jī)M與左線性文法G是等價(jià)的。,69,例：設(shè)有右線性文法G=(a,b, S,B, S, )，其中： SaB BaB|bS|a 試構(gòu)造與G等價(jià)的有限自動機(jī)M。,設(shè)FA M=(, Q, q0, F, ) =a,b q0=S F=f Q=S,B,f 轉(zhuǎn)換函數(shù)： 對于產(chǎn)生式SaB，有(S,a)=B 對于產(chǎn)生式BaB，有(B,a)=B 對于產(chǎn)生式BbS，有(B,b)=S 對于產(chǎn)生式Ba， 有(B,a)=f FA M的狀態(tài)轉(zhuǎn)換圖：,70,定理：對每一個DFA M，都存在一個等價(jià)

42、的右線性文 法G和一個等價(jià)的左線性文法G。,設(shè)DFA M為：M=(，Q，q0，F(xiàn)，) 構(gòu)造右線性文法G：G=(VT，VN，S，) VT=、VN=Q、S=q0 的構(gòu)造：對任何a，及A、BQ，若存在(A,a)=B，則： 如果BF，則有AaB 如果BF，則有AaB|a 證明L(M)=L(G) 首先證明被DFA M接受的語言可以由右線性文法G產(chǎn)生 對任何L(M),設(shè)=a1a2an，ai，存在狀態(tài)序列：q0,q1,,qn-1,q qF，有轉(zhuǎn)換函數(shù)(q0,a1)=q1，(q1,a2)=q2，，(qn-1,an)=q 因此在文法G中有產(chǎn)生式：q0a1q1, q1a2q2,, qn-1an 于是有推導(dǎo)序列

43、：q0a1q1a1a2q2a1a2an-1qn-1a1a2an 因此，a1a2an是文法G生成的一個句子，即L(G)，因此L(M)L(G),71,再證明由文法G產(chǎn)生的語言，能夠被DFA M所接受。,對任何L(G)，設(shè)=a1a2an，其中aiVT，必存在推導(dǎo)序列： q0a1q1a1a2q2a1a2an-1qn-1a1a2an DFA M中有轉(zhuǎn)換函數(shù)：(q0,a1)=q1,(q1,a2)=q2,,(qn-1,an)=q,并且qF 在DFA M中有一條從q0出發(fā)、依次經(jīng)過狀態(tài)q1,q2,,qn-1再到達(dá)終態(tài)q的道路，路徑上有向邊的標(biāo)記依次為a1,a2,,an-1,an，這些標(biāo)記依次連接起來恰好是，所

44、以被DFA M所接受，即L(M)，因此L(G)L(M)。 若q0F，則=L(M)，但L(G)，即：L(G)=L(M)- 進(jìn)一步改進(jìn)文法G：增加一個新的非終結(jié)符號S，及相應(yīng)產(chǎn)生式：SS|，并用S代替S作為文法的開始符號。 改進(jìn)后的文法G仍是右線性文法，并且滿足：L(M)=L(G)。 推論：對任何一個有限自動機(jī)M，都存在一個等價(jià)的 正規(guī)文法G，反之亦然。 推論：對任何一個右線性文法G，都存在一個等價(jià)的 左線性文法G，反之亦然。,72,例：設(shè)有DFA M=(a,b, q0,q1,q2,q3,q0,q3,) 其中轉(zhuǎn)換函數(shù)如下： (q0,a)=q1, (q1,a)=q3, (q2,a)=q2 (q

45、0,b)=q2, (q1,b)=q1, (q2,b)=q3 試構(gòu)造與之等價(jià)的右線性文法G。,DFA M的狀態(tài)轉(zhuǎn)換圖,構(gòu)造右線性文法G=(VT,VN,S,) VT=a,b VN=q0,q1,q2,q3 S=q0 產(chǎn)生式集合 (q0,a)=q1， q0aq1 (q0,b)=q2， q0bq2 (q1,a)=q3，q3F， q1a|aq3 (q1,b)=q1， q1bq1 (q2,a)=q2， q2aq2 (q2,b)=q3，q3F， q2b|bq3,構(gòu)造的文法G： G=(a,b,q0,q1,q2,q0,) ：q0aq0|bq2 q1a|bq1 q2aq2|b,73,2.4 正規(guī)表達(dá)式與有限自動

46、機(jī)的等價(jià)性,用正規(guī)表達(dá)式可以精確地定義集合， 定義Pascal語言標(biāo)識符的正規(guī)表達(dá)式： letter(letter|digit)* 定義：字母表上的正規(guī)表達(dá)式 (1) 是正規(guī)表達(dá)式，它表示的語言是 (2) 如果a，則a是正規(guī)表達(dá)式，它表示的語言是a (3) 如果r和s都是正規(guī)表達(dá)式,分別表示語言L(r)和L(s),則： 1) (r)|(s) 是正規(guī)表達(dá)式，表示的語言是L(r)L(s) 2) (r)(s) 是正規(guī)表達(dá)式，表示的語言是L(r)L(s) 3) (r)* 是正規(guī)表達(dá)式，表示的語言是(L(r))* 4) (r) 是正規(guī)表達(dá)式，表示的語言是L(r) 正規(guī)表達(dá)式表示的語言叫做正規(guī)

47、集。,74,正規(guī)表達(dá)式的書寫約定,一元閉包*具有最高優(yōu)先級，并且遵從左結(jié)合 連接運(yùn)算的優(yōu)先級次之，遵從左結(jié)合 并運(yùn)算|的優(yōu)先級最低，遵從左結(jié)合 例：如果=a，b，則有： 正規(guī)表達(dá)式 a|b 表示集合 a，b (a|b)(a|b) 表示：aa，ab，ba，bb a* 表示：由0個或多個a組成的所有符號串的集合 a|a*b 表示：a和0個或多個a后跟一個b的所有符號串的集合 (a|b)* 表示：由a和b構(gòu)成的所有符號串的集合 (a*|b*)* 如果兩個正規(guī)表達(dá)式r和s表示同樣的語言，即L(r)=L(s),則稱r和s等價(jià)，寫作r=s。 如：(a|b)=(b|a),75,正規(guī)表達(dá)式

48、遵從的代數(shù)定律,76,定理：對任何一個正規(guī)表達(dá)式r，都存在一個FA M， 使L(r)=L(M)，反之亦然。,證1：設(shè)r是上的一個正規(guī)表達(dá)式，則存在一個具有-轉(zhuǎn)移的NFA M接受L(r)。 首先，為正規(guī)表達(dá)式r構(gòu)造如下圖所示的拓廣轉(zhuǎn)換圖。,然后，按照下面的轉(zhuǎn)換規(guī)則，對正規(guī)表達(dá)式r進(jìn)行分裂、加入新的結(jié)點(diǎn)，直到每條邊的標(biāo)記都為基本符號為止。,77,證2：設(shè)有FA M，則存在一個正規(guī)表達(dá)式r，它表示的語言即該FA M所識別的語言。,首先，在FA M的轉(zhuǎn)換圖中增加兩個結(jié)點(diǎn)i和f，并且增加邊，將i連接到M的所有初態(tài)結(jié)點(diǎn)，并將M的所有終態(tài)結(jié)點(diǎn)連接到f。形成一個新的與M等價(jià)的NFA N。 然后，反復(fù)利用下面

49、的替換規(guī)則，逐步消去N中的中間結(jié)點(diǎn)，直到只剩下結(jié)點(diǎn)i和f為止。,78,例：為正規(guī)表達(dá)式(a|b)*abb，構(gòu)造等價(jià)的NFA。,構(gòu)造過程：,79,例：構(gòu)造與如下的NFA M等價(jià)的正規(guī)表達(dá)式r。,80,2.5 正規(guī)表達(dá)式與正規(guī)文法的等價(jià)性,正規(guī)表達(dá)式與正規(guī)文法具有同樣的表達(dá)能力 對任何一個正規(guī)表達(dá)式都可以找到一個正規(guī)文法，使這個正規(guī)文法所產(chǎn)生的語言（即正規(guī)語言）恰好是該正規(guī)表達(dá)式所表示的語言（即正規(guī)集），反之亦然。 正規(guī)表達(dá)式和正規(guī)文法都可以用來描述程序設(shè)計(jì)語言中單詞符號的結(jié)構(gòu) 用正規(guī)表達(dá)式描述，清晰而簡潔； 用正規(guī)文法描述，易于識別。,81,正規(guī)定義式,定義：令是字母表，正規(guī)定義式是如下形式的定

50、義序列： d1r1 d2r2 dnrn 其中di是不同的名字，ri是d1,d2,,di-1上的正規(guī)表達(dá)式。 例：Pascal語言的無符號數(shù)可用如下的正規(guī)表達(dá)式來描述： digit+(.digit+|)(E(+|-|)digit+|) 正規(guī)定義式： digit 0|1||9 digits digit digit* optional_fraction .digits| optional_exponent (E(+|-|)digits)| num digits optional_fraction optional_exponent,82,表示的縮寫,引入正閉包運(yùn)算符+ r*=r+|、 r+=

51、rr* digits digit+ 引入可選運(yùn)算符？ r?=r| optional_fraction (.digits)? optional_exponent (E(+|-)?digits)? 引入表示 字符組abc，表示正規(guī)表達(dá)式a|b|c digit 0-9 標(biāo)識符的正規(guī)表達(dá)式：A-Za-zA-Za-z0-9*,83,正規(guī)表達(dá)式轉(zhuǎn)換為等價(jià)的正規(guī)文法,例：Pascal語言標(biāo)識符的正規(guī)表達(dá)式： letter(letter|digit)* 引入名字letter、digit、和id 正規(guī)定義式： letter A|B||Z|a|b||z digit 0|1||9 id letter(letter

52、|digit)* 關(guān)鍵：如何把正規(guī)定義式轉(zhuǎn)換為相應(yīng)的正規(guī)文法 分析： 為子表達(dá)式(letter|digit)* 取一個名字rid 展開第三個正規(guī)定義,84,正規(guī)文法,(letter|digit)* = | (letter|digit)+ = | (letter|digit) (letter|digit)* = | letter(letter|digit)* | digit(letter|digit)* = | (A|B||Z|a|b||z)(letter|digit)* | (0|1||9)(letter|digit)* = | A(letter|digit)* | B(letter|digi

53、t)* | | Z(letter|digit)* | a(letter|digit)* | b(letter|digit)* | | z(letter|digit)* | 0(letter|digit)* | 1(letter|digit)* | | 9(letter|digit)* id和rid看成是文法的非終結(jié)符號，產(chǎn)生式： id A rid|B rid||Z rid|a rid|b rid||z rid rid |A rid|B rid||Z rid|a rid|b rid||z rid|0 rid|1 rid||9 rid 把letter和digit看作是終結(jié)符號，產(chǎn)生式： id

54、 letter rid rid | letter rid | digit rid,85,正規(guī)文法的產(chǎn)生式和正規(guī)定義式中的正規(guī)定義,兩個不同的概念，具有不同的含義。 產(chǎn)生式：左部是一個非終結(jié)符號，右部是一個符合特定形式的文法符號串，中的非終結(jié)符號可以與該產(chǎn)生式左部的非終結(jié)符號相同，即允許非終結(jié)符號的遞歸出現(xiàn)。 正規(guī)定義：左部是一個名字，右部是一個正規(guī)表達(dá)式，表達(dá)式中出現(xiàn)的名字是有限制的，即只能是此定義之前已經(jīng)定義過的名字。,86,小 結(jié),字母表和符號串 前綴、后綴、子串、子序列、真前綴、真后綴、真子串 連接、冪 語言 語言的運(yùn)算：并、連接、閉包、正閉包 文法 形式定義G=(VT,VN,S,)

55、文法的分類 上下文無關(guān)文法（A） 正規(guī)文法 右線性文法（AaB Aa） 左線性文法（ABa Aa）,87,推導(dǎo) 一步推導(dǎo)、直接推導(dǎo)、推導(dǎo)的長度 最左推導(dǎo)、最右推導(dǎo)、規(guī)范推導(dǎo) 句型、左句型、右句型、規(guī)范句型 句子,短語 短語、直接短語、句柄,分析樹及二義性 分析樹、子樹 子樹與短語之間的關(guān)系 子樹短語 只有父子兩代的子樹直接短語 最左邊的只有父子兩代的子樹句柄 句子二義性、文法的二義性、語言的二義性,88,文法的變換 文法的改寫 左遞歸的消除 簡單的直接左遞歸的消除 間接左遞歸的消除算法 改寫文法為無-產(chǎn)生式的文法 提取左公因子,有限自動機(jī) 形式定義M=(,Q,q0,F,) DFA： ：QQ NFA： ：Q2Q 具有-轉(zhuǎn)移的NFA： ：Q()2Q 自動機(jī)之間的等價(jià)性 NFA確定化 具有-轉(zhuǎn)移的NFA的確定化,89,DFA的最小化 狀態(tài)等價(jià)、狀態(tài)可區(qū)分 將DFA的狀態(tài)集合劃分為等價(jià)狀態(tài)子集,正規(guī)文法與有限自動機(jī)之間的等價(jià)性 為右線性文法構(gòu)造DFA 為DFA構(gòu)造右線性文法 正規(guī)表達(dá)式與有限自動機(jī)之間的等價(jià)性 為NFA構(gòu)造正規(guī)表達(dá)式 為正規(guī)表達(dá)式構(gòu)造NFA 正規(guī)表達(dá)式與正規(guī)文法之間的等價(jià)性 同等表達(dá)能力 利用正規(guī)定義式，將正規(guī)表達(dá)式轉(zhuǎn)換為正規(guī)文法,