形式語言與自動機6 ch3.9b-3.10

1、1College of Computer Science & Technology, BUPT第五講第五講3.9 (part 2) 右線性語言的封閉性右線性語言的封閉性 3.10 雙向和有輸出的有限自動機雙向和有輸出的有限自動機 2College of Computer Science & Technology, BUPT右線性語言的封閉性右線性語言的封閉性 上節(jié)從文法產(chǎn)生的角度證明了右線性語言及其并，積，閉上節(jié)從文法產(chǎn)生的角度證明了右線性語言及其并，積，閉包是正則集；本節(jié)用有限自動機接受的語言來證明。包是正則集；本節(jié)用有限自動機接受的語言來證明。(書書P103)1.1.設(shè)設(shè)和

2、和是右線性語言，證明是右線性語言，證明為右線性語言為右線性語言 構(gòu)造NFA M(Q ，T ，q0，F(xiàn))QQ1Qq0 q0是新的起始狀態(tài)當(dāng)，q 否則 F =M形如形如: 3College of Computer Science & Technology, BUPT右線性語言的封閉性右線性語言的封閉性 設(shè)設(shè)和和是右線性語言，證明是右線性語言，證明為右線性語言為右線性語言(書書P104) 構(gòu)造NFA M(Q ，T ， q0， F), 其中Q=QQ q0 =q1 當(dāng)q2F2 當(dāng)q2F2 F =M形如形如: 4College of Computer Science & Technolog

3、y, BUPT右線性語言的封閉性右線性語言的封閉性 設(shè)設(shè)是右線性語言，證明是右線性語言，證明L*是右線性語言是右線性語言(書書P106) 構(gòu)造構(gòu)造NFA M(Q ，T ，q0，F(xiàn)), Q = Q1q q是新的起始狀態(tài)是新的起始狀態(tài), F=1qL* 形如形如 5College of Computer Science & Technology, BUPT右線性語言的封閉性右線性語言的封閉性 設(shè)設(shè)是右線性語言，證明是右線性語言，證明 L 是右線性語言是右線性語言證明：證明：構(gòu)造接受構(gòu)造接受1的的M(Q ，T ， q0， F)其中其中Q = Q1 是一個新狀態(tài)是一個新狀態(tài) T T1 q0 =q

4、1 (Q11) (即將即將1的終止?fàn)顟B(tài)變?yōu)榈慕K止?fàn)顟B(tài)變?yōu)镸的非終止?fàn)顟B(tài)的非終止?fàn)顟B(tài))定義為定義為: 當(dāng)當(dāng)aT1 ，則則(q，a)= 1(q，a) 保留原有函數(shù)保留原有函數(shù)當(dāng)當(dāng)aTT1，則則(q，a)= 遇到原來沒有的字符全轉(zhuǎn)至遇到原來沒有的字符全轉(zhuǎn)至.對任意對任意aT， (，a) 6College of Computer Science & Technology, BUPT右線性語言的封閉性右線性語言的封閉性 例例: (: (書書P108)P108) 對下圖的對下圖的1 , ,求求( (1 1) ) 7College of Computer Science & Technolo

5、gy, BUPT右線性語言的封閉性右線性語言的封閉性 例例: 設(shè)設(shè)DFA1（q,q,，q,q,q） 對，對，, 求求(1) 8College of Computer Science & Technology, BUPT右線性語言的封閉性右線性語言的封閉性 證明證明1是封閉的是封閉的 證明：證明：11 得證得證6. 證明右線性語言對于置換是封閉的證明右線性語言對于置換是封閉的. (略略 - 自學(xué)自學(xué)) 9College of Computer Science & Technology, BUPT補充： 構(gòu)造自動機的“交”通過構(gòu)造證明，說明正則語言在交運算下封閉。通過構(gòu)造證明，說明

6、正則語言在交運算下封閉。設(shè) 兩個DFA M1(Q1 ，T ，1，q1，F(xiàn)1) M2(Q 2，T ，2，q2，F(xiàn)2)構(gòu)造新的 DFA M, M(Q1 x Q 2，T，q1，q2 ，F(xiàn)1 x F2)對一切對一切p1 Q1, p2 Q2， a T，（p1，p2, a）= 1（p1, a）, 2（p2, a）則L（M）= L（M1）L（M2）10College of Computer Science & Technology, BUPT有關(guān)正則語言的幾個判定性質(zhì) 判定正判定正則則語言是否為空語言是否為空 判定正判定正則則語言中是否包含特定的字符串語言中是否包含特定的字符串 判定兩個正判定兩個正

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

