形式語言與自動機week4-ch37-39a

1、1College of Computer Science & Technology, BUPT 正則表達式與有限自動機的關系正則表達式與有限自動機的關系 右線性語言與有限自動機的關系右線性語言與有限自動機的關系 右線性語言的性質(zhì)右線性語言的性質(zhì)(part1)第四講第四講2College of Computer Science & Technology, BUPT3.7 正則表達式與有限自動機的關系結(jié)論結(jié)論: 有限自動機、右（左）線性文法、正則表有限自動機、右（左）線性文法、正則表達式都定義了同一種語言達式都定義了同一種語言- 正則語言正則語言 . 證明策略證明策略 - NFANFADFARER

2、E( Regular Expression) - 正則表達式3College of Computer Science & Technology, BUPT從從 DFA 構造等價的構造等價的正則表達式正則表達式（狀態(tài)消去法）（狀態(tài)消去法）思路思路: : (1) 擴展自動機的概念，允許正則表達式作為轉(zhuǎn)移弧的標記. 這樣，就有可能在消去某一中間狀態(tài)時，保證自動機能夠接受的字符串集合保持不變. (2) 在消去某一中間狀態(tài)時，與其相關的轉(zhuǎn)移弧也將同時消去，所造成的影響將通過修改從每一個前趨狀態(tài)到每一個后繼狀態(tài)的轉(zhuǎn)移弧標記來彌補. 以下分別介紹中間狀態(tài)的消去與正則表達式構造過程.4College of C

3、omputer Science & Technology, BUPT從從 DFA 構造等價的構造等價的正則表達式正則表達式（中間狀態(tài)的消去）（中間狀態(tài)的消去）xy r1r2xz r1y r2代之以：xy r1+r2xyr2r1代之以：xy r1*xz y r1代之以：5College of Computer Science & Technology, BUPT從從 DFA 構造等價的構造等價的正則表達式正則表達式（中間狀態(tài)的消去）（中間狀態(tài)的消去）sSq1qkp1pmP1PmQkQ1R11R1mRkmRk1R11+ Q1S* P1R1m+ Q1S* PmRkm+ QkS* PmRk1 + Qk

4、S* P1q1p1qkpm消去消去 s6College of Computer Science & Technology, BUPT從從 DFA 構造等價的構造等價的正則表達式正則表達式（狀態(tài)消去法）（狀態(tài)消去法）步驟步驟: : (1) 對每一終態(tài)對每一終態(tài)q，依次消去除依次消去除 q 和初態(tài)和初態(tài) q0 之外的其它狀態(tài)之外的其它狀態(tài); ;StartRStartSTUR(2) 若若q q0，最終可得到一般最終可得到一般形式如下左圖形式如下左圖兩狀態(tài)自動機，兩狀態(tài)自動機， 該自動機對應的正則表達式可表示為該自動機對應的正則表達式可表示為 ( R+SU*T )*SU*.(3) 若若q= q0，最終

5、可得到最終可得到如下右圖的自動機，它對應的正則如下右圖的自動機，它對應的正則 表達式可以表示為表達式可以表示為 R*.(4) 最終最終的正則表達式為的正則表達式為每一終態(tài)對應的每一終態(tài)對應的 正則表達式之和（并）正則表達式之和（并）.7College of Computer Science & Technology, BUPT狀態(tài)消去法舉例狀態(tài)消去法舉例A0+1StartBCD10+10+1對于終態(tài)對于終態(tài)CA0+1StartC1(0+1)A0+1StartD1(0+1)(0+1)對于終態(tài)對于終態(tài)D等價的正則表達式等價的正則表達式(0+1)*1(0+1)+(0+1)*1(0+1)(0+1)8C

6、ollege of Computer Science & Technology, BUPT狀態(tài)消去法舉例狀態(tài)消去法舉例01342567 a b aa b b a b012567a+ba+b aabb0257(a+b)*(a+b)*aa+bb07(a+b)* (aa+bb) (a+b)*9College of Computer Science & Technology, BUPT定理定理: L 是正則表達式是正則表達式 R 表示的語言表示的語言, 則存在一個則存在一個 - NFA E ,滿足滿足 L(E) = L(R) = L. 證明證明: 構造性證明構造性證明. 可以通過結(jié)構歸納法證明從可以通

