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

12023/4/6CollegeofComputerScience&Technology,BUPT正則表達式與有限自動機的關系右線性語言與有限自動機的關系右線性語言的性質(part1)22023/4/6CollegeofComputerScience&Technology,BUPT3.7正則表達式與有限自動機的關系結論:有限自動機、右（左）線性文法、正則表達式都定義了同一種語言--正則語言.

證明策略-NFANFADFARERE(RegularExpression)---正則表達式32023/4/6CollegeofComputerScience&Technology,BUPT從DFA構造等價的正則表達式（狀態(tài)消去法）思路:

(1)擴展自動機的概念，允許正則表達式作為轉移弧的標記。這樣，就有可能在消去某一中間狀態(tài)時，保證自動機能夠接受的字符串集合保持不變。

(2)在消去某一中間狀態(tài)時，與其相關的轉移弧也將同時消去，所造成的影響將通過修改從每一個前趨狀態(tài)到每一個后繼狀態(tài)的轉移弧標記來彌補。

以下分別介紹中間狀態(tài)的消去與正則表達式構造過程。42023/4/6CollegeofComputerScience&Technology,BUPT從DFA構造等價的正則表達式（中間狀態(tài)的消去）xy

r1r2xz

r1y

r2代之以：xy

r1+r2xyr2r1代之以：xy

r1*xzy

r1代之以：52023/4/6CollegeofComputerScience&Technology,BUPT從DFA構造等價的正則表達式（中間狀態(tài)的消去）q1qkp1pmP1PmQkQ1R11R1mRkmRk1R11+Q1S*P1R1m+Q1S*PmRkm+QkS*PmRk1+QkS*P1q1p1qkpm消去s62023/4/6CollegeofComputerScience&Technology,BUPT從DFA構造等價的正則表達式（狀態(tài)消去法）步驟:

(1)對每一終態(tài)q，依次消去除q和初態(tài)q0之外的其它狀態(tài);(2)若qq0，最終可得到一般形式如下左圖的狀態(tài)自動機，

該自動機對應的正則表達式可表示為(R+SU*T)*SU*.(3)若q=q0，最終可得到如下右圖的自動機，它對應的正則表達式可以表示為R*.(4)最終的正則表達式為每一終態(tài)對應的正則表達式之和（并）.72023/4/6CollegeofComputerScience&Technology,BUPT狀態(tài)消去法舉例對于終態(tài)C對于終態(tài)D等價的正則表達式(0+1)*1(0+1)+(0+1)*1(0+1)(0+1)82023/4/6CollegeofComputerScience&Technology,BUPT狀態(tài)消去法舉例01342567

a

b

aa

b

b

a

b012567a+ba+baabb0257(a+b)*(a+b)*aa+bb07(a+b)*(aa+bb)(a+b)*92023/4/6CollegeofComputerScience&Technology,BUPT定理:

L是正則表達式R表示的語言,則存在一個-NFA

E,滿足L(E)=L(R)=L.

證明:構造性證明.可以通過結構歸納法證明從R可以構造出與其等價的，滿足如下條件的-NFA：

(1)恰好一個終態(tài);

(2)沒有弧進入初態(tài)；(3)沒有弧離開終態(tài)；

從正則表達式構造等價的-NFA102023/4/6CollegeofComputerScience&Technology,BUPT基礎:從正則表達式構造等價的-NFA（歸納構造過程）1對于，構造為3對于a

，構造為a2對于

，構造為112023/4/6CollegeofComputerScience&Technology,BUPT歸納:從正則表達式構造等價的-NFA（歸納構造過程）1對于R+S，構造為122023/4/6CollegeofComputerScience&Technology,BUPT歸納:從正則表達式構造等價的-NFA（歸納構造過程）2對于RS

，構造為3對于R*

，構造為132023/4/6CollegeofComputerScience&Technology,BUPT舉例:

設正則表達式1*0(0+1)*,構造等價的-NFA.從正則表達式構造等價的-NFA0+11*142023/4/6CollegeofComputerScience&Technology,BUPT從正則表達式構造等價的-NFA(0+1)*1*0(0+1)*152023/4/6CollegeofComputerScience&Technology,BUPT3.8右線性語言與有限自動機

至此，我們已學到正則集有三種定義方式，且這三種方式等價：正則集是含有{ε}，φ，{a}以及在并、連接和*運算下封閉的語言由正規(guī)表達式定義的集合是正則集。由右線性文法生成的語言是正則集。此外，還有第四種方式： 將正則集作為由有限自動機定義的集合。即正則集(右線性語言)<＝>有限自動機162023/4/6CollegeofComputerScience&Technology,BUPT右線性文法＝>有限自動機定理3.8.1：由任意右線性文法G定義的語言必然能被一個NFAM所接受。即L（G）＝L（M）證明思路（構造證明）： 設右線性文法G＝（N，T，P，S），構造一個與G等價的有限自動機NFA

M＝（Q，T，δ，q0，F(xiàn)），其中：Q＝NU{H}，H為一個新增加的狀態(tài),HN，q0＝S{H，S}當S->ε屬于P。{H}否則

δ的定義為：當AaBP，則Bδ（A，a）當AaP,則Hδ（A，a）對于任意輸入，δ（H，a）＝φ。F=172023/4/6CollegeofComputerScience&Technology,BUPT右線性文法＝>有限自動機（例）例：設有右線性文法G=({S,B},{a,b},P,S)，其中 P：SaBBaB|bS|a

試構造與G等價的有限自動機M。解：設NFAM=(Q,T,,q0,F)Q={S,B,H}T={a,b}q0=SF={H}轉換函數(shù)：對于產生式SaB，有(S,a)={B}對于產生式BaB，有(B,a)={B}對于產生式BbS，有(B,b)={S}對于產生式Ba，有(B,a)={H}SBH開始aaab182023/4/6CollegeofComputerScience&Technology,BUPT右線性文法＝>有限自動機（續(xù)）求證

G與NFAM兩者定義了同一語言。

證明：

先證（1）文法G產生的語言L(G)能夠被NFAM所接收；再證（2）NFAM接受的語言L(M)可由文法G產生。192023/4/6CollegeofComputerScience&Technology,BUPT右線性文法＝>有限自動機（續(xù)）證明方法：通過兩者定義的語言中任意一個字符串來說明。（1）設ω=a1a2…an∈L(G)，且n1則有S＝>a1A1＝>a1a2A2＝>… ＝>a1a2…an-1An-1＝>a1a2…an-1an則由δ的定義，有A1

δ(S，a1)，A2

δ(A1，a2),…,An-1

δ(An-2，an-1)，Hδ(An-1，an)，且Hδ(S，)因為HF,所以被NFAM所接受。又若ε∈L（G）,則表明Sε∈P,由NFAM的定義，有S∈F,即ε也被NFAM接受。所以，由文法G派生的任意字符串

L（M）。

#202023/4/6CollegeofComputerScience&Technology,BUPT右線性文法＝>有限自動機（續(xù)）（2）再證L(M)可由G產生設ω=a1a2…an

被NFAM接受，即

L（M），則必然存在狀態(tài)序列S，A1，A2，…An-1，H對M有轉換函數(shù)為 A1

δ(S，a1)，A2

δ(A1，a2),…, An-1

δ(An-2，an-1)，Hδ(An-1，an)則可規(guī)定G中含有產生式S

a1A1，A1

a2A2，……，An-1

an于是存在推導S＝>a1A1＝>a1a2A2＝>…＝>a1a2…an-1An-1＝>a1a2…an-1an即a1a2…an

是文法G的一個句子。也即

L（G）。#212023/4/6CollegeofComputerScience&Technology,BUPT課堂練習：

練習：設線性文法G＝（{S，A，B}，{a，b}，P，S）P： S

