12025/10/20SchoolofComputerScience,BUPT3.7正則表達式與有限自動機的關(guān)系結(jié)論:有限自動機、右（左）線性文法、正則表達式都定義了同一種語言--正則語言.

證明策略

-NFANFADFARERE(RegularExpression)---正則表達式22025/10/20SchoolofComputerScience,BUPT從DFA構(gòu)造等價的正則表達式（狀態(tài)消去法）思路:

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

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

以下分別介紹中間狀態(tài)的消去與正則表達式構(gòu)造過程。32025/10/20SchoolofComputerScience,BUPT從DFA構(gòu)造等價的正則表達式（中間狀態(tài)的消去）xy

r1r2xz

r1y

r2代之以：xy

r1+r2xyr2r1代之以：xy

r1*xz

y

r1代之以：42025/10/20SchoolofComputerScience,BUPT從DFA構(gòu)造等價的正則表達式（中間狀態(tài)的消去）

q1qkp1pmP1PmQkQ1R11R1mRkmRk1

R11+Q1S*P1R1m+Q1S*PmRkm+QkS*PmRk1+QkS*P1q1p1qkpm消去s52025/10/20SchoolofComputerScience,BUPT從DFA構(gòu)造等價的正則表達式（狀態(tài)消去法）步驟:

(1)對每一終態(tài)q，依次消去除q和初態(tài)q0之外的其它狀態(tài);(2)若q

q0，最終可得到一般形式如下左圖的狀態(tài)自動機，

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

a

b

aa

b

b

a

b

012567a+ba+b

aabb0257(a+b)*(a+b)*aa+bb07(a+b)*(aa+bb)(a+b)*82025/10/20SchoolofComputerScience,BUPT定理:

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

-NFA

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

證明:構(gòu)造性證明.可以通過結(jié)構(gòu)歸納法證明從R可以構(gòu)造出與其等價的，滿足如下條件的

-NFA：

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

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

從正則表達式構(gòu)造等價的

-NFA92025/10/20SchoolofComputerScience,BUPT基礎(chǔ):從正則表達式構(gòu)造等價的

-NFA（歸納構(gòu)造過程）1對于

，構(gòu)造為

3對于a

，構(gòu)造為a2對于

，構(gòu)造為102025/10/20SchoolofComputerScience,BUPT歸納:從正則表達式構(gòu)造等價的

-NFA（歸納構(gòu)造過程）1對于R+S，構(gòu)造為

112025/10/20SchoolofComputerScience,BUPT歸納:從正則表達式構(gòu)造等價的

-NFA（歸納構(gòu)造過程）2對于RS

，構(gòu)造為

3對于R*

，構(gòu)造為

122025/10/20SchoolofComputerScience,BUPT舉例:

設(shè)正則表達式1*0(0+1)*,構(gòu)造等價的

-NFA.從正則表達式構(gòu)造等價的

-NFA0+1

1*

132025/10/20SchoolofComputerScience,BUPT從正則表達式構(gòu)造等價的

-NFA(0+1)*

1*0(0+1)*

142025/10/20SchoolofComputerScience,BUPT3.8右線性語言與有限自動機

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

M＝（Q，T，δ，q0，F(xiàn)），其中：Q＝NU{H}，H為一個新增加的狀態(tài),H

N，q0＝S{H，S}當(dāng)S->ε屬于P。{H}否則

δ的定義為：當(dāng)A

aB

P，則B

δ（A，a）當(dāng)A

a

P,則H

δ（A，a）對于任意輸入，δ（H，a）＝φ。F=162025/10/20SchoolofComputerScience,BUPT右線性文法＝>有限自動機（例）例：設(shè)有右線性文法G=({S,B},{a,b},P,S)，其中 P：S

aBB

aB|bS|a

試構(gòu)造與G等價的有限自動機M。解：設(shè)NFAM=(Q,T,,q0,F)Q={S,B,H}T={a,b}q0=SF={H}轉(zhuǎn)換函數(shù)：對于產(chǎn)生式S

aB，有

(S,a)={B}對于產(chǎn)生式B

aB，有

(B,a)={B}對于產(chǎn)生式B

bS，有

(B,b)={S}對于產(chǎn)生式B

a，有

(B,a)={H}SBH開始aaab172025/10/20SchoolofComputerScience,BUPT右線性文法＝>有限自動機（續(xù)）求證

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

證明：

先證（1）文法G產(chǎn)生的語言L(G)能夠被NFAM所接收；再證（2）NFAM接受的語言L(M)可由文法G產(chǎn)生。182025/10/20SchoolofComputerScience,BUPT右線性文法＝>有限自動機（續(xù)）證明方法：通過兩者定義的語言中任意一個字符串來說明。（1）設(shè)ω=a1a2…an∈L(G)，且n

1則有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）。

#192025/10/20SchoolofComputerScience,BUPT右線性文法＝>有限自動機（續(xù)）（2）再證L(M)可由G產(chǎn)生設(shè)ω=a1a2…an

被NFAM接受，即

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

an于是存在推導(dǎo)S＝>a1A1＝>a1a2A2＝>…＝>a1a2…an-1An-1＝>a1a2…an-1an即a1a2…an

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

L（G）。#202025/10/20SchoolofComputerScience,BUPT有限自動機＝>右線性文法定理3.8.2：設(shè)有限自動機M接受的語言為L(M)則存在右線性文法G，它產(chǎn)生的語言L(G)＝L(M)。證明思路：構(gòu)造一個右線性文法G，使它接受由NFAM定義的語言。構(gòu)造方法： 設(shè)M＝（Q，T，δ，q0，F(xiàn)），構(gòu)造一個右線性文法G＝（N，T，P，S），其中N＝Q，S＝q0P定義為：若δ（A，a）＝B且B

F，則A

aB在P中若δ（A，a）＝B且B∈F，則A

a和A

aB在P中

L（M）<＝>L（G）的證明見書P65（自學(xué)）。

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

,q0,{q3})

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

試構(gòu)造與之等價的右線性文法G。解：構(gòu)造右線性文法G=(N,T,P,S)N={q0,q1,q2,q3}T={a,b}S=q0產(chǎn)生式集合P

(q0,a)=q1，

q0

aq1

(q0,b)=q2，

q0

bq2

(q1