形式語(yǔ)言與自動(dòng)機(jī)基礎(chǔ)

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

2、 DFA化簡(jiǎn),Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ),,定義2.24 一個(gè)確定的有限自動(dòng)機(jī)M ( DFA M)是一個(gè)五元組M =（Q, ?, f, q0, Z）,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.1 確定的FA（DFA）,,,確定的有限自動(dòng)機(jī)（ DFA） ( DFA：Deterministic Finite

3、 Automaton ),其中： Q：狀態(tài)的有限集合，每個(gè)元素qi (qi ?Q) 稱為一 個(gè)狀態(tài)。,?：輸入字符的有限集合(或有窮字母表)。 每個(gè)元素是一個(gè)輸入字符。,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 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 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.1 確定的FA（DFA）,,,二. DFA的等價(jià)表示,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.1 確

5、定的FA（DFA）,,,狀態(tài)轉(zhuǎn)換圖表示,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 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 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.1 確定的FA（DFA）,,,二. DFA的等價(jià)表示,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 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 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.1 確定的FA（DFA）,,,三 . DFA的識(shí)別機(jī)制,如果存在Q中的狀態(tài)序列p0，p1，?，pn，滿足下列條件： p0＝q0 f（pi，wi＋1）＝pi＋1，i＝0，1，?，n－1 pn?Z 則M接受（識(shí)別

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

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

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

11、 2.2.1 確定的FA（DFA）,,,例2.21: 分析下面描述的DFA M1 。,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.1 確定的FA（DFA）,,$1=110101，其M1對(duì)$1的識(shí)別過(guò)程是：,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 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.1 確定的FA（DFA）,,,DFA M1狀態(tài)圖,1,qee,qeo,qoe,qoo,,,1,1,1,0,0,0,0,對(duì)1010:,qee,qeo,qoo,qoe,qee,?Z,可以識(shí)別的語(yǔ)言為含偶數(shù)個(gè)0和偶數(shù)個(gè)1的二進(jìn)制串集合。,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)

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

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

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

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

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

19、5 一個(gè)非確定的有限自動(dòng)機(jī)M ( NFA M)是一個(gè)五元組M =（Q, ?, f, q0, Z）,其中： Q， ?， Z， q0同DFA。,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 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)稱為有限自動(dòng)機(jī)FA。,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.2 非確定的FA(NFA),,,例2.23: 設(shè)有一個(gè)非確定的有限自動(dòng)機(jī)M NFA M=（{q0, q1, q2, q3, q4},{0,1}, f , q0, { q2,q4}）,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ)

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 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.1 確定的FA（DFA）,,,二 . NFA的識(shí)別機(jī)制,如果存在Q中的狀態(tài)序列p0，p1，?，pn，滿足下列條件： p0＝q0 pi＋1?f（pi，wi＋1），i＝0，1，?，n－1 pn?Z 則M接受（識(shí)別）?。,非確定的有限自動(dòng)機(jī)M=（Q,

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

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

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

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

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

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

29、(NFA) 2.2.3 NFA確定化 2.2.4 DFA化簡(jiǎn),Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ),,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.3 NFA確定化,,,定理2.1 對(duì)任何一個(gè)NFA M，都存在一個(gè)DFA M ' , 使 L(M' )=L(M)。,定理2.1說(shuō)明： 對(duì)任何一個(gè)NFA M，都存

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

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

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

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

34、就是狀態(tài)集I的 ε閉包。,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 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 {對(duì)look中每一個(gè)狀態(tài)i if ? 結(jié)構(gòu) look = look + {j};

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

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

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

39、理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.3 NFA確定化,,,NFA確定化關(guān)鍵： 1） 消去ε??； 2） 解決映射不唯一問(wèn)題。,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.3 NFA確定化,,,子集法——NFA的確定化算法,對(duì)NFA M’ =（Q, {?1, ?2, … , ?n }, f, q0, Z）,,,Step

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

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

42、 2.2 自動(dòng)機(jī)基礎(chǔ) 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 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 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 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 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 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.3 NFA確定化,1,,,r,q,s,0,1,0,1,0,1,0,1,,p,,1,?,,,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ)

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

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

47、2.2.4 DFA的化簡(jiǎn),,,定義2.29(無(wú)關(guān)狀態(tài)或多余狀態(tài)或無(wú)用狀態(tài)) 如果從DFA M的初態(tài)開始，任何輸入序列都不能到達(dá)的那些狀態(tài)稱為無(wú)關(guān)狀態(tài)。,DFA化簡(jiǎn)實(shí)現(xiàn)思想： 通過(guò)刪除無(wú)關(guān)狀態(tài)，合并等價(jià)狀態(tài)的歸約過(guò)程，直至得到歸約機(jī)( 最小的DFA )。,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.4 DFA的化簡(jiǎn),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 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.4 DFA的化簡(jiǎn),,,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2

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

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

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

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

53、的過(guò)程，如此下去，直到最后得到一個(gè)劃分π，使πnew＝π，即π中的各個(gè)子集不能再進(jìn)行劃分為止。,(4)對(duì)所得的最后劃分π，對(duì)它的每個(gè)子集Qj ={qj1，qj2，…，qjr}進(jìn)行重新命名為一個(gè)狀態(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)。此外，對(duì)狀態(tài)轉(zhuǎn)移函數(shù)作相應(yīng)的修

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

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

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

57、限自動(dòng)機(jī)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 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.4 DFA的化簡(jiǎn),,,化簡(jiǎn)后的DFA M,,重新命名： {0,1}為0，{2}為1。,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.4 DFA的化簡(jiǎn),,,例2.31：對(duì)下圖的DFA M化簡(jiǎn)。,a,a,a,a,,b,b,a,,b,a,b,b,1,a,,6,4,3,,7,,5,,,,,,,,

59、,b,,2,,,b,,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.4 DFA的化簡(jiǎn),,,第一步，對(duì)M的狀態(tài)形成基本劃分?０，?０有兩個(gè)組q１ , q2，即 ?０=({1, 2, 3, 4} , { 5, 6, 7 })= ( q1,q2 ),第二步，對(duì)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、價(jià)的。,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ) 2.2.4 DFA的化簡(jiǎn),,,對(duì)q1進(jìn)行劃分，形成： q1=(q3, q4)=({1,2}，{3,4}),,由此，對(duì)基本劃分?0 經(jīng)考察后，形成新的劃分?1： ?1 =（q2，q3，q4） = ( {5,6,7}， {1,2}，{3,4}),Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ) 2.2 自動(dòng)機(jī)基礎(chǔ)

62、 2.2.4 DFA的化簡(jiǎn),,,第三步，考察?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是不等價(jià)的，形成q2的新的劃分： q2 =( q5, q6 )=（{5}，{6, 7}）,Ch2 形式語(yǔ)言自動(dòng)機(jī)理論基礎(chǔ)

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

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

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