形式語言與自動機基礎

1、第 2 章 形式語言與自動機基礎,2.1 文法和語言2.2 有限自動機2.3 正規(guī)式與有限自動機,,Ch2 形式語言自動機理論基礎 2.2 自動機基礎,第 2 章 形式語言與自動機基礎,2.2 有限自動機基礎 2.2.1 確定的有限狀態(tài)自動機(DFA) 2.2.2 非確定的有限狀態(tài)自動機(NFA) 2.2.3 NFA確定化 2.2.4

2、 DFA化簡,Ch2 形式語言自動機理論基礎 2.2 自動機基礎,,定義2.24 一個確定的有限自動機M ( DFA M)是一個五元組M =（Q, ?, f, q0, Z）,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,確定的有限自動機（ DFA） ( DFA：Deterministic Finite

3、 Automaton ),其中： Q：狀態(tài)的有限集合，每個元素qi (qi ?Q) 稱為一 個狀態(tài)。,?：輸入字符的有限集合(或有窮字母表)。 每個元素是一個輸入字符。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,q0：M的唯一初態(tài)（也稱開始狀態(tài)），q0?Q。,f：狀態(tài)轉(zhuǎn)換函數(shù)：從Q???Q的映射。 例

4、如, f（p,a）=q, q、p?Q, a??。表示了狀態(tài) p在輸入字符a之后轉(zhuǎn)入狀態(tài)q。q也稱為p的后 繼狀態(tài)。,Z： M的終態(tài)集（或接受狀態(tài)）Z?Q。,,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,二. DFA的等價表示,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確