aA|baB|a AaA|aS|bB BbB|b|a 構造相應的NFAM。222023/4/6CollegeofComputerScience&Technology,BUPT有限自動機＝>右線性文法定理3.8.2：設有限自動機M接受的語言為L(M)則存在右線性文法G，它產生的語言L(G)＝L(M)。證明思路：構造一個右線性文法G，使它接受由NFAM定義的語言。構造方法： 設M＝（Q，T，δ，q0，F(xiàn)），構造一個右線性文法G＝（N，T，P，S），其中N＝Q，S＝q0P定義為：若δ（A，a）＝B且BF，則AaB在P中若δ（A，a）＝B且B∈F，則Aa和A

aB在P中（注：書上未明確）

L（M）<＝>L（G）的證明見書P91（自學）。

232023/4/6CollegeofComputerScience&Technology,BUPT有限自動機＝>右線性文法（例）例：設有DFAM=({q0,q1,q2,q3},{a,b},,q0,{q3})

其中轉換函數(shù)如圖所示，

試構造與之等價的右線性文法G。解：構造右線性文法G=(N,T,P,S)N={q0,q1,q2,q3}T={a,b}S=q0產生式集合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(化簡q3)：G=({q0,q1,q2},{a,b},P,q0)P：q0aq0|bq2q1a|bq1q2aq2|b242023/4/6CollegeofComputerScience&Technology,BUPT3.9右線性語言的性質主要內容：DFA的極小化泵浦引理右線性語言的封閉性252023/4/6CollegeofComputerScience&Technology,BUPT確定有限自動機DFA的化簡(極小化) 對DFAM的極小化是找出一個狀態(tài)數(shù)比M少的DFAM1，使?jié)M足L(M)=L(M1)1．等價和可區(qū)分的概念 設DFAM=(Q，T，δ，q0，F(xiàn)) 對不同的狀態(tài)q１，q２∈Q和每個ω∈T*，如果有(q１，ω)┣*(q，ε)必有(q２，ω)┣*(q，ε)且q∈F，則稱q１與q２狀態(tài)等價.記為q１≡q２否則，稱q１，q２可區(qū)分。262023/4/6CollegeofComputerScience&Technology,BUPT確定有限自動機DFA的化簡

2．不可達狀態(tài)

如果不存在任何ω∈T*，使(q０，ω)┣*(q，ε)，

則稱狀態(tài)q∈Q為不可達狀態(tài)。3．最小化

若DFAＭ不存在互為等價狀態(tài)及不可達狀態(tài)，則稱DFAＭ是最小化的。272023/4/6CollegeofComputerScience&Technology,BUPT最小化算法

一個DFAＭ的最小化，是把Ｍ的狀態(tài)集Ｑ構成一個劃分。即:任何兩個子集的狀態(tài)都是可區(qū)分的；同一子集中的任何兩個狀態(tài)都是等價的。之后，每個子集用一個狀態(tài)代表，并取一個狀態(tài)名。構成劃分的步驟:構成基本劃分∏={∏’，∏”}，(∏’為終態(tài)集，∏”為非終態(tài)集)細分∏={∏1，∏2，…，∏n}，∏i∈∏∏i={q１，q２，…，qｍ} 當輸入任意字符a時，若∏i中的狀態(tài)經標a的邊可到達的狀態(tài)集的元素分屬于兩個不同的子集中，則將∏i細分為兩個子集.重復步驟(2)，直至不可再細分，得到Ｍ1.若Ｍ1中有不可達狀態(tài)，將其刪除，Ｍ1便是最小化的.282023/4/6CollegeofComputerScience&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１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２｝｝292023/4/6CollegeofComputerScience&Technology,BUPT計算狀態(tài)集劃分的算法—填表法填表算法（table-fillingalgorithm）基于如下遞歸地標記可區(qū)別的狀態(tài)偶對的過程:基礎如果p為終態(tài)，而q為非終態(tài)，則p和q標記為可區(qū)別的；歸納設p和q已標記為可區(qū)別的,如果狀態(tài)r和s

通過某個輸入符號a可分別轉移到p和q，即

(r,a)=p,(s,a)=q,則r和s也標記為可區(qū)別的；這是因為：若p和q可為字符串w

