形式語言與自動機ch3.7-3.9a

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

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

3、紹中間狀態(tài)的消去與正則表達式構(gòu)造過程。42022-3-19College of Computer Science & Technology, BUPT從從 DFA 構(gòu)造等價的構(gòu)造等價的正則表達式正則表達式（中間狀態(tài)的消去）（中間狀態(tài)的消去）xy r1r2xz r1y r2代之以：xy r1+r2xyr2r1代之以：xy r1*xz y r1代之以：52022-3-19College of Computer Science & Technology, BUPT從從 DFA 構(gòu)造等價的構(gòu)造等價的正則表達式正則表達式（中間狀態(tài)的消去）（中間狀態(tài)的消去）sSq1qkp1pmP1PmQk

4、Q1R11R1mRkmRk1R11+ Q1S* P1R1m+ Q1S* PmRkm+ QkS* PmRk1 + QkS* P1q1p1qkpm消去消去 s62022-3-19College of Computer Science & Technology, BUPT從從 DFA 構(gòu)造等價的構(gòu)造等價的正則表達式正則表達式（狀態(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)自動機

5、，的狀態(tài)自動機， 該自動機對應(yīng)的正則表達式可表示為該自動機對應(yīng)的正則表達式可表示為 ( R+SU*T )*SU*.(3) 若若q= q0，最終可得到最終可得到如下右圖的自動機，它對應(yīng)的正則如下右圖的自動機，它對應(yīng)的正則 表達式可以表示為表達式可以表示為 R*.(4) 最終最終的正則表達式為的正則表達式為每一終態(tài)對應(yīng)的每一終態(tài)對應(yīng)的 正則表達式之和（并）正則表達式之和（并）.72022-3-19College of Computer Science & Technology, BUPT狀態(tài)消去法舉例狀態(tài)消去法舉例A0+1StartBCD10+10+1對于終態(tài)對于終態(tài)CA0+1StartC

6、1(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)82022-3-19College 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)*92022-3-19College of Computer Science & Technology, BUPT

7、定理定理: L 是正則表達式是正則表達式 R 表示的語言表示的語言, 則存在一個則存在一個 - NFA E ,滿足滿足 L(E) = L(R) = L. 證明證明: 構(gòu)造性證明構(gòu)造性證明. 可以通過結(jié)構(gòu)歸納法證明從可以通過結(jié)構(gòu)歸納法證明從 R 可以構(gòu)可以構(gòu)造出與其等價的，滿足如下條件的造出與其等價的，滿足如下條件的 - NFA ： (1) 恰好一個終態(tài)恰好一個終態(tài); (2) 沒有弧進入初態(tài)；沒有弧進入初態(tài)； (3) 沒有弧離開終態(tài)；沒有弧離開終態(tài)； 從從正則表達式正則表達式構(gòu)造等價的構(gòu)造等價的 - NFA102022-3-19College of Computer Science &

8、Technology, BUPT基礎(chǔ)基礎(chǔ): :從從正則表達式正則表達式構(gòu)造等價的構(gòu)造等價的 - NFA（歸納歸納構(gòu)造過程）構(gòu)造過程）1 對于對于 ，構(gòu)造為構(gòu)造為 3 對于對于 a ，構(gòu)造為構(gòu)造為a2 對于對于 ，構(gòu)造為構(gòu)造為112022-3-19College of Computer Science & Technology, BUPT歸納歸納: :從從正則表達式正則表達式構(gòu)造等價的構(gòu)造等價的 - NFA（歸納歸納構(gòu)造過程）構(gòu)造過程）1 對于對于 R+S ，構(gòu)造為構(gòu)造為SR 122022-3-19College of Computer Science & Technology,

9、 BUPT歸納歸納: :從從正則表達式正則表達式構(gòu)造等價的構(gòu)造等價的 - NFA（歸納歸納構(gòu)造過程）構(gòu)造過程）2 對于對于 RS ，構(gòu)造為構(gòu)造為RS R3 對于對于 R* ，構(gòu)造為構(gòu)造為 132022-3-19College of Computer Science & Technology, BUPT舉例舉例: : 設(shè)設(shè)正則表達式正則表達式 1*0(0+1)*, 構(gòu)造等價的構(gòu)造等價的 - NFA.從從正則表達式正則表達式構(gòu)造等價的構(gòu)造等價的 - NFA100+1 11* 142022-3-19College of Computer Science & Technology, B