5、定的FA（DFA）,,,狀態(tài)轉(zhuǎn)換圖表示,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,,,狀態(tài)轉(zhuǎn)換圖表示,DFA M =({0,1,2,3}, {a,b}, f , 0 , {3}） f（0,a）=1 f（0,b）=2 f（1,a）=3 f（1,b）=2 f（2,a）=1 f（2,b）=3 f（3,a）=3 f（3,

6、b）=3,,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,二. DFA的等價表示,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,狀態(tài)轉(zhuǎn)換表表示,DFA M =({0,1,2,3}, {a,b}, f , 0 , {3}） f（0,a）=1 f（0,b）=2 f（1,a）

7、=3 f（1,b）=2 f（2,a）=1 f（2,b）=3 f（3,a）=3 f（3,b）=3,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,三 . DFA的識別機制,如果存在Q中的狀態(tài)序列p0，p1，?，pn，滿足下列條件： p0＝q0 f（pi，wi＋1）＝pi＋1，i＝0，1，?，n－1 pn?Z 則M接受（識別

8、）?。,確定的有限自動機M=（Q, ?, f, q0, Z）接受或識別字母表?上的字符串?＝w1w2? wn 的意義：,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,從狀態(tài)圖出發(fā)可以更形象地進行描述。,若存在一條從初態(tài)結點到某一終態(tài)結點的路徑，且在這條路徑上所有弧的標記連接成的字符串等于?，則稱?為DFA M所識別(接受)。,確定的有限自動機M識別的字符串的全體

9、稱為M識別的語言，記為L(M)。 L(M) = {? | ? ? ?* ? f(q0, ?) ?Z },特例的是，若M的初態(tài)結點同時又是終態(tài)結點，則空串ε為M所識別。,設?＝a1a2??an-1an，f(q0,?)=f(f(?f(f(q0,a1,),a2),?,an-1),an),確定的有限自動機M=（Q, ?, f, q0, Z）接受或識別字母表?上的字符串?＝w1w2? wn 的意義：,根據(jù)串沿著序列（路徑）p0，p1

10、，?，找到pn，判斷pn是否屬于終態(tài)集。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,具體識別方法：,如果存在Q中的狀態(tài)序列p0，p1，?，pn，滿足下列條件： p0＝q0 f（pi，wi＋1）＝pi＋1，i＝0，1，?，n－1 pn?Z 則M接受（識別）?。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎

11、 2.2.1 確定的FA（DFA）,,,例2.21: 分析下面描述的DFA M1 。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,$1=110101，其M1對$1的識別過程是：,f（ qee ,1）= qeo,f（ qeo ,1）= qee,f（ qee,0）= qoe,f（ qoe , 1）= qoo,f（ qoo ,0）= qeo,

12、所以串$1= 110101可以被M1接受。,({qee,qoe,qeo,qoo},{0,1},f,qee,{qee}) f(qee ,0)= qoef(qee,1)= qeof(qoe,0)= qeef(qoe,1)= qoof(qeo,0)=qoof(qeo,1)= qeef(qoo,0)=qeo f(qoo,1)= qoe,f（ qee , 110101 ）= f(f（ qee ,11010）,1)=?? ＝

13、f（ qeo ,1）= qee?Z,f（ qeo ,1）= qee?Z,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,DFA M1狀態(tài)圖,1,qee,qeo,qoe,qoo,,,1,1,1,0,0,0,0,對1010:,qee,qeo,qoo,qoe,qee,?Z,可以識別的語言為含偶數(shù)個0和偶數(shù)個1的二進制串集合。,Ch2 形式語言自動機理論基礎

14、 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,例2.22: 設計一臺DFA ，接受含有子串001的所有二進制串。,問題分析：,輸入字母為0或1，所以?＝{0,1},識別過程中有4種可能性：剛才沒看見模式的任何符號；剛才看見一個0；剛才看見00；已經(jīng)看見整個模式001,所以有4個狀態(tài)Q＝{q，q0， q00， q001},其中q為初態(tài)，q001為終態(tài)。,,Ch2 形式語言自動機理論基

15、礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,,,代表兩條有向邊，一個權值為0，一個為1,接受含有子串001的所有二進制串的DFA,,,,與文法等價概念類似： 設有DFA M 和DFA M' ， 若L(M) = L(M') , 則稱M 和 M' 等價。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定

16、的FA（DFA）,,? 注意： 1） DFA是具有離散輸入、輸出系統(tǒng)的一 個純數(shù)學模型； 2） DFA的技巧在于狀態(tài)的設置； 3） DFA映射的唯一性。（ 對于任意字, 在DFA中有且僅有唯一路徑）。,第 2 章 形式語言與自動機基礎,2.2 有限自動機基礎 2.2.1 確定的有限狀態(tài)自動機(DFA) 2.2.2 非確定的有限狀

17、態(tài)自動機(NFA) 2.2.3 NFA確定化 2.2.4 DFA化簡,Ch2 形式語言自動機理論基礎 2.2 自動機基礎,,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.2 非確定的FA(NFA),,,一. NFA的定義 DFA的確定性表現(xiàn)在其映射函數(shù)是一個單值函數(shù)。但是實際問題中，映射函數(shù)往往是一個多值函數(shù)。,例如，源程序中掃

18、描到一個字母時，不同的語言對應多種情況：,FORTRAN中： 標識符/格式轉(zhuǎn)換碼E、D…,C語言中：標識符/ if / switch ….,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.2 非確定的FA(NFA),,,? NFA在實際中更具普遍性。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.2 非確定的FA(NFA),,,定義2.2

19、5 一個非確定的有限自動機M ( NFA M)是一個五元組M =（Q, ?, f, q0, Z）,其中： Q， ?， Z， q0同DFA。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.2 非確定的FA(NFA),,,f：狀態(tài)轉(zhuǎn)換函數(shù)。 從Q?? ∪{?} ?2Q的映射。這里的后繼狀態(tài)不是唯一的，它是狀態(tài)集Q的子集。,? 注

20、意：NFA亦可用狀態(tài)圖和狀態(tài)表表示。DFA和NFA統(tǒng)稱為有限自動機FA。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.2 非確定的FA(NFA),,,例2.23: 設有一個非確定的有限自動機M NFA M=（{q0, q1, q2, q3, q4},{0,1}, f , q0, { q2,q4}）,Ch2 形式語言自動機理論基礎 2.2 自動機基礎

21、 2.2.2 非確定的FA(NFA),,,q1,q3,,q4,,,,,,q2,q0,0,0,1,1,0,1,0,1,0,1,,f（q0,0）= {q0,q3} f（q0,1）= {q0,q1} f（q1,0）= ? f（q1,1）={ q2} f（q2,0）= {q2} f（q2,1）= {q2} f（q3,0）= {q4} f（q3，

22、1）= ? f（q4,0）= {q4} f（q4,1）={ q4},Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,二 . NFA的識別機制,如果存在Q中的狀態(tài)序列p0，p1，?，pn，滿足下列條件： p0＝q0 pi＋1?f（pi，wi＋1），i＝0，1，?，n－1 pn?Z 則M接受（識別）?。,非確定的有限自動機M=（Q,

23、 ?, f, q0, Z）接受或識別字母表?上的字符串?＝w1w2? wn ， wi? ?? ∪{?}的意義：,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,從狀態(tài)轉(zhuǎn)換圖進行描述：,若存在一條從初態(tài)結點到某一終態(tài)結點的路徑，且在這條路徑上所有弧的標記連接成的字符串等于?，則稱?為NFA M所識別(接受)。,非確定的有限自動機M識別的字符串的全體稱為M識別的語言，

24、記為L(M)。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.2 非確定的FA(NFA),,,例2.23的非確定的有限自動機M所識別的語言L（M）？,L（M）＝{含有兩個相鄰的0或兩個相鄰的1的由0和1組成的字符串},q1,q3,,q4,,,,,,q2,q0,0,0,1,1,0,1,0,1,0,1,,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2

25、.2 非確定的FA(NFA),,,例2.24: 給出一個識別語言為{a}+?+的NFA M 如下圖所示。,對字符串a(chǎn)aa的接受路徑為0，1，2，2，2，接受 路徑中邊的標記是?，a，a，a，它們的連接為字符串a(chǎn)aa，?在連接中消失。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,例2.22: 設計一臺FA ，接受含有子串00

26、1的所有二進制串。,問題分析：,輸入字母為0或1，所以?＝{0,1},識別過程中有4種可能性：剛才沒看見模式的任何符號；剛才看見一個0；剛才看見00；已經(jīng)看見整個模式001,所以有4個狀態(tài)Q＝{q，q0， q00， q001},其中q為初態(tài)，q001為終態(tài)。,,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.1 確定的FA（DFA）,,,,,接受含有子串001的所有二進制串的

27、FA,0,1,0,1,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.2 非確定的FA(NFA),,,NFA DFA f ( Q?? ∪{?}) f ( Q?? )

28、 f f (Q?? ∪{?}) 2Q f ( Q??) Q,,,,,,,,三. NFA和DFA的區(qū)別,? 注意：在NFA中對字的識別時驗證的路徑可能不唯一。,第 2 章 形式語言與自動機基礎,2.2 有限自動機基礎 2.2.1 確定的有限狀態(tài)自動機(DFA) 2.2.2 非確定的有限狀態(tài)自動機

29、(NFA) 2.2.3 NFA確定化 2.2.4 DFA化簡,Ch2 形式語言自動機理論基礎 2.2 自動機基礎,,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,,,定理2.1 對任何一個NFA M，都存在一個DFA M ' , 使 L(M' )=L(M)。,定理2.1說明： 對任何一個NFA M，都存