區(qū)別,則r和s可為字符串aw

區(qū)別.（∵'(r,aw)='(p,w),'(s,aw)='(q,w)）302023/4/6CollegeofComputerScience&Technology,BUPT計算狀態(tài)集劃分的算法—填表法填表算法舉例xxxxxxxxxxxxx(1)區(qū)別所有終態(tài)和非終態(tài)(2)區(qū)別(1,3),(1,4),(2,3),(2,4),(5,6),(5,7)xxxxx(3)區(qū)別(3,4)x(4)結束.劃分結果：{1,2},{3},{4},{5},{6,7}312023/4/6CollegeofComputerScience&Technology,BUPT通過合并等價的狀態(tài)進行DFA

的優(yōu)化步驟

1.刪除所有從開始狀態(tài)不可到達的狀態(tài)及與其相關的邊,

設所得到的DFA

為A=(Q,

T,,q0,F)；2.使用填表算法找出所有等價的狀態(tài)偶對；3.根據(jù)2的結果計算當前狀態(tài)集合的劃分塊，每一劃分塊中的狀態(tài)相互之間等價，而不同劃分塊中的狀態(tài)之間都是可區(qū)別的.包含狀態(tài)q的劃分塊用[q]表示.

4.構造與A等價的DFA

B=(QB,

T,B,[q0],FB

),其中

QB={[q]|qQ},FB={[q]|qF},B([q],a)=[

(q,a)]322023/4/6CollegeofComputerScience&Technology,BUPT通過合并等價的狀態(tài)進行DFA

的優(yōu)化舉例劃分結果：{1,2},{3},{4},

{5},{6,7}等價的狀態(tài)偶對為：

（1,2）,（6,7）新的狀態(tài)集合：

[1],[3],[4],[5],[6]332023/4/6CollegeofComputerScience&Technology,BUPT最小化的DFA課堂練習最小化下列DFA:參考結果342023/4/6CollegeofComputerScience&Technology,BUPT針對正則語言的Pumping引理正則語言應滿足的一個必要條件用于判定給定的語言不是正則集。物理意義：當給定一個正則集和該集合上一個足夠長的字符串時，在該字符串中能找到一個非空的子串，并使子串重復，從而組成新的字符串。該新串必在同一個正則集內。定理：設L是正則集，存在常數(shù)k，對字符串ω∈Ｌ且｜ω｜≥ｋ，則ω可寫成ω1ω0ω２，其中｜ω1ω0｜≤ｋ，｜ω0｜＞０，對所有的ｉ≥0有ω1ω0iω2∈Ｌ。證明

設L是DFAD=(Q,

T,,q0,F)的語言，取k=|Q|

即可.352023/4/6CollegeofComputerScience&Technology,BUPTDFA

的“Pumping”特性設DFAD=(Q,

T,,q0,F),|Q|=n.對于任一長度不小于n的字符串w=a1a2…am,其中mn,akT(1km),qQ,考察如下狀態(tài)序列

p0=qp1='(q,a1)p2='(q,a1a2)…pn='(q,a1a2…an)pn+1='(q,a1a2…an+1)…pm='(q,a1a2…am)由pigeonhole原理,p0,p1,p2,…,pn中至少有兩個狀態(tài)是重復的，即存在i,j,0ijn,pi=pj.

“pumping”特性：任一長度不小于狀態(tài)數(shù)目

的字符串所標記的路徑上，

必然出現(xiàn)重復的狀態(tài).362023/4/6CollegeofComputerScience&Technology,BUPTDFA

的“Pumping”特性

“pumping”特性：如前,設DFAD=(Q,

T,,q0,F),|Q|=n,w=a1a2…am(mn),則存在i,j,0ijn,pi=pj

,

其中pk='(p0,a1a2…ak),0km.若假定p0=

q0,pmF,即wL(D).

令w=xyz,其中：

x=a1a2…ai

,y=ai+1ai+2…aj

,z=aj+1aj+2…am

則對任何k0，都有xyk