10、UPT從從正則表達式正則表達式構(gòu)造等價的構(gòu)造等價的 - NFA(0+1)*10 11001*0(0+1)* 152022-3-19College of Computer Science & Technology, BUPT3.8 右線性語言與右線性語言與有限自動機有限自動機 至此，我們已學(xué)到正則集有三種定義方式，且這三種方式等價： 正則集是含有，a 以及在并、連接和 * 運算下封閉的語言 由正規(guī)表達式定義的集合是正則集。 由右線性文法生成的語言是正則集。此外，還有第四種方式： 將正則集作為由有限自動機定義的集合。即 正則集(右線性語言) 有限自動機162022-3-19College

11、of Computer Science & Technology, BUPT右線性文法右線性文法 有限自動機有限自動機定理定理3.8.1：由任意右線性文法G定義的語言必然能被一個NFA M所接受。即L（G）L（M）證明思路（構(gòu)造證明）證明思路（構(gòu)造證明）：設(shè)右線性文法G（N，T，P，S），構(gòu)造一個與G等價的有限自動機NFA M（Q，T，q0，F(xiàn)），其中： QN U H，H為一個新增加的狀態(tài), HN， q0S H，S 當(dāng)S-屬于P。 H 否則 的定義為：的定義為：當(dāng)當(dāng)A a B P，則則 B （A，a）當(dāng)當(dāng)A a P, 則則 H （A，a）對于任意輸入，（H，a）。F=172022-3-

12、19College of Computer Science & Technology, BUPT右線性文法右線性文法 有限自動機有限自動機（例）例：例：設(shè)有右線性文法設(shè)有右線性文法G=(S,B ,a,b, P,S)，其中其中P： SaB BaB|bS|a 試構(gòu)造與試構(gòu)造與G等價的有限自動機等價的有限自動機M。解：解： 設(shè)設(shè)NFA M=(Q,T, , q0, F)Q=S,B,H T=a,b q0 = S F =H轉(zhuǎn)換函數(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)生式對

13、于產(chǎn)生式Ba， 有有(B,a)=HSBH開始aaab182022-3-19College of Computer Science & Technology, BUPT右線性文法右線性文法 有限自動機有限自動機（續(xù)）（續(xù)）求證求證 G與與NFA M兩者定義了同一語言。兩者定義了同一語言。 證明：證明： 先證（先證（1）文法）文法G產(chǎn)生的語言產(chǎn)生的語言 L(G) 能夠被能夠被NFA M所接收；所接收；再證（再證（2）NFA M 接受的語言接受的語言 L(M) 可由文法可由文法G 產(chǎn)生。產(chǎn)生。192022-3-19College of Computer Science & Techn

14、ology, BUPT右線性文法右線性文法 有限自動機有限自動機（續(xù)）（續(xù)）證明方法：證明方法：通過兩者定義的語言中任意一個字符串來說明。（1）設(shè) = 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 ,由 NFA M 的定義，有S F, 即也被NFA M接受。所以，由文法所以，由文法G派生的任意字符串派生的任意字符串 L（M

15、）。 #202022-3-19College of Computer Science & Technology, BUPT右線性文法右線性文法 有限自動機有限自動機（續(xù)）（續(xù)）（2）再證再證 L(M)可由可由G產(chǎn)生產(chǎn)生設(shè) = 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 ， ，An-1 a n于是存在推導(dǎo)S a1A1 a1a2A2 a1a2an-1An-1 a1a

16、2 an-1a n即a1a2an 是文法G的一個句子。也即也即 L（G）。）。 #212022-3-19College of Computer Science & Technology, BUPT課堂練習(xí)：課堂練習(xí)： 練習(xí)：練習(xí)： 設(shè)線性文法設(shè)線性文法 G （S，A，B，a，b，P，S） P： S aA | baB | aA aA | aS | bBB bB | b | a構(gòu)造相應(yīng)的構(gòu)造相應(yīng)的 NFA M。222022-3-19College of Computer Science & Technology, BUPT有限自動機有限自動機 右線性文法右線性文法定理定理3.8.2

17、：設(shè)有限自動機設(shè)有限自動機 M 接受的語言為接受的語言為L(M)則存在右線性文法則存在右線性文法G，它產(chǎn)生的語言它產(chǎn)生的語言L(G)L(M)。證明思路：證明思路：構(gòu)造一個右線性文法構(gòu)造一個右線性文法G，使它接受由使它接受由NFA M定義的語言。定義的語言。構(gòu)造方法：構(gòu)造方法：設(shè)設(shè) M（Q，T，q0，F(xiàn)），），構(gòu)造一個右線性文法構(gòu)造一個右線性文法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中中 （注：書上未明確）（注：書上未明確） L（M） L（G）