8、 O(n2). 基礎(chǔ)基礎(chǔ)：初態(tài)是可達的：初態(tài)是可達的： 歸納歸納：設(shè)狀態(tài)：設(shè)狀態(tài) q 是可達的，若對于某個輸入符號或是可達的，若對于某個輸入符號或 ， q 可轉(zhuǎn)移到可轉(zhuǎn)移到 p ，則則 p 也是可達的：也是可達的：12College of Computer Science & Technology, BUPT 判定正判定正則則語言中是否包含特定的字符串語言中是否包含特定的字符串- 判定算法判定算法 從初態(tài)開始，處理輸入字符串從初態(tài)開始，處理輸入字符串 w ，如果可如果可 以結(jié)束于某一終態(tài)，則該正規(guī)語言中包含以結(jié)束于某一終態(tài)，則該正規(guī)語言中包含 w，否則不否則不 包含包含 w 。- 算法

9、復(fù)雜度算法復(fù)雜度 設(shè)輸入字符串設(shè)輸入字符串w 的長度的長度 |w|=n，上述判上述判定定 算法的復(fù)雜度為算法的復(fù)雜度為 O(n). 以以 DFA 表示正則語言表示正則語言 以正則表達式表示正則語言以正則表達式表示正則語言將其轉(zhuǎn)化為等價將其轉(zhuǎn)化為等價的的 NFA ，然后執(zhí)行上述過程然后執(zhí)行上述過程. 以以 NFA （或或NFA ）表示正則語言表示正則語言 可以將其轉(zhuǎn)化為可以將其轉(zhuǎn)化為等價的等價的 DFA，然后執(zhí)行上述過程；也可以直接模擬其處然后執(zhí)行上述過程；也可以直接模擬其處理字符串的過程，判定算法的復(fù)雜度為理字符串的過程，判定算法的復(fù)雜度為 O(n2s), 其中其中n為為字符串的長度，字符串的

10、長度，s為為NFA （或或NFA ）的狀態(tài)數(shù)目的狀態(tài)數(shù)目.13College of Computer Science & Technology, BUPT 判定兩個正判定兩個正則則語言是否相等語言是否相等 判定算法判定算法 可由采取如下步驟：可由采取如下步驟： 算法復(fù)雜度算法復(fù)雜度 以上算法的復(fù)雜度即填表算法的以上算法的復(fù)雜度即填表算法的 復(fù)雜度，其上限為復(fù)雜度，其上限為O(n4) ；可以適當(dāng)設(shè)計填表可以適當(dāng)設(shè)計填表 算法的數(shù)據(jù)結(jié)構(gòu)，使其復(fù)雜度降為算法的數(shù)據(jù)結(jié)構(gòu)，使其復(fù)雜度降為 O(n2) .1. 先將兩個正則語言的表達形式都轉(zhuǎn)化為先將兩個正則語言的表達形式都轉(zhuǎn)化為 DFA ，問題問題

11、 轉(zhuǎn)化為兩個轉(zhuǎn)化為兩個DFA是否是等價的；是否是等價的；2. 適當(dāng)重命名，使兩個適當(dāng)重命名，使兩個DFA沒有重名的狀態(tài)；沒有重名的狀態(tài)；3. 將兩個將兩個DFA相并，相并， 構(gòu)造一個新的構(gòu)造一個新的DFA ，原來的終態(tài)原來的終態(tài)仍是終態(tài)，轉(zhuǎn)移邊不發(fā)生任何變化，取任何一個狀態(tài)仍是終態(tài)，轉(zhuǎn)移邊不發(fā)生任何變化，取任何一個狀態(tài)為初態(tài)；為初態(tài)；4. 對新構(gòu)造的對新構(gòu)造的DFA運用填表算法，如果原來運用填表算法，如果原來DFA的兩個的兩個初態(tài)不可區(qū)別，則這兩個正則語言相等，否則不相等初態(tài)不可區(qū)別，則這兩個正則語言相等，否則不相等.14College of Computer Science & Te

12、chnology, BUPT雙向有限自動機雙向有限自動機 (2DFA)定義定義:n讀入一個字符之后，讀頭既可以左移一格，也可以右移一格，或者不移動的有限自動機， 為雙向有限自動機.n確定的雙向有限自動機: 每讀入一字符，必須向左或右移動，不考慮不移動的情況. 15College of Computer Science & Technology, BUPT2DFA的形式定義2DFA M(Q ，T ， q0， F) 是從是從QTQL，R的映射的映射.即即 (q，a)=(p，R) 或或 (q，a)=(p，L) （在狀態(tài)在狀態(tài)q， 讀入讀入a， 進入狀態(tài)進入狀態(tài)p，讀頭向右讀頭向右(向左向左)