30、在一個DFA M' ，使M和M'所識別的字的全體相同，我們可簡記為 M' ＝M。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,,,NFA確定化的算法 — 子集法。,定義2.26 假設I是NFA M' 狀態(tài)集Q的一個子集。(即I?Q)，則定義ε-closure(I)為 ： (1)  

31、60;若qi∈I，則qi ∈ε-closure(I)； (2)  若qi ∈I，則從qi出發(fā)經(jīng)過任意條ε弧而能到達 的任何狀態(tài)qj ，有qj ∈ε-closure(I)。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,,,例2.25: 有NFA M如下圖所示。,Ch2 形式語言自動機理論基礎 2.2 自動

32、機基礎 2.2.3 NFA確定化,,,設 I= {1,5} 則 ε-closure({1,5}) ＝ε-closure ({5}) ∪ε-closure ({1}) ＝{1,2,5,6},設 I={5},設 I={1},則 ε-closure(I) = ε-closure({5}) = {5, 6, 2},則

33、 ε-closure({1}) = {1, 2},Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,,,,? 綜述：,1）狀態(tài)集I的ε-closure(I)仍是一狀態(tài)集；,2） 狀態(tài)集（ε-closure(I)）即為在I中的狀態(tài) 下，不輸入任何字符所能到達的狀態(tài)的 全體并包含I中的狀態(tài)，