18、的證明見書的證明見書 P91 （自學(xué)）。自學(xué)）。 232022-3-19College of Computer Science & Technology, BUPT有限自動機有限自動機右線性文法右線性文法（例）例：例：設(shè)有設(shè)有DFA M =(q0,q1,q2,q3, a,b, , q0, q3 ) 其中轉(zhuǎn)換函數(shù)如圖所示，其中轉(zhuǎn)換函數(shù)如圖所示， 試構(gòu)造與之等價的右線性文法試構(gòu)造與之等價的右線性文法G。解：解：構(gòu)造右線性文法構(gòu)造右線性文法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 T =a,b

19、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òu)造的文法構(gòu)造的文法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|b242022-3-19College of Computer Science & Tech

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

21、稱q， q可區(qū)分。262022-3-19College of Computer Science & Technology, BUPT確定有限自動機確定有限自動機DFA的化簡的化簡2不可達狀態(tài) 如果不存在任何T*，使(q，)* (q，)， 則稱狀態(tài)qQ為不可達狀態(tài)。3 最小化 若DFA 不存在互為等價狀態(tài)及不可達狀態(tài)，則稱DFA 是最小化的。272022-3-19College of Computer Science & Technology, BUPT最小化算法最小化算法 一個DFA 的最小化，是把的狀態(tài)集構(gòu)成一個劃分。即: 任何兩個子集的狀態(tài)都是可區(qū)分的；同一子集中的任何兩個

22、狀態(tài)都是等價的。之后，每個子集用一個狀態(tài)代表，并取一個狀態(tài)名。構(gòu)成劃分的步驟構(gòu)成劃分的步驟: 構(gòu)成基本劃分 =，”， (為終態(tài)集，”為非終態(tài)集) 細分 =1， 2， n， i i = q， q， q當(dāng)輸入任意字符a時，若i中的狀態(tài)經(jīng)標(biāo)a的邊可到達的狀態(tài)集的元素分屬于兩個不同的子集中，則將i 細分為兩個子集.重復(fù)步驟(2)，直至不可再細分，得到1.若1中有不可達狀態(tài)，將其刪除，1便是最小化的. 282022-3-19College of Computer Science & Technology, BUPT例例(1) q，q為不可達狀態(tài)，刪除之.(2) Q = q，q，q，q，q, =

23、q，q ，q，q，q 構(gòu)成基本劃分 =，”(a) 對于= q， q，對字符a，有(q，a)= q，(q，a)= q 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 292022-3-19College of Computer Sc

24、ience & Technology, BUPT計算狀態(tài)集劃分的算法計算狀態(tài)集劃分的算法 填表法填表法 填表算法（填表算法（table-filling algorithm）基于如下遞歸地基于如下遞歸地 標(biāo)記可區(qū)別的狀態(tài)偶對的過程標(biāo)記可區(qū)別的狀態(tài)偶對的過程:- 基礎(chǔ)基礎(chǔ) 如果如果 p 為終態(tài)，而為終態(tài)，而 q 為非終態(tài)，則為非終態(tài)，則 p 和和 q 標(biāo)記標(biāo)記 為可區(qū)別的；為可區(qū)別的；- 歸納歸納 設(shè)設(shè) p 和和 q 已標(biāo)記為可區(qū)別的已標(biāo)記為可區(qū)別的, 如果狀態(tài)如果狀態(tài) r 和和 s 通過某個通過某個 輸入符號輸入符號 a 可分別轉(zhuǎn)移到可分別轉(zhuǎn)移到 p 和和 q ，即即 (r,a)=p ,

25、 (s,a)=q , 則則 r 和和 s 也標(biāo)記為可區(qū)別的；也標(biāo)記為可區(qū)別的； 這是因為：這是因為：若若 p 和和 q 可為字符串可為字符串 w 區(qū)別區(qū)別, 則則 r 和和 s 可可 為字符串為字符串 aw 區(qū)別區(qū)別. （ (r,aw) = (p,w) , (s,aw) = (q,w) ）302022-3-19College of Computer Science & Technology, BUPT計算狀態(tài)集劃分的算法計算狀態(tài)集劃分的算法 填表法填表法 填表算法舉例填表算法舉例212334455667xxxxxxxxxxxxx651Start3724aaaaaaabbbbbbb(1)

