形式語(yǔ)言與自動(dòng)機(jī)6ch39b-310

1CollegeofComputerScience&Technology,BUPT第五講3.9(part2)右線(xiàn)性語(yǔ)言的封閉性3.10雙向和有輸出的有限自動(dòng)機(jī)

2CollegeofComputerScience&Technology,BUPT右線(xiàn)性語(yǔ)言的封閉性

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

構(gòu)造NFAM＝(Q

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

否則

F=M形如:3CollegeofComputerScience&Technology,BUPT右線(xiàn)性語(yǔ)言的封閉性設(shè)Ｌ１和Ｌ２是右線(xiàn)性語(yǔ)言，證明Ｌ１Ｌ２為右線(xiàn)性語(yǔ)言(書(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右線(xiàn)性語(yǔ)言的封閉性設(shè)Ｌ１是右線(xiàn)性語(yǔ)言，證明L１*是右線(xiàn)性語(yǔ)言(書(shū)P106~)

構(gòu)造NFAM＝(Q

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

形如

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

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

其中Q=Q1∪｛γ｝γ是一個(gè)新?tīng)顟B(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)=γ —遇到原來(lái)沒(méi)有的字符全轉(zhuǎn)至γ. 對(duì)任意a∈T，δ(γ，a)＝γ

6CollegeofComputerScience&Technology,BUPT右線(xiàn)性語(yǔ)言的封閉性例:(書(shū)P108)

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

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

對(duì)Ｔ＝｛ａ，ｂ，ｃ｝,求Ｌ(Ｍ1)8CollegeofComputerScience&Technology,BUPT右線(xiàn)性語(yǔ)言的封閉性證明Ｌ1∩Ｌ２是封閉的證明：∵Ｌ1∩Ｌ２＝Ｌ1∪Ｌ２∴得證6.證明右線(xiàn)性語(yǔ)言對(duì)于置換是封閉的.(略--自學(xué))9CollegeofComputerScience&Technology,BUPT補(bǔ)充：構(gòu)造自動(dòng)機(jī)的“交”通過(guò)構(gòu)造證明，說(shuō)明正則語(yǔ)言在交運(yùn)算下封閉。設(shè)兩個(gè)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)對(duì)一切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)正則語(yǔ)言的幾個(gè)判定性質(zhì)

判定正則語(yǔ)言是否為空

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

判定兩個(gè)正則語(yǔ)言是否相等11CollegeofComputerScience&Technology,BUPT

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

O(n2).

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

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

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

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

O(n).

以DFA表示正則語(yǔ)言

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

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

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

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

O(n2).1.先將兩個(gè)正則語(yǔ)言的表達(dá)形式都轉(zhuǎn)化為DFA，問(wèn)題轉(zhuǎn)化為兩個(gè)DFA是否是等價(jià)的；2.適當(dāng)重命名，使兩個(gè)DFA沒(méi)有重名的狀態(tài)；3.將兩個(gè)DFA相并，構(gòu)造一個(gè)新的DFA，原來(lái)的終態(tài)仍是終態(tài)，轉(zhuǎn)移邊不發(fā)生任何變化，取任何一個(gè)狀態(tài)為初態(tài)；4.對(duì)新構(gòu)造的DFA運(yùn)用填表算法，如果原來(lái)DFA的兩個(gè)初態(tài)不可區(qū)別，則這兩個(gè)正則語(yǔ)言相等，否則不相等.14CollegeofComputerScience&Technology,BUPT雙向有限自動(dòng)機(jī)(2DFA)定義: 讀入一個(gè)字符之后，讀頭既可以左移一格，也可以右移一格，或者不移動(dòng)的有限自動(dòng)機(jī)，為雙向有限自動(dòng)機(jī).確定的雙向有限自動(dòng)機(jī):每讀入一字符，必須向左或右移動(dòng)，不考慮不移動(dòng)的情況.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}例:書(shū)P113例1. 其狀態(tài)圖為b,R17CollegeofComputerScience&Technology,BUPT有輸出的有限自動(dòng)機(jī) 有輸出的有限自動(dòng)機(jī)是有限自動(dòng)機(jī)的一個(gè)類(lèi)型.這類(lèi)自動(dòng)機(jī)在有字符輸入時(shí)，不僅存在狀態(tài)轉(zhuǎn)換，同時(shí)引起字符輸出. 根據(jù)輸入字符，自動(dòng)機(jī)狀態(tài)，輸出字符三者之間關(guān)系，可有兩類(lèi)有輸出的自動(dòng)機(jī):米蘭機(jī)(Mealy):輸出字符與輸入字符及狀態(tài)有關(guān).摩爾機(jī)(Moore):輸出字符僅與狀態(tài)有關(guān).最大優(yōu)點(diǎn):節(jié)省狀態(tài)!

18CollegeofComputerScience&Technology,BUPT米蘭機(jī)

米蘭機(jī)形式定義: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ù)共同描述了米蘭機(jī)的工作狀況.

19CollegeofComputerScience&Technology,BUPT米蘭機(jī)米蘭機(jī)圖形表示:

δ(p，a)=q

g(p，a)=b

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

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

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

}

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

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

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

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

Q:00q0001q0110q1011q11

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

剛開(kāi)始工作時(shí)輸入前兩個(gè)字符，輸出為ε

24CollegeofComputerScience&Technology,BUPT摩爾機(jī)摩爾機(jī)的輸出只與到達(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摩爾機(jī)例:

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

分別輸出0，1，2，3

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

26CollegeofComputerScience&Technology,BUP