34、就是狀態(tài)集I的 ε閉包。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,,,,算法2.1 (求I的ε-closure(I)) 輸入：NFA M 和M的子集I 輸出：ε-closure(I) 算法： set_of_state look (set_of_state I) {

35、 look=I; do {對look中每一個狀態(tài)i if ? 結構 look = look + {j};

36、 }while(look不再擴大) },i,j,,?,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,,,定義2.27 （狀態(tài)集合I的a弧轉(zhuǎn)換Ia ） 設 NFA M' =(Q，∑，f，q0，Z) 假定I ?Q，a∈∑，則定義 Ia=ε-closure({p|?q?? -

37、close(I)，p?f(q，a)})。,注意：計算Ia需三步： I的?閉包；閉包的映射集；映射集的?閉包。Ia=ε-closure(f (? -close(I) ，a))。,設I={2,5} 則 Ia =ε-closure（f({2,5,6},a） =ε-closure（{3}）= { 3,8 },Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.

38、3 NFA確定化,,,例2.26: 有NFA M如例2.25。  設I={1} 求Ia 則ε-closure（I）＝{1, 2} f({1,2},a)=f(1,a)∪f(2,a) ={3,4,5} Ia =ε-closure（{3,4,5}） = { 2, 3, 4, 5, 6,7,8 },Ch2 形式語言自動機

39、理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,,,NFA確定化關鍵： 1） 消去ε??； 2） 解決映射不唯一問題。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,,,子集法——NFA的確定化算法,對NFA M’ =（Q, {?1, ?2, … , ?n }, f, q0, Z）,,,Step

40、1:初始化,設一狀態(tài)表：,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,,,,,,,,I11,I12,I1n,Step2:求I?n,…,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,,,Step3: 重新命名,對求得的狀態(tài)表（DFA M）的第一列各狀態(tài)子集重新命名，然后代入相應的狀態(tài)表元素；

41、 第一列第一行為DFA M 的惟一初態(tài)； 含有原M?終態(tài)的I為M終態(tài)。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,,,例2.27: 有NFA M’如下圖所示。,1,2,3,8,5,4,,6,,7,,,,,,,,,a,a,a,ε,ε,ε,ε,,ε,,,ε-closure(q0)={1,2},Ch2 形式語言自動機理論基礎

42、 2.2 自動機基礎 2.2.3 NFA確定化,{2, 3, 4, 5, 6, 7, 8},{ 3, 8},?,1 2,01 2,ε,1,2,3,8,5,4,,,,,,,,,a,a,a,ε,ε,ε,,ε,,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,,,,,2,1,3,8,5,4,,,,,,,,,a,a,a,ε,ε,ε

43、,ε,,ε,,,,例2.28: 有NFA M’如下圖所示。,1,p,r,s,,,,,0,0,1,0|1,0|1,q,1,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,,,{q, s},{ q },{ r },{ r },{ q,r,p },{ q,r },{ q,r },{ s },{ p },{ s },{ q,r,s },{ q,r,s },{ q,r,p

44、 },{ r,s },{ r,s },{ r,s },{ q,r,p },{ q,r,p },{ p },{ p },{ s },0*123 4*5678,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.3 NFA確定化,1,,,r,q,s,0,1,0,1,0,1,0,1,,p,,1,?,,,Ch2 形式語言自動機理論基礎 2.2 自動機基礎

45、 2.2.3 NFA確定化,第 2 章 形式語言與自動機基礎,2.2 有限自動機基礎 2.2.1 確定的有限狀態(tài)自動機(DFA) 2.2.2 非確定的有限狀態(tài)自動機(NFA) 2.2.3 NFA確定化 2.2.4 DFA化簡,Ch2 形式語言自動機理論基礎 2.2 自動機基礎,,所謂DFA M的化簡是指尋找一個狀態(tài)數(shù)比 較少的DFA M?，即規(guī)約的DFA M?，使得

46、 L(M)=L(M?)，可以證明存在一個最小 DFA M?，使得L(M)=L(M?)。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,定義2.28 如果DFA M既沒有無關狀態(tài)，且沒有彼此等價的狀態(tài)，則稱DFA M是規(guī)約的(即最小的DFA M)。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎

47、2.2.4 DFA的化簡,,,定義2.29(無關狀態(tài)或多余狀態(tài)或無用狀態(tài)) 如果從DFA M的初態(tài)開始，任何輸入序列都不能到達的那些狀態(tài)稱為無關狀態(tài)。,DFA化簡實現(xiàn)思想： 通過刪除無關狀態(tài)，合并等價狀態(tài)的歸約過程，直至得到歸約機( 最小的DFA )。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,0 1,s

48、tate,,,6,3,8,1,0,7,0,8,6,1,3,5,6,5,4,7,5,3,5,2,2,7,2,1,5,1,0,,,,,,,,,,,,,,,,,,,,,,,,,例2.29: 有FA M,0,1,5,2,7,3,1：5：,2：7：,3：,,,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,,,Ch2 形式語言自動機理論基礎 2.2

49、自動機基礎 2.2.4 DFA的化簡,,,定義2.30 (等價狀態(tài)、可區(qū)分狀態(tài)) 設DFA M的兩個不同狀態(tài) q1，q2，如果對任意輸入字符串ω，從q1，q2狀態(tài)出發(fā)，總是同時到達接收狀態(tài)或拒絕狀態(tài)之中，稱q1，q2是等價的。即對于?ω，(ω∈∑*)有：f(q1，ω)= p1 ， f(q2，ω)=p2 ，p1 ,p2∈Z 或p1 ,p2?Z ，則q1，q2等價，記作 q1?q2 。如果兩

50、個狀態(tài)不等價，則稱q1，q2是可區(qū)別的（或者說q1，q2 被ω 所區(qū)別）。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,,,DFA合并等價狀態(tài)的實現(xiàn)方法：劃分法。 劃分法的核心是尋找且合并等價狀態(tài)。即：將給定的DFA劃分為互不相交的子集，使得任何兩個不同子集的狀態(tài)都是可區(qū)分的，而同一個子集的任何兩個狀態(tài)都是等價的。然后每個子集中的狀態(tài)合并為一個狀

51、態(tài)。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,,,劃分法的算法實現(xiàn)步驟如下： (1) 把M的所有狀態(tài)Q按終態(tài)與非終態(tài)劃分成兩個狀 態(tài)子集Z及Q―Z，構成初始劃分(或稱基本劃分)， 記作：π= { Z, Q―Z }；,(2)  設當前的劃分π中已經(jīng)含有m個子集，即： π={ Q1，Q2，…，Qm } 其

52、中，屬于不同子集的狀態(tài)是可區(qū)分的，而屬于同一子集中的各狀態(tài)是待區(qū)分的。即需要對每一個子集Qi={qi1，qi2，…，qin}中各狀態(tài)qir (qir∈Q, 1≤r≤n) 進行考察，確認是否還能對它們進行劃分。 若能進行劃分，則形成新的劃分πnew 。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,,,(3) 若πnew≠π，則將其作為π再重復(2)中

53、的過程，如此下去，直到最后得到一個劃分π，使πnew＝π，即π中的各個子集不能再進行劃分為止。,(4)對所得的最后劃分π，對它的每個子集Qj ={qj1，qj2，…，qjr}進行重新命名為一個狀態(tài)，如pj作為π 中子集Qj的名字，這些新命名的狀態(tài)pj組成了M ' 的狀態(tài)集Q ' 。而且，若Qj中含有M的初態(tài),則pj為M ' 的初態(tài);若Qj中含有M的終態(tài)，則pj為M '的終態(tài)。此外，對狀態(tài)轉(zhuǎn)移函數(shù)作相應的修

54、改。,第（2）步詳解：例如，qir和qis是Qi中的兩個狀態(tài)，若有某個a∈∑,使得f (qir, a)= qju 及f (qis, a)= qkv，而狀態(tài)qju 及qkv分別屬于π中兩個不同的子集Qj和Qk，由于qju 與qkv為某一符號串ω所區(qū)分，從而qir和qis必為aω所區(qū)分，故應將子集Qi進一步劃分，使qir和qis分別屬于Qi的不同子集。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎

55、 2.2.4 DFA的化簡,(2)需要對每一個子集Qi={qi1，qi2，…，qin}中各狀態(tài)qir (qir∈Q,1≤r≤n) 進行考察，確認是否還能對它們進行劃分。,第（2）步需要考察：對于每一個子集Qi及每一個a∈∑， Qia= f (Qi , a) = ∪ f (qir, a)若Qia中的狀態(tài)分別落在π中的p個不同的子集，則將Qi分為p個更小的狀態(tài)子集Qi1，Qi2 ，…，Qip，若f

56、(Qi ,a)中的全部狀態(tài)都落在π的同一子集之中，則不再劃分Qi。特殊情況：若對某狀態(tài)qir，f (qir, a)無意義，則qir與任何f (q, a)有定義的狀態(tài)都是可區(qū)分的。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,,,例2.30： 設確定有

57、限自動機DFA M' ，如圖所示。,Step1: 形成基本劃分。劃分為終態(tài)集和非終態(tài)集。 P0 = （ {0,1} , {2}）,Step2: 重新命名。令 {0,1}為0，令{2}為1。,,b,a,b,a,a,,0,2,,1,,,,,考察 ： f(0,a)=1? {0,1} f(0,b)=2? {2} f(1,a)=1? {0,1} f(1,b)=2? {2},Ch

58、2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,,,化簡后的DFA M,,重新命名： {0,1}為0，{2}為1。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,,,例2.31：對下圖的DFA M化簡。,a,a,a,a,,b,b,a,,b,a,b,b,1,a,,6,4,3,,7,,5,,,,,,,,

59、,b,,2,,,b,,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,,,第一步，對M的狀態(tài)形成基本劃分?０，?０有兩個組q１ , q2，即 ?０=({1, 2, 3, 4} , { 5, 6, 7 })= ( q1,q2 ),第二步，對q１ , q2考察： ?０中的q１的映射，f(1,a)=6 ?q2 f(1,b)=3?q1

60、 f(2,a)=7 ?q2 f(2,b)=3?q1 f(3,a)=1 ?q1 f(3,b)=5?q2 f(4,a)=4 ?q1 f(4,b)=6?q2,輸入a和b的情況下， q1中的狀態(tài)1,2與狀態(tài)3,4 是不等

61、價的。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,,,對q1進行劃分，形成： q1=(q3, q4)=({1,2}，{3,4}),,由此，對基本劃分?0 經(jīng)考察后，形成新的劃分?1： ?1 =（q2，q3，q4） = ( {5,6,7}， {1,2}，{3,4}),Ch2 形式語言自動機理論基礎 2.2 自動機基礎

62、 2.2.4 DFA的化簡,,,第三步，考察?1中的q2：f(5,a)=7 ?q2 f(5,b)=3?q4 f(6,a)=4 ?q4 f(6,b)=1?q3 f(7,a)=4 ?q4 f(7,b)=2?q3輸入a和b的情況下， q2中的狀態(tài)5與狀態(tài) 6,7是不等價的，形成q2的新的劃分： q2 =( q5, q6 )=（{5}，{6, 7}）,Ch2 形式語言自動機理論基礎

63、 2.2 自動機基礎 2.2.4 DFA的化簡,,,由此，對劃分?1 經(jīng)考察且劃分后，形成新的劃分?2： ?2 =（q3，q4，q5，q6） = ( {1,2}，{3,4}，{5}，{6,7} ),第四步，對新形成的劃分?2 重復上述考察步驟，對?2中q3, q5，q6的狀態(tài)在輸入字符a,b的情況下考察其是等價的。,對?2中q4的狀態(tài){ 3,4 }在輸入字符a的情況下

64、考察其是不等價的，再劃分為 q4=（q7, q8）=（{3}, {4}）,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,,,對劃分? 2 經(jīng)考察且劃分后，形成新的劃分? 3：? 3 =(q3, q5, q6, q7, q8 )=({1,2}, {5}, {6,7} , {3}, {4} ),Ch2 形式語言自動機理論基礎 2.2 自動機基礎

65、 2.2.4 DFA的化簡,第六步，重新命名。,第五步，對新形成的劃分?3 =(q3, q5, q6, q7, q8 )=({1,2}, {5}, {6,7} , {3}, {4} )重復上述步，對?3中的q3, q5，q6， q7, q8的狀態(tài)在輸入字符a,b的情況下考察其是等價的。,Ch2 形式語言自動機理論基礎 2.2 自動機基礎 2.2.4 DFA的化簡,,,?