12023/5/21SchoolofComputerScience,BUPT3.7正則表達式與有限自動機的關系結論:有限自動機、右（左）線性文法、正則表達式都定義了同一種語言--正則語言.

證明策略-NFANFADFARERE(RegularExpression)---正則表達式22023/5/21SchoolofComputerScience,BUPT從DFA構造等價的正則表達式（狀態消去法）思路:

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

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

以下分別介紹中間狀態的消去與正則表達式構造過程。32023/5/21SchoolofComputerScience,BUPT從DFA構造等價的正則表達式（中間狀態的消去）xy

r1r2xz

r1y

r2代之以：xy

r1+r2xyr2r1代之以：xy

r1*xzy

r1代之以：42023/5/21SchoolofComputerScience,BUPT從DFA構造等價的正則表達式（中間狀態的消去）q1qkp1pmP1PmQkQ1R11R1mRkmRk1R11+Q1S*P1R1m+Q1S*PmRkm+QkS*PmRk1+QkS*P1q1p1qkpm消去s52023/5/21SchoolofComputerScience,BUPT從DFA構造等價的正則表達式（狀態消去法）步驟:

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

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

a

b

aa

b

b

a

b012567a+ba+baabb0257(a+b)*(a+b)*aa+bb07(a+b)*(aa+bb)(a+b)*82023/5/21SchoolofComputerScience,BUPT定理:

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

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

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

(1)恰好一個終態;

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

從正則表達式構造等價的-NFA92023/5/21SchoolofComputerScience,BUPT基礎:從正則表達式構造等價的-NFA（歸納構造過程）1對于，構造為3對于a

，構造為a2對于

，構造為102023/5/21SchoolofComputerScience,BUPT歸納:從正則表達式構造等價的-NFA（歸納構造過程）1對于R+S，構造為112023/5/21SchoolofComputerScience,BUPT歸納:從正則表達式構造等價的-NFA（歸納構造過程）2對于RS

，構造為3對于R*

，構造為122023/5/21SchoolofComputerScience,BUPT舉例:

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

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

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

δ的定義為：當AaBP，則Bδ（A，a）當AaP,則Hδ（A，a）對于任意輸入，δ（H，a）＝φ。F=162023/5/21SchoolofComputerScience,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}轉換函數：對于產生式SaB，有(S,a)={B}對于產生式BaB，有(B,a)={B}對于產生式BbS，有(B,b)={S}對于產生式Ba，有(B,a)={H}SBH開始aaab172023/5/21SchoolofComputerScience,BUPT右線性文法＝>有限自動機（續）求證

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

證明：

先證（1）文法G產生的語言L(G)能夠被NFAM所接收；再證（2）NFAM接受的語言L(M)可由文法G產生。182023/5/21SchoolofComputerScience,BUPT右線性文法＝>有限自動機（續）證明方法：通過兩者定義的語言中任意一個字符串來說明。（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）。

#192023/5/21SchoolofComputerScience,BUPT右線性文法＝>有限自動機（續）（2）再證L(M)可由G產生設ω=a1a2…an

被NFAM接受，即

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

δ(S，a1)，A2

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

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

a1A1，A1

a2A2，……，An-1

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

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

L（G）。#202023/5/21SchoolofComputerScience,BUPT有限自動機＝>右線性文法定理3.8.2：設有限自動機M接受的語言為L(M)則存在右線性文法G，它產生的語言L(G)＝L(M)。證明思路：構造一個右線性文法G，使它接受由NFAM定義的語言。構造方法： 設M＝（Q，T，δ，q0，F），構造一個右線性文法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）的證明見書P65（自學）。

212023/5/21SchoolofComputerScience,BUPT有限自動機＝>右線性文法（例）例：設有DFAM=({q0,q1,q2,q3},{a,b},,q0,{q3})

其中轉換函數如圖所示，

試構造與之等價的右線性文法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，