7、過結(jié)構歸納法證明從 R 可以構可以構造出與其等價的，滿足如下條件的造出與其等價的，滿足如下條件的 - NFA ： (1) 恰好一個終態(tài)恰好一個終態(tài); (2) 沒有弧進入初態(tài)；沒有弧進入初態(tài)； (3) 沒有弧離開終態(tài)；沒有弧離開終態(tài)； 從從正則表達式正則表達式構造等價的構造等價的 - NFA10College of Computer Science & Technology, BUPT基礎基礎: :從從正則表達式正則表達式構造等價的構造等價的 - NFA（歸納歸納構造過程）構造過程）1 對于對于 ，構造為構造為 3 對于對于 a ，構造為構造為a2 對于對于 ，構造為構造為11College o

8、f Computer Science & Technology, BUPT歸納歸納: :從從正則表達式正則表達式構造等價的構造等價的 - NFA（歸納歸納構造過程）構造過程）1 對于對于 R+S ，構造為構造為SR 12College of Computer Science & Technology, BUPT歸納歸納: :從從正則表達式正則表達式構造等價的構造等價的 - NFA（歸納歸納構造過程）構造過程）2 對于對于 RS ，構造為構造為RS R3 對于對于 R* ，構造為構造為 13College of Computer Science & Technology, BUPT舉例舉例: :

9、 設設正則表達式正則表達式 1*0(0+1)*, 構造等價的構造等價的 - NFA.從從正則表達式正則表達式構造等價的構造等價的 - NFA100+1 11* 14College of Computer Science & Technology, BUPT從從正則表達式正則表達式構造等價的構造等價的 - NFA(0+1)*10 11001*0(0+1)* 15College of Computer Science & Technology, BUPT3.8 右線性語言與右線性語言與有限自動機有限自動機 至此，我們已學到正則集有三種定義方式，且這三種方式等價： 正則集是含有，a 以及在并、連接和

10、 * 運算下封閉的語言 由正規(guī)表達式定義的集合是正則集。 由右線性文法生成的語言是正則集。此外，還有第四種方式： 將正則集作為由有限自動機定義的集合。即 正則集(右線性語言) 有限自動機16College of Computer Science & Technology, BUPT右線性文法右線性文法 有限自動機有限自動機定理定理3.8.1：由任意右線性文法G定義的語言必然能被一個NFA M所接受。即L（G）L（M）證明思路（構造證明）證明思路（構造證明）：設右線性文法G（N，T，P，S），構造一個與G等價的有限自動機NFA M（Q，T，q0，F(xiàn)），其中： QN U H，H為一個新增加的狀態(tài),

11、 HN， q0S H，S 當S-屬于P。 H 否則 的定義為：的定義為：當當A a B P，則則 B （A，a）當當A a P, 則則 H （A，a）對于任意輸入，（H，a）。F=17College of Computer Science & Technology, BUPT右線性文法右線性文法 有限自動機有限自動機（例）例：例：設有右線性文法設有右線性文法G=(S,B ,a,b, P,S)，其中其中P： SaB BaB|bS|a 試構造與試構造與G等價的有限自動機等價的有限自動機M。解：解： 設設NFA M=(Q,T, , q0, F)Q=S,B,H T=a,b q0 = S F =H轉(zhuǎn)換函

12、數(shù)轉(zhuǎn)換函數(shù) ：n對于產(chǎn)生式對于產(chǎn)生式SaB，有有(S,a)=Bn對于產(chǎn)生式對于產(chǎn)生式BaB，有有(B,a)=Bn對于產(chǎn)生式對于產(chǎn)生式BbS，有有(B,b)=Sn對于產(chǎn)生式對于產(chǎn)生式Ba， 有有(B,a)=HSBH開始aaab18College of Computer Science & Technology, BUPT右線性文法右線性文法 有限自動機有限自動機（續(xù)）（續(xù)）求證求證 G與與NFA M兩者定義了同一語言。兩者定義了同一語言。 證明：證明： 先證（先證（1）文法）文法G產(chǎn)生的語言產(chǎn)生的語言 L(G) 能夠被能夠被NFA M所接收；所接收；再證（再證（2）NFA M 接受的語言接受的語

