形式語言與自動機6ch39b-310

1CollegeofComputerScience&Technology,BUPT第五講3.9(part2)右線性語言的封閉性3.10雙向和有輸出的有限自動機

2CollegeofComputerScience&Technology,BUPT右線性語言的封閉性

上節(jié)從文法產(chǎn)生的角度證明了右線性語言及其并，積，閉包是正則集；本節(jié)用有限自動機接受的語言來證明。(書P103~)設(shè)Ｌ１和Ｌ２是右線性語言，證明Ｌ１∪Ｌ２為右線性語言

構(gòu)造NFAM＝(Q

，T，δ，q0，F(xiàn))Q＝Q1∪Q２∪｛q0｝q0是新的起始狀態(tài)Ｆ１∪Ｆ２當(dāng)εＬ１，εＬ２Ｆ１∪Ｆ２∪｛q０｝

否則

F=M形如:3CollegeofComputerScience&Technology,BUPT右線性語言的封閉性設(shè)Ｌ１和Ｌ２是右線性語言，證明Ｌ１Ｌ２為右線性語言(書P104~)

構(gòu)造NFAM＝(Q

，T，δ，q0，F(xiàn)),其中Q=Q１∪Q２q0=q1 Ｆ２

當(dāng)q2F2

Ｆ１∪Ｆ２

當(dāng)q2∈F2

F=M形如:4CollegeofComputerScience&Technology,BUPT右線性語言的封閉性設(shè)Ｌ１是右線性語言，證明L１*是右線性語言(書P106~)

構(gòu)造NFAM＝(Q

，T，δ，q0，F(xiàn)),Q=Q1∪｛q０｝ q０是新的起始狀態(tài), F=Ｆ1∪｛q０｝L１*

形如

5CollegeofComputerScience&Technology,BUPT右線性語言的封閉性設(shè)Ｌ１是右線性語言，證明L１是右線性語言證明：構(gòu)造接受Ｌ1的M＝(Q

，T，δ，q0，F(xiàn))

其中Q=Q1∪｛γ｝γ是一個新狀態(tài)

TT1q0=q1

Ｆ＝(Q1－Ｆ1)∪｛γ｝(即將Ｍ1的終止?fàn)顟B(tài)變?yōu)镸的非終止?fàn)顟B(tài))δ定義為:當(dāng)a∈T1，則δ(q，a)=δ1(q，a) —保留原有函數(shù) 當(dāng)a∈T－T1，則δ(q，a)=γ —遇到原來沒有的字符全轉(zhuǎn)至γ. 對任意a∈T，δ(γ，a)＝γ

6CollegeofComputerScience&Technology,BUPT右線性語言的封閉性例:(書P108)

對下圖的Ｍ1,求Ｌ(Ｍ1)

7CollegeofComputerScience&Technology,BUPT右線性語言的封閉性例:設(shè)DFAＭ1＝（｛q０,q４｝,｛ａ,ｂ｝,δ１，q０,｛q３,q４｝）

對Ｔ＝｛ａ，ｂ，ｃ｝,求Ｌ(Ｍ1)8CollegeofComputerScience&Technology,BUPT右線性語言的封閉性證明Ｌ1∩Ｌ２是封閉的證明：∵Ｌ1∩Ｌ２＝Ｌ1∪Ｌ２∴得證6.證明右線性語言對于置換是封閉的.(略--自學(xué))9CollegeofComputerScience&Technology,BUPT補充：構(gòu)造自動機的“交”通過構(gòu)造證明，說明正則語言在交運算下封閉。設(shè)兩個DFAM1＝(Q1，T，δ1，q1，F(xiàn)1) M2＝(Q2，T，δ2，q2，F(xiàn)2)構(gòu)造新的DFAM,M＝(Q1xQ2，T，δ，[q1，q2]，F(xiàn)1xF2)對一切p1∈Q1,p2∈Q2，a∈T，δ（[p1，p2],a）=[δ1（p1,a）,δ2（p2,a）]則L（M）=L（M1）∩L（M2）10CollegeofComputerScience&Technology,BUPT有關(guān)正則語言的幾個判定性質(zhì)

判定正則語言是否為空

判定正則語言中是否包含特定的字符串

判定兩個正則語言是否相等11CollegeofComputerScience&Technology,BUPT

判定正則語言是否為空可由如下步驟遞歸地計算可達(dá)狀態(tài)集合：判定算法測試從初態(tài)是否可達(dá)某一終態(tài).先求所有可達(dá)狀態(tài)的集合，若其中包含終態(tài)，則該正規(guī)語言非空，否則為空語言。算法復(fù)雜度設(shè)有限自動機的狀態(tài)數(shù)目為n，上述判定算法的復(fù)雜度為

O(n2).

基礎(chǔ)：初態(tài)是可達(dá)的：

歸納：設(shè)狀態(tài)q是可達(dá)的，若對于某個輸入符號或，q可轉(zhuǎn)移到p，則p也是可達(dá)的：12CollegeofComputerScience&Technology,BUPT

判定正則語言中是否包含特定的字符串判定算法從初態(tài)開始，處理輸入字符串w

，如果可以結(jié)束于某一終態(tài)，則該正規(guī)語言中包含w，否則不包含w。算法復(fù)雜度設(shè)輸入字符串w的長度|w|=n，上述判定算法的復(fù)雜度為

O(n).

以DFA表示正則語言

以正則表達(dá)式表示正則語言將其轉(zhuǎn)化為等價的NFA，然后執(zhí)行上述過程.

以NFA（或NFA）表示正則語言可以將其轉(zhuǎn)化為等價的DFA，然后執(zhí)行上述過程；也可以直接模擬其處理字符串的過程，判定算法的復(fù)雜度為

O(n2s),其中n為字符串的長度，s為NFA（或NFA）的狀態(tài)數(shù)目.13CollegeofComputerScience&Technology,BUPT

判定兩個正則語言是否相等判定算法可由采取如下步驟：算法復(fù)雜度以上算法的復(fù)雜度即填表算法的復(fù)雜度，其上限為O(n4)；可以適當(dāng)設(shè)計填表算法的數(shù)據(jù)結(jié)構(gòu)，使其復(fù)雜度降為

O(n2).1.先將兩個正則語言的表達(dá)形式都轉(zhuǎn)化為DFA，問題轉(zhuǎn)化為兩個DFA是否是等價的；2.適當(dāng)重命名，使兩個DFA沒有重名的狀態(tài)；3.將兩個DFA相并，構(gòu)造一個新的DFA，原來的終態(tài)仍是終態(tài)，轉(zhuǎn)移邊不發(fā)生任何變化，取任何一個狀態(tài)為初態(tài)；4.對新構(gòu)造的DFA運用填表算法，如果原來DFA的兩個初態(tài)不可區(qū)別，則這兩個正則語言相等，否則不相等.14CollegeofComputerScience&Technology,BUPT雙向有限自動機(2DFA)定義: 讀入一個字符之后，讀頭既可以左移一格，也可以右移一格，或者不移動的有限自動機，為雙向有限自動機.確定的雙向有限自動機:每讀入一字符，必須向左或右移動，不考慮不移動的情況.15CollegeofComputerScience&Technology,BUPT2DFA的形式定義2DFAM＝(Q

，T，δ，q0，F(xiàn)) δ是從Q×T→Q×{L，R}的映射. 即δ(q，a)=(p，R)或δ(q，a)=(p，L)（在狀態(tài)q，讀入a，進(jìn)入狀態(tài)p，讀頭向右(向左)移一格）用格局描述:

設(shè)有ω1qω2

ω1---已輸入串 q---當(dāng)前狀態(tài)ω2---

待輸入串δ(q，am+1)=(p，R)的格局表示: a1a2…amqam+1…an┣a1a2…am+1pam+2…anδ(q，am+1)=(p，L)的格局表示: a1a2…amqam+1…an┣a1a2…am-1pamam+1…an

16CollegeofComputerScience&Technology,BUPT2DFA2DFA接受的字符串集合是:

L(M)={ω|q０ω┣*ωq，qF}例:書P113例1. 其狀態(tài)圖為b,R17CollegeofComputerScience&Technology,BUPT有輸出的有限自動機 有輸出的有限自動機是有限自動機的一個類型.這類自動機在有字符輸入時，不僅存在狀態(tài)轉(zhuǎn)換，同時引起字符輸出. 根據(jù)輸入字符，自動機狀態(tài)，輸出字符三者之間關(guān)系，可有兩類有輸出的自動機:米蘭機(Mealy):輸出字符與輸入字符及狀態(tài)有關(guān).摩爾機(Moore):輸出字符僅與狀態(tài)有關(guān).最大優(yōu)點:節(jié)省狀態(tài)!

18CollegeofComputerScience&Technology,BUPT米蘭機

米蘭機形式定義:M＝(Q

，T，R，δ，g，q0)其中Q有限狀態(tài)集合

T有限輸入字母表

R有限輸出字母表

δ:Q×T→Q轉(zhuǎn)換函數(shù)

g:Q×T→R輸出函數(shù)

q0:初始狀態(tài)q0Qδ和g函數(shù)共同描述了米蘭機的工作狀況.

19CollegeofComputerScience&Technology,BUPT米蘭機米蘭機圖形表示:

δ(p，a)=q

g(p，a)=b

Pqa/b例:(P115例2)設(shè)計米蘭機，其輸出是輸入字符個數(shù)的模3數(shù)解:輸出字母表R={0，1，2}.設(shè)輸入字母表T={a},M的狀態(tài)數(shù)應(yīng)有3個，記錄已輸入字符個數(shù)的模3數(shù).Q={q0，q1，q2}分別表示輸入字符數(shù)模3=0,1,220CollegeofComputerScience&Technology,BUPT米蘭機例:（P115例3）

設(shè)計米蘭機，其輸入{0，1}*，當(dāng)輸入串有奇數(shù)個1時，輸出1.當(dāng)輸入串有偶數(shù)個1時，輸出0.

解:需二個狀態(tài){q0，q1

}

q0表示輸入串有偶數(shù)個1，

q1表示輸入串有奇數(shù)個121CollegeofComputerScience&Technology,BUPT課堂練習(xí)設(shè)語言L由0，1組成，且字符串的最后兩個字符相同.構(gòu)造米蘭機M，輸出Y/N表示輸入串是否屬于L.解:設(shè)狀態(tài)集Q為初始狀態(tài)q0

狀態(tài)p0表示輸入串最后字符為0狀態(tài)p1表示輸入串最后字符為122CollegeofComputerScience&Technology,BUPT課堂練習(xí)練習(xí):(書P12219題)設(shè)計米蘭機，輸入是0，1組成的串，要求輸出串對輸入串延遲兩個時間單位.解:M＝(Q

，T，R，δ，g，q0)，T={0，1}R={0，1}分析:可能的狀態(tài)---即一個輸入在輸出前可能處于的狀態(tài)

Q:00q0001q0110q1011q11

Q={q00，q01，q10，q11}23CollegeofComputerScience&Technology,BUPT課堂練習(xí)初始情況:

剛開始工作時輸入前兩個字符，輸出為ε

24CollegeofComputerScience&Technology,BUPT摩爾機摩爾機的輸出只與到達(dá)的狀態(tài)有關(guān)

形式定義:M＝(Q

，T，R，δ，g，q0)g:QR δ:QTQ圖形表示:

δ(q，a)=p

g(p)=b2

q,b1p,b2a25CollegeofComputerScience&Technology,BUPT摩爾機例:

(書P117例4)設(shè)計自動機Ｍ，其輸入串{0，1}*，輸出是(n1-n0)mod4，n0是ω中含0的個數(shù)，n1是ω中含1的個數(shù)。四個狀態(tài)q0，q1，q2，q3

分別輸出0，1，2，3

解:需四個狀態(tài)，取輸出字母表R={0，1，2，3}.

26CollegeofComputerScience&Technology,BUP