26、 區(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ū)別 (3,4)x(4) 結(jié)束結(jié)束. 劃分結(jié)果：劃分結(jié)果：1,2, 3, 4, 5, 6,7312022-3-19College of Computer Science & Technology, BUPT通過合并等價的狀態(tài)進行通過合并等價的狀態(tài)進行 DFA 的優(yōu)化的優(yōu)化 步驟步驟 1. 刪除所有從開始狀態(tài)不可到達的狀態(tài)及與其相關(guān)的邊刪除所有從開始狀態(tài)不可到達的狀態(tài)及與其相關(guān)的邊, 設(shè)所得到的設(shè)所得到的 DFA 為為 A = (

27、Q, T, , q0 , F ) ； 2. 使用填表算法找出所有等價的狀態(tài)偶對；使用填表算法找出所有等價的狀態(tài)偶對； 3. 根據(jù)根據(jù) 2 的結(jié)果計算當(dāng)前狀態(tài)集合的劃分塊，每一劃分的結(jié)果計算當(dāng)前狀態(tài)集合的劃分塊，每一劃分 塊中的狀態(tài)相互之間等價，而不同劃分塊中的狀態(tài)之塊中的狀態(tài)相互之間等價，而不同劃分塊中的狀態(tài)之 間都是可區(qū)別的間都是可區(qū)別的. 包含狀態(tài)包含狀態(tài) q 的劃分塊用的劃分塊用 q 表示表示. 4. 構(gòu)造與構(gòu)造與 A 等價的等價的 DFA B = (QB, T, B, q0, FB ) , 其中其中 QB= q | q Q, FB = q | q F, B(q ,a)= (q,a)32

28、2022-3-19College of Computer Science & Technology, BUPT通過合并等價的狀態(tài)進行通過合并等價的狀態(tài)進行 DFA 的優(yōu)化的優(yōu)化 舉例舉例 651Start3724aaaaaaabbbbbbb 劃分結(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, 6651Start34aaaabbbbba332022-3-19College of Computer Science & Technology, BUPT最

29、小化的最小化的 DFA 課堂練習(xí)課堂練習(xí) 最小化下列最小化下列 DFA:651Start3724aaaaaaabbbbbbb 參考結(jié)果參考結(jié)果61Start34aaaabbbb342022-3-19College of Computer Science & Technology, BUPT針對正則語言的針對正則語言的 Pumping 引理引理 正則語言應(yīng)滿足的一個必要條件 用于判定給定的語言不是正則集。物理意義：物理意義：當(dāng)給定一個正則集和該集合上一個足夠長的字符串時，在該字符串中能找到一個非空的子串，并使子串重復(fù)，從而組成新的字符串。該新串必在同一個正則集內(nèi)。定理：定理：設(shè)L是正則集

30、，存在常數(shù)k，對字符串 且，則可寫成10，其中10， 0，對所有的0有10i2。證明證明 設(shè)設(shè) L 是是 DFA D = (Q, T, , q0 , F ) 的語言，的語言， 取取 k = |Q| 即可即可. 352022-3-19College of Computer Science & Technology, BUPTDFA 的的“Pumping”特性特性 設(shè) DFA D = (Q, T, , q0 , F ), |Q|=n. 對于任一長度不小于 n 的字符串 w = a1a2am , 其中 mn, akT (1 k m), qQ , 考察如下狀態(tài)序列 p0=q p1=(q, a1

31、) p2=(q, a1a2) pn=(q, a1a2an ) pn+1=(q, a1a2an+1 ) pm=(q, a1a2am ) 由pigeonhole 原理, p0, p1, p2, , pn 中至少有兩個狀態(tài)是重復(fù)的，即存在 i, j, 0ijn, pi=pj . “pumping” 特性： 任一長度不小于狀態(tài)數(shù)目 的字符串所標(biāo)記的路徑上， 必然出現(xiàn)重復(fù)的狀態(tài).362022-3-19College of Computer Science & Technology, BUPTDFA 的的“Pumping”特性特性 “pumping” 特性：特性：如前如前,設(shè)設(shè) DFA D = (

32、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 = aj+1aj+2am 則對任何則對任何k 0，都有都有 xykz L(D). (參考下圖參考下圖)Startp0pipmx = a1a2aiy = ai+1ai+2ajz=aj+1aj+2am372022-3-19College