13、言 L(M) 可由文法可由文法G 產(chǎn)生。產(chǎn)生。19College of Computer Science & Technology, BUPT右線性文法右線性文法 有限自動機有限自動機（續(xù)）（續(xù)）證明方法：證明方法：通過兩者定義的語言中任意一個字符串來說明。（1）設 = a1a2anL(G) ，且n 1則有 S a1A1 a1a2A2 a1a2an-1An-1 a1a2 an-1a n則由的定義，有A1 (S，a1)，A2 (A1，a2), ,An-1 (An-2，an-1)，H (An-1，an)，且 H (S，)因為H F, 所以被NFA M 所接受。又若L（G）, 則表明 S P ,由

14、NFA M 的定義，有S F, 即也被NFA M接受。所以，由文法所以，由文法G派生的任意字符串派生的任意字符串 L（M）。 #20College of Computer Science & Technology, BUPT右線性文法右線性文法 有限自動機有限自動機（續(xù)）（續(xù)）（2）再證再證 L(M)可由可由G產(chǎn)生產(chǎn)生設 = a1a2an 被NFA M接受，即 L（M），則必然存在狀態(tài)序列 S， A1，A2 ， An-1，H對M有轉(zhuǎn)換函數(shù)為A1 (S，a1)，A2 (A1，a2), ,An-1 (An-2，an-1)，H (An-1，an)則可規(guī)定G中含有產(chǎn)生式S a1A1， A1 a2A2

15、， ，An-1 a n于是存在推導S a1A1 a1a2A2 a1a2an-1An-1 a1a2 an-1a n即a1a2an 是文法G的一個句子。也即也即 L（G）。）。 #21College of Computer Science & Technology, BUPT課堂練習：課堂練習：練習：練習： 設線性文法設線性文法 G （S，A，B，a，b，P，S） P： S aA | baB | aA aA | aS | bBB bB | b | a構造相應的構造相應的 NFA M。22College of Computer Science & Technology, BUPT有限自動機有限自動機

16、 右線性文法右線性文法定理定理3.8.2：設有限自動機設有限自動機 M 接受的語言為接受的語言為L(M)則存在右線性文法則存在右線性文法G，它產(chǎn)生的語言它產(chǎn)生的語言L(G)L(M)。證明思路：證明思路：構造一個右線性文法構造一個右線性文法G，使它接受由使它接受由NFA M定義的語言。定義的語言。構造方法：構造方法：設設 M（Q，T，q0，F(xiàn)），），構造一個右線性文法構造一個右線性文法G（N，T，P，S），），其中其中NQ， Sq0P定義為：定義為： 若若（A，a）B 且且 B F，則則A aB 在在P中中 若若（A，a）B 且且 B F，則則A a 和和A aB 在在P中中 （注：書上未明確）

17、（注：書上未明確） L（M） L（G） 的證明見書的證明見書 P91 （自學）。自學）。 23College of Computer Science & Technology, BUPT有限自動機有限自動機右線性文法右線性文法（例）例：例：設有設有DFA M =(q0,q1,q2,q3, a,b, , q0, q3 ) 其中轉(zhuǎn)換函數(shù)如圖所示，其中轉(zhuǎn)換函數(shù)如圖所示， 試構造與之等價的右線性文法試構造與之等價的右線性文法G。解：解：構造右線性文法構造右線性文法G=(N,T,P,S)G=(N,T,P,S) N =q N =q0 0,q,q1 1,q,q2 2,q,q3 3 T =a,b S = q

18、T =a,b S = q0 0 產(chǎn)生式集合產(chǎn)生式集合P P(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|bq3q0q1q2q3aaabbb開始構造的文法構造的文法G(G(化簡化簡q q3 3) )：G=(qG=(q0 0,q,q1 1,q,q2 2,a,b, P,q,a,b, P,q0 0) )P： q0aq0|bq2 q1a|bq1 q2aq2|b24College of Computer Science & Technology

19、, BUPT3.9 右線性語言的性質(zhì)右線性語言的性質(zhì)主要內(nèi)容：主要內(nèi)容：DFA的極小化泵浦引理右線性語言的封閉性25College of Computer Science & Technology, BUPT確定有限自動機確定有限自動機DFA的化簡的化簡(極小化極小化)對DFA M的極小化是找出一個狀態(tài)數(shù)比M少的DFA M1，使?jié)M足 L(M) = L(M1) 1等價和可區(qū)分的概念 設DFA M = (Q，T，q0，F(xiàn)) 對不同的狀態(tài)q， qQ 和每個T*，如果有(q，)* (q，) 必有 (q，)* (q，) 且qF，則稱q與q狀態(tài)等價. 記為qq 否則，稱q， q可區(qū)分. 26College