13、移一格）移一格） 用格局描述用格局描述: 設(shè)有設(shè)有1q2 1 - 已輸入串已輸入串q - 當(dāng)前狀態(tài)當(dāng)前狀態(tài) 2 - 待輸入串待輸入串(q，am+1)=(p，R)的格局表示的格局表示:a1 a2am q am+1an a1 a2am+1 p am+2an(q，am+1)=(p，L)的格局表示的格局表示:a1 a2am q am+1an a1 a2am-1 p am am+1an 16College of Computer Science & Technology, BUPT2DFA2DFA接受的字符串集合是接受的字符串集合是: L(M)=| q*q，q F例例: 書書P113 例例1.

14、其狀態(tài)圖為其狀態(tài)圖為b,R17College of Computer Science & Technology, BUPT有輸出的有限自動機有輸出的有限自動機 有輸出的有限自動機是有限自動機的一個類型有輸出的有限自動機是有限自動機的一個類型.這類自動機在有字符輸入時，不僅存在狀態(tài)轉(zhuǎn)換，這類自動機在有字符輸入時，不僅存在狀態(tài)轉(zhuǎn)換，同時引起字符輸出同時引起字符輸出. 根據(jù)輸入字符，自動機狀態(tài)，輸出字符三者之根據(jù)輸入字符，自動機狀態(tài)，輸出字符三者之間關(guān)系，可有兩類有輸出的自動機間關(guān)系，可有兩類有輸出的自動機:n 米蘭機米蘭機(Mealy): 輸出字符與輸入字符及狀態(tài)有關(guān)輸出字符與輸入字符及狀

15、態(tài)有關(guān).n 摩爾機摩爾機(Moore): 輸出字符僅與狀態(tài)有關(guān)輸出字符僅與狀態(tài)有關(guān).最大優(yōu)點最大優(yōu)點: : 節(jié)省狀態(tài)節(jié)省狀態(tài)! ! 18College of Computer Science & Technology, BUPT米蘭機米蘭機米蘭機米蘭機形式定義形式定義: M(Q ，T ，R， g ， q0)其中其中 Q 有限狀態(tài)集合有限狀態(tài)集合 T 有限輸入字母表有限輸入字母表 R 有限輸出字母表有限輸出字母表 : QTQ 轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù) g : QTR 輸出函數(shù)輸出函數(shù) q0: 初始狀態(tài)初始狀態(tài) q0 Q和和g函數(shù)共同描述了米蘭機的工作狀況函數(shù)共同描述了米蘭機的工作狀況. 19Co

16、llege of Computer Science & Technology, BUPT米蘭機米蘭機米蘭機米蘭機圖形表示圖形表示: (p(p，a)=qa)=q g(pg(p，a)=ba)=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, 220College of Computer Science & Technology, BUPT米蘭機米蘭機例例: （P115 例3）設(shè)計米蘭機

17、， 其輸入0，1*， 當(dāng)輸入串有奇數(shù)個1時，輸出1. 當(dāng)輸入串有偶數(shù)個1時，輸出0. 解解: 需二個狀態(tài)q0，q1 q0 表示輸入串有偶數(shù)個1， q1 表示輸入串有奇數(shù)個121College of Computer Science & Technology, BUPT課堂練習(xí)課堂練習(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 表示輸入串最后字符為122College of Computer Science & Technology, BUPT

18、課堂練習(xí)課堂練習(xí)練習(xí)練習(xí): (書書P122 19題題) 設(shè)計米蘭機，輸入是0，1組成的串，要求輸出串對輸入串延遲兩個時間單位. 解: M(Q ，T ，R， g ， q0)， T=0，1 R=0，1 分析分析:可能的狀態(tài)-即一個輸入在輸出前可能處于的狀態(tài) Q: 00 q00 01 q01 10 q10 11 q11 Q= q00， q01， q10， q1123College of Computer Science & Technology, BUPT課堂練習(xí)課堂練習(xí)初始情況初始情況: 剛開始工作時輸入前兩個字符，輸出為 24College of Computer Science &am

19、p; Technology, BUPT摩爾機摩爾機 摩爾機的輸出只與到達的狀態(tài)有關(guān)摩爾機的輸出只與到達的狀態(tài)有關(guān) 形式定義形式定義: M(Q ，T ，R， g ， q0) g : Q R: Q T Q 圖形表示圖形表示: (q(q，a)= pa)= p g (p)= bg (p)= b2 2 q,b1p,b2a25College of Computer Science & Technology, BUPT摩爾機摩爾機例例: (書P117 例4)設(shè)計自動機，其輸入串0，1*，輸出是(n1- n0) mod 4，n0是中含0的個數(shù)，n1是中含1的個數(shù)。四個狀態(tài) q0， q1， q2， q3 分別輸出0，1，2，3 解解: 需四個狀態(tài)， 取輸出字母表 R=0，1，2，3. 26College of Computer Sci