形式語言與自動機.ppt

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

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

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

3、后綴或子串，并且，則稱是的真前綴、真后綴、或真子串。 子序列 符號串的子序列是指從中刪除0個或多個符號(這些符號可以是不連續(xù)的)后得到的符號串。如：nvst,6,連接,符號串和符號串的連接是把符號串加在符號串之后得到的符號串 若=ab，=cd，則=abcd，=cdba。 對任何符號串來說，都有== 冪 若是符號串，的n次冪n 定義為：,當n=0時，0是空串。 假如=ab，則有： 0= 1=ab 2=abab ,7,二、語言,語言：在某一確定字母表上的符號串的集合。 空集，集合也是符合此定義的語言。 這個定義并沒有把任何意義賦予語言中的符號串。 語言的運算：假設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看作是語言 語言運算舉例：,把冪運算推廣到語言 L0=，Ln=Ln-1L，于是Ln是語言L與其自身的n-1次連接。,9,三、文法及其形式定義,文法：所謂文法就是描述語言的語法結構的形式規(guī)則。 任何一個文法都可以表示為一個四元組G=(VT,VN,S, ) VT是一個非空的有限集

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

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

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

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

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

10、 ,21,五、分析樹及二義性,分析樹 子樹 子樹與短語之間的關系 二義性,22,分析樹,推導的圖形表示，又稱推導樹。 一棵有序有向樹，因此具有樹的性質(zhì)； 自己的特點：每一個結點都有標記。 根結點由文法的開始符號標記； 每個內(nèi)部結點由非終結符號標記，它的子結點由這個非終結符號的這次推導所用產(chǎn)生式的右部各符號從左到右依次標記； 葉結點由非終結符號或終結符號標記，它們從左到右排列起來，構成句型。 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、,分析樹中一個特有的結點、連同它的全部后裔結點、連接這些結點的邊、以及這些結點的標記。 子樹的根結點的標記可能不是文法的開始符號。 如果子樹的根結點標記為非終結符號A，則可稱該子樹為A-子樹。,24,,子樹與短語的關系,一棵子樹的所有葉結點自左至右排列起來，形成此句型相對于該子樹根的短語； 分析樹中只有父子兩代的子樹的所有葉結點自左至右排列起來，形成此句型相對于該子樹根的直接短語； 分析樹中最左邊的那棵只有父子兩代的子樹的所有葉結點自左至右排列起來，就是該句型的句柄。,25,二義性,如果一個文法的某個句子有不止一棵分析樹，則這個句子是二義性的。 含有二義性句子的文法是二義性的文法。 例：考慮文

12、法 G=(+,*,（,）,i,E,E,) ： E E+E | E*E | (E) | id 句子 id+id*id 存在兩個不同的最左推導： 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)，則稱這兩個文法是等價的。 有時，一個二義性的文法可以變換為一個等價的、無二義性的文法。 有些語言，根本就不存在無二義性的文法，這樣的語言稱為二義性的語言。 二義性問題是不可判定的 不存在一種算法，它能夠在有限的步驟內(nèi)確切地判定出一個

13、文法是否是二義性的。 可以找出一些充分條件（未必是必要條件），當文法滿足這些條件時，就可以確信該文法是無二義性的。,27,六、文法的變換,文法二義性的消除 左遞歸的消除 提取左因子,28,文法二義性的消除,映射程序設計語言中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,左遞歸的消除,一個文法是左遞歸的，如果它有非終結符

15、號A，對某個文法符號串，存在推導：,消除左遞歸的方法： 簡單情況：如果文法G有產(chǎn)生式：AA| 可以把A的這兩個產(chǎn)生式改寫為：AA AA| 這兩組產(chǎn)生式是等價的 由于從A推導出的符號串是相同的，即都是,若存在某個=，則稱該文法是有環(huán)路的。,32,例：消除表達式文法中的左遞歸： EE+T|T TT*F|F F(E)|id,利用消除直接左遞歸的方法，可以改寫為: ETE E+TE | TFT T*FT | F(E) | id,33,一般情況：假定關于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等價的文法G 方法： (1)把文法G的所有非終結符號按某種順序排列成A1,A2,,An (2)for (i=1; i<=n; i++) for (j=1; j<=i-1; j++) if (Aj1|2||k是關于當前Aj的所有產(chǎn)生式) 把每個形如AiAj的產(chǎn)生式改寫為：Ai1|2||k； 消除關于Ai的產(chǎn)生式中的直接左遞歸; (3)化簡第(2)步得到的文法，即去除無用的非終結符號

17、和產(chǎn)生式。 這種方法得到的非遞歸文法可能含有-產(chǎn)生式。,35,為含有-產(chǎn)生式的文法G=(VT,VN,S,) 構造不含-產(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滿足：,一個文法是-無關的， 如果它沒有-產(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 消除其中的左遞歸： 第一步，把文法的非終結符號排列為S、A； 第二步，由于S不存在直接左遞歸，所以算法第2步在i=1時不做工作； 在i=2時，把產(chǎn)生式SAa|a|b代入A的有關產(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,例：映射程序設計語言中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 有限自動機,有限自動機是具有離散輸入與輸出的系統(tǒng)的一種數(shù)學模型 系統(tǒng)可處于有限個內(nèi)部狀態(tài)的任何一個之中 系統(tǒng)的當前狀態(tài)概括了有關過去輸入的信息 例：自動電梯的控制機構 “確定的有限自動機”指，在當前狀態(tài)下，輸入一個符號，有限

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

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

22、單值映射 轉(zhuǎn)換函數(shù)(q,a)=q (其中q,qQ,a）表示當前狀態(tài)為q，輸入符號為a時，自動機將轉(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列的矩陣 每一行對應M的一個狀態(tài) 每一列對應M的一個輸入符號,DFA M可用一張狀態(tài)轉(zhuǎn)

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

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

25、若存在一條從初態(tài)結點到終態(tài)結點的路徑，該路徑上每條邊的標記連接成的符號串恰好是，則稱為NFA M所識別。 NFA M所能識別的符號串的全體記為L(M)，稱為NFA M所識別的語言。 如果q0F 存在一條從初態(tài)結點到終態(tài)結點的-道路 空串可為該NFA M所識別，即 L(M),48,例：設有 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，都存在一個與之等價的 DFA D，即L(M)=L(D)。,例：

26、構造與下面的NFA M等價的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)換圖,假設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,的構成 (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,子集構造法：構造與NFA M等價的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)移的非確定有限自動機,定義：一個具有-轉(zhuǎn)移的非確定有限自動機M(記作：NFA M) 是一個五元組 M=(，Q，q0，F(xiàn)，) 其中 ：是一個字母表，它的每個元素稱為一個輸入符號 Q：是一個有限的狀態(tài)集

28、合 q0Q：q0稱為初始狀態(tài) FQ：F稱為終結狀態(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)換圖 圖中可能有標記為的邊 當(q,)=q1,q2,,qk時，從q出發(fā)有k條標記為的邊分別指向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,假設 NFA N=(a,b,0,1,2,3,4,0,F,) _closure(q)：從狀態(tài)q出發(fā)，經(jīng)過-道路可以到達的所有狀態(tài)的集合。 F的構成：,定理：對任何一個具有-轉(zhuǎn)移的NFA M，都存在一個 等價的不具有-轉(zhuǎn)移的NFA N，即L(M)=L(N)。,例：構造與NFA M 等價的不具有-轉(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,的構成：,(q,a)=q| q為從q出發(fā),經(jīng)過標記

30、為a的道路所能到達的狀態(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，都存在 一個與之等價的DFA D，即L(M)=L(D)。,DFA D的每個狀態(tài)對應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、達狀態(tài)q,從T中任一狀態(tài)出發(fā)，經(jīng)過-道路后可以到達的狀態(tài)集合。 move(T,a)=q | (qi,a)=q，其中qiT 從某個狀態(tài)qiT出發(fā)，經(jīng)過輸入符號a之后可到達的狀態(tài)集合。,57,算法：計算_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構造等價的DFA,輸入：一個NFA M 輸出：一個與NFA M等價（即接受同樣語言）的DFA D 方法：為D

32、FA D構造狀態(tài)轉(zhuǎn)換表DTT 初態(tài)：_closure(q0)是DQ中唯一的狀態(tài)，且未標記。 while (DQ中存在一個未標記的狀態(tài)T) 標記 T； for (each a) U=_closure(move(T,a))； if (UDQ) 把U做為一個未標記的狀態(tài)加入DQ； DTTT,a：=U; ,59,例：構造與下面的NFA M等價的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)，因為E的狀態(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及與之相連接的邊，可以得到等價的狀態(tài)轉(zhuǎn)換圖,L(M)=0(10)* 對于任何一個含有n個狀態(tài)的DFA，都存在含有m(mn)個狀態(tài)的DFA與之等價。 DFA D的化簡，指尋找一個狀態(tài)數(shù)比較少的DFA D，使L(D)=L(D)。 可以證明，存在一個最少狀態(tài)的DFA D，使L(D)=L(D)，并且這個D是唯一的。,62,,DFA D的最小化過程,定義：設s,tQ，若對任何*， (s,)F

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

37、換。 如果A中的狀態(tài)相對于a，轉(zhuǎn)換到不同子集中的狀態(tài)，則要對A進行劃分。使A中能夠轉(zhuǎn)換到同一子集的狀態(tài)作為一個新的子集。 重復上述過程，直到每個子集都不能再劃分為止。,64,例：對狀態(tài)轉(zhuǎn)換圖所描述的DFA D最小化,第一步：把DFA D的狀態(tài)集合劃分為子集，使每個子集中的狀態(tài)相互等價，不同子集中的狀態(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)。 - 應把子集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分屬于不同的子集。 - 應把子集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,構造最小DFA D,第二步：為每個子集選擇一個代表狀態(tài)。 選擇A

39、為子集A,C的代表狀態(tài) D的狀態(tài)轉(zhuǎn)換圖,D的狀態(tài)轉(zhuǎn)換矩陣,67,2.3 正規(guī)文法與有限自動機的等價性,如果對于某個正規(guī)文法G和某個有限自動機M，有L(G)=L(M)，則稱G和M是等價的。 定理：對每一個右線性文法G或左線性文法G，都存在一個等價的有限自動機M。 證明：首先考慮右線性正規(guī)文法 設給定的一個右線性文法G為：G=(VT，VN，S，) 與G等價的有限自動機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推導出的充分必要條件為：在自動機M中，從初態(tài)S到終態(tài)f有一條路徑，該路徑上所有邊的標記依次連接起來恰好是。 現(xiàn)在考慮左線性正規(guī)文法 設給定的一個左線性文法G為：G=(VT，VN，S，) 與G等價的有限自動機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)，即 有限自動機M與左線性文法G是等價的。,69,例：設有右線性文法G=(a,b, S,B, S, )，其中： SaB BaB|bS|a 試構造與G等價的有限自動機M。,設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，都存在一個等價

42、的右線性文 法G和一個等價的左線性文法G。,設DFA M為：M=(，Q，q0，F(xiàn)，) 構造右線性文法G：G=(VT，VN，S，) VT=、VN=Q、S=q0 的構造：對任何a，及A、BQ，若存在(A,a)=B，則： 如果BF，則有AaB 如果BF，則有AaB|a 證明L(M)=L(G) 首先證明被DFA M接受的語言可以由右線性文法G產(chǎn)生 對任何L(M),設=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 于是有推導序列

43、：q0a1q1a1a2q2a1a2an-1qn-1a1a2an 因此，a1a2an是文法G生成的一個句子，即L(G)，因此L(M)L(G),71,再證明由文法G產(chǎn)生的語言，能夠被DFA M所接受。,對任何L(G)，設=a1a2an，其中aiVT，必存在推導序列： 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再到達終態(tài)q的道路，路徑上有向邊的標記依次為a1,a2,,an-1,an，這些標記依次連接起來恰好是，所

44、以被DFA M所接受，即L(M)，因此L(G)L(M)。 若q0F，則=L(M)，但L(G)，即：L(G)=L(M)- 進一步改進文法G：增加一個新的非終結符號S，及相應產(chǎn)生式：SS|，并用S代替S作為文法的開始符號。 改進后的文法G仍是右線性文法，并且滿足：L(M)=L(G)。 推論：對任何一個有限自動機M，都存在一個等價的 正規(guī)文法G，反之亦然。 推論：對任何一個右線性文法G，都存在一個等價的 左線性文法G，反之亦然。,72,例：設有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。,DFA M的狀態(tài)轉(zhuǎn)換圖,構造右線性文法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： G=(a,b,q0,q1,q2,q0,) ：q0aq0|bq2 q1a|bq1 q2aq2|b,73,2.4 正規(guī)表達式與有限自動

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

47、集。,74,正規(guī)表達式的書寫約定,一元閉包*具有最高優(yōu)先級，并且遵從左結合 連接運算的優(yōu)先級次之，遵從左結合 并運算|的優(yōu)先級最低，遵從左結合 例：如果=a，b，則有： 正規(guī)表達式 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構成的所有符號串的集合 (a*|b*)* 如果兩個正規(guī)表達式r和s表示同樣的語言，即L(r)=L(s),則稱r和s等價，寫作r=s。 如：(a|b)=(b|a),75,正規(guī)表達式

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

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

50、義序列： d1r1 d2r2 dnrn 其中di是不同的名字，ri是d1,d2,,di-1上的正規(guī)表達式。 例：Pascal語言的無符號數(shù)可用如下的正規(guī)表達式來描述： 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,表示的縮寫,引入正閉包運算符+ r*=r+|、 r+=

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

52、|digit)* 關鍵：如何把正規(guī)定義式轉(zhuǎn)換為相應的正規(guī)文法 分析： 為子表達式(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看成是文法的非終結符號，產(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看作是終結符號，產(chǎn)生式： id

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

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