20、 of Computer Science & Technology, BUPT確定有限自動機確定有限自動機DFA的化簡的化簡2不可達狀態(tài) 如果不存在任何T*，使(q，)* (q，)， 則稱狀態(tài)qQ為不可達狀態(tài).3 最小化 若DFA 不存在互為等價狀態(tài)及不可達狀態(tài)，則稱DFA 是最小化的.27College of Computer Science & Technology, BUPT最小化算法最小化算法 一個DFA 的最小化，是把的狀態(tài)集構成一個劃分。即: 任何兩個子集的狀態(tài)都是可區(qū)分的；同一子集中的任何兩個狀態(tài)都是等價的。之后，每個子集用一個狀態(tài)代表，并取一個狀態(tài)名.構成劃分的步驟構成劃分的步

21、驟: 構成基本劃分 =，”， (為終態(tài)集，”為非終態(tài)集) 細分 =1， 2， n， i i = q， q， q當輸入任意字符a時，若i中的狀態(tài)經(jīng)標a的邊可到達的狀態(tài)集的元素分屬于兩個不同的子集中，則將i 細分為兩個子集.重復步驟(2)，直至不可再細分，得到1.若1中有不可達狀態(tài)，將其刪除，1便是最小化的. 28College of Computer Science & Technology, BUPT例例(1) q，q為不可達狀態(tài)，刪除之.(2) Q = q，q，q，q，q, = q，q ，q，q，q 構成基本劃分 =，”(a) 對于= q， q，對字符a，有(q，a)= q，(q，a)= q

22、 q， q 同一子集.對字符b，有(q，b)= q，(q，a)= q q， q 同一子集. = q， q 不能再細分. 可用q表示 狀態(tài).(b) 對于” = q， q， q對a，(q,a)= q，(q,a)= q，(q,a)= q q, q同一子集對b，(q,b)= q，(q,b)= q，(q,b)= q q， q， q 同一子集. 將再分解. = q， q1，q3 ，q1，q3 不可再細分，用q1表示 q，q，q 29College of Computer Science & Technology, BUPT計算狀態(tài)集劃分的算法計算狀態(tài)集劃分的算法 填表法填表法 填表算法（填表算法（tabl

23、e-filling algorithm）基于如下遞歸地基于如下遞歸地 標記可區(qū)分的狀態(tài)偶對的過程標記可區(qū)分的狀態(tài)偶對的過程:- 基礎基礎 如果如果 p 為終態(tài)，而為終態(tài)，而 q 為非終態(tài)，則為非終態(tài)，則 p 和和 q 標記標記 為可區(qū)分的；為可區(qū)分的；- 歸納歸納 設設 p 和和 q 已標記為可區(qū)分的已標記為可區(qū)分的, 如果狀態(tài)如果狀態(tài) r 和和 s 通過某個通過某個 輸入符號輸入符號 a 可分別轉(zhuǎn)移到可分別轉(zhuǎn)移到 p 和和 q ，即即 (r,a)=p , (s,a)=q , 則則 r 和和 s 也標記為可區(qū)分的；也標記為可區(qū)分的； 這是因為：這是因為：若若 p 和和 q 可為字符串可為字符串

24、 w 區(qū)分區(qū)分, 則則 r 和和 s 可可 為字符串為字符串 aw 區(qū)分區(qū)分. （ (r,aw) = (p,w) , (s,aw) = (q,w) ）30College of Computer Science & Technology, BUPT計算狀態(tài)集劃分的算法計算狀態(tài)集劃分的算法 填表法填表法 填表算法舉例填表算法舉例212334455667xxxxxxxxxxxxx651Start3724aaaaaaabbbbbbb(1) 區(qū)分所有終態(tài)和非終態(tài)區(qū)分所有終態(tài)和非終態(tài)(2) 區(qū)分區(qū)分(1,3), (1,4), (2,3), (2,4), (5,6), (5,7)xxxxx(3) 區(qū)分區(qū)分

25、(3,4)x(4) 結(jié)束結(jié)束. 劃分結(jié)果：劃分結(jié)果：1,2, 3, 4, 5, 6,731College of Computer Science & Technology, BUPT通過合并等價的狀態(tài)進行通過合并等價的狀態(tài)進行 DFA 的優(yōu)化的優(yōu)化 步驟步驟 1. 刪除所有從開始狀態(tài)不可到達的狀態(tài)及與其相關的邊刪除所有從開始狀態(tài)不可到達的狀態(tài)及與其相關的邊, 設所得到的設所得到的 DFA 為為 A = (Q, T, , q0 , F ) ； 2. 使用填表算法找出所有等價的狀態(tài)偶對；使用填表算法找出所有等價的狀態(tài)偶對； 3. 根據(jù)根據(jù) 2 的結(jié)果計算當前狀態(tài)集合的劃分塊，每一劃分的結(jié)果計算當前

26、狀態(tài)集合的劃分塊，每一劃分 塊中的狀態(tài)相互之間等價，而不同劃分塊中的狀態(tài)之塊中的狀態(tài)相互之間等價，而不同劃分塊中的狀態(tài)之 間都是可區(qū)分的間都是可區(qū)分的. 包含狀態(tài)包含狀態(tài) q 的劃分塊用的劃分塊用 q 表示表示. 4. 構造與構造與 A 等價的等價的 DFA B = (QB, T, B, q0, FB ) , 其中其中 QB= q | q Q, FB = q | q F, B(q ,a)= (q,a)32College of Computer Science & Technology, BUPT通過合并等價的狀態(tài)進行通過合并等價的狀態(tài)進行 DFA 的優(yōu)化的優(yōu)化 舉例舉例 651Start372

27、4aaaaaaabbbbbbb 劃分結(jié)果：劃分結(jié)果： 1, 2 , 3, 4, 5, 6, 7 等價的狀態(tài)偶對為：等價的狀態(tài)偶對為： （1, 2）,（6, 7） 新的狀態(tài)集合：新的狀態(tài)集合： 1, 3, 4, 5, 6651Start34aaaabbbbba33College of Computer Science & Technology, BUPT最小化的最小化的 DFA 課堂練習課堂練習 最小化下列最小化下列 DFA:651Start3724aaaaaaabbbbbbb 參考結(jié)果參考結(jié)果61Start34aaaabbbb34College of Computer Science & Te

28、chnology, BUPT針對正則語言的針對正則語言的 Pumping 引理引理 正則語言應滿足的一個必要條件 用于判定給定的語言不是正則集。物理意義：物理意義：當給定一個正則集和該集合上一個足夠長的字符串時，在該字符串中能找到一個非空的子串，并使子串重復，從而組成新的字符串。該新串必在同一個正則集內(nèi)。定理：定理：設L是正則集，存在常數(shù)n，對字符串 且n，則可寫成10，其中10n， 0，對所有的0有10i2。證明證明 設設 L 是是 DFA D = (Q, T, , q0 , F ) 的語言，的語言， 取取 n = |Q| 即可即可. 35College of Computer Scienc

29、e & Technology, BUPTDFA 的的“Pumping”特性特性 設 DFA D = (Q, T, , q0 , F ), |Q|=n. 對于任一長度不小于 n 的字符串 w = a1a2am , 其中 mn, akT (1 k m), qQ , 考察如下狀態(tài)序列 p0=q p1=(q, a1) p2=(q, a1a2) pn=(q, a1a2an ) pn+1=(q, a1a2an+1 ) pm=(q, a1a2am ) 由pigeonhole 原理, p0, p1, p2, , pn 中至少有兩個狀態(tài)是重復的，即存在 i, j, 0ijn, pi=pj . “pumping”

30、 特性： 任一長度不小于狀態(tài)數(shù)目 的字符串所標記的路徑上， 必然出現(xiàn)重復的狀態(tài).36College of Computer Science & Technology, BUPTDFA 的的“Pumping”特性特性 “pumping” 特性：特性：如前如前,設設 DFA D = (Q, T, , q0 , F ), |Q|=n, w = a1a2am (m n), 則存在則存在 i, j, 0 i j n, pi=pj , 其中其中pk= (p0, a1a2ak ) , 0 k m. 若假定若假定p0 = q0 , pm F, 即即w L(D). 令令 w = xyz, 其中：其中： x = a1a2ai , y = ai+1ai+2aj , z