自動機與形式語言_第三章_DFA_NFA

1、第第3章章 有窮狀態(tài)自動機有窮狀態(tài)自動機 主要內(nèi)容主要內(nèi)容 確定的有窮狀態(tài)自動機確定的有窮狀態(tài)自動機(DFA) 作為對實際問題的抽象、直觀物理模型、形式作為對實際問題的抽象、直觀物理模型、形式定義，定義，DFA接受的句子、語言，狀態(tài)轉(zhuǎn)移圖。接受的句子、語言，狀態(tài)轉(zhuǎn)移圖。 不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機(NFA) 定義；定義； NFA與與DFA的等價性；的等價性；2021-12-211第第3章章 有窮狀態(tài)自動機有窮狀態(tài)自動機 帶空移動的有窮狀態(tài)自動機帶空移動的有窮狀態(tài)自動機(-NFA) 定義。定義。 -NFA與與DFA的等價性。的等價性。 FA是正則語言的識別器是正則語言的識別器

2、正則文法正則文法(RG)與與FA的等價性。的等價性。 相互轉(zhuǎn)換方法。相互轉(zhuǎn)換方法。 帶輸出的有窮狀態(tài)自動機。帶輸出的有窮狀態(tài)自動機。 雙向有窮狀態(tài)自動機。雙向有窮狀態(tài)自動機。2021-12-212第第3章章 有窮狀態(tài)自動機有窮狀態(tài)自動機 重點：重點：DFA的概念，的概念，DFA、NFA、-NFA 、RG之間的等價轉(zhuǎn)換思路與方法。之間的等價轉(zhuǎn)換思路與方法。 難點：對難點：對DFA概念的理解，概念的理解，DFA、RG的構(gòu)的構(gòu)造方法，造方法， RG與與FA的等價性證明。的等價性證明。2021-12-213到目前為止，我們學(xué)了什么？到目前為止，我們學(xué)了什么？ 文法：語言的產(chǎn)生文法：語言的產(chǎn)生 RG,

3、CFG, CSG, PSG 對應(yīng)的語言：RL, CFL, CSL, PSL FA：語言的識別：語言的識別2021-12-214RGRE-NFA NFADFA 正則語言正則語言 (RL)3.1 語言的識別語言的識別 推導(dǎo)和歸約中的回溯問題將對系統(tǒng)的效率產(chǎn)推導(dǎo)和歸約中的回溯問題將對系統(tǒng)的效率產(chǎn)生極大的影響生極大的影響 SaA|aB AaA|c BaB|d分析句子分析句子aaac 的過程中可能需要回溯。的過程中可能需要回溯。2021-12-2153.1 語言的識別語言的識別 系統(tǒng)識別語言系統(tǒng)識別語言anc|n1and|n1的字符的字符串過程中狀態(tài)的變化圖示如下：串過程中狀態(tài)的變化圖示如下： 2021

4、-12-2163.1 語言的識別語言的識別 識別系統(tǒng)識別系統(tǒng)(模型模型) 系統(tǒng)具有有窮個狀態(tài)，不同的狀態(tài)代表系統(tǒng)具有有窮個狀態(tài)，不同的狀態(tài)代表不同的意義。按照實際的需要，系統(tǒng)可以不同的意義。按照實際的需要，系統(tǒng)可以在不同的狀態(tài)下完成規(guī)定的任務(wù)。在不同的狀態(tài)下完成規(guī)定的任務(wù)。 我們可以將輸入字符串中出現(xiàn)的字符匯我們可以將輸入字符串中出現(xiàn)的字符匯集在一起構(gòu)成一個字母表。系統(tǒng)處理的所集在一起構(gòu)成一個字母表。系統(tǒng)處理的所有字符串都是這個字母表上的字符串。有字符串都是這個字母表上的字符串。 2021-12-2173.1 語言的識別語言的識別 系統(tǒng)在任何一個狀態(tài)系統(tǒng)在任何一個狀態(tài)(當(dāng)前狀態(tài)當(dāng)前狀態(tài))下，從

5、下，從輸入字符串中讀入一個字符，根據(jù)當(dāng)前狀輸入字符串中讀入一個字符，根據(jù)當(dāng)前狀態(tài)和讀入的這個字符轉(zhuǎn)到新的狀態(tài)。當(dāng)前態(tài)和讀入的這個字符轉(zhuǎn)到新的狀態(tài)。當(dāng)前狀態(tài)和新的狀態(tài)可以是同一個狀態(tài)，也可狀態(tài)和新的狀態(tài)可以是同一個狀態(tài)，也可以是不同的狀態(tài)；當(dāng)系統(tǒng)從輸入字符串中以是不同的狀態(tài)；當(dāng)系統(tǒng)從輸入字符串中讀入一個字符后，它下一次再讀時，會讀讀入一個字符后，它下一次再讀時，會讀入下一個字符。這就是說，相當(dāng)于系統(tǒng)維入下一個字符。這就是說，相當(dāng)于系統(tǒng)維持有一個讀寫指針，該指針在系統(tǒng)讀入一持有一個讀寫指針，該指針在系統(tǒng)讀入一個字符后指向輸入串的下一個字符。個字符后指向輸入串的下一個字符。 2021-12-2183

6、.1 語言的識別語言的識別 系統(tǒng)中有一個狀態(tài)，它是系統(tǒng)的開始狀系統(tǒng)中有一個狀態(tài)，它是系統(tǒng)的開始狀態(tài)，系統(tǒng)在這個狀態(tài)下開始進行某個給定態(tài)，系統(tǒng)在這個狀態(tài)下開始進行某個給定句子的處理。句子的處理。 系統(tǒng)中還有一些狀態(tài)表示它到目前為止系統(tǒng)中還有一些狀態(tài)表示它到目前為止所讀入的字符構(gòu)成的字符串是語言的一個所讀入的字符構(gòu)成的字符串是語言的一個句子，把所有將系統(tǒng)從開始狀態(tài)引導(dǎo)到這句子，把所有將系統(tǒng)從開始狀態(tài)引導(dǎo)到這種狀態(tài)的字符串放在一起構(gòu)成一個語言，種狀態(tài)的字符串放在一起構(gòu)成一個語言，該語言就是系統(tǒng)所能識別的語言。該語言就是系統(tǒng)所能識別的語言。 2021-12-2193.1 語言的識別語言的識別 相應(yīng)的物

7、理模型相應(yīng)的物理模型一個右端無窮的輸入帶。一個右端無窮的輸入帶。一個有窮狀態(tài)控制器一個有窮狀態(tài)控制器(finite state control,FSC) 。一個讀頭。一個讀頭。 系統(tǒng)的每一個動作由三個節(jié)拍構(gòu)成：讀入系統(tǒng)的每一個動作由三個節(jié)拍構(gòu)成：讀入讀頭正注視的字符；根據(jù)當(dāng)前狀態(tài)和讀入讀頭正注視的字符；根據(jù)當(dāng)前狀態(tài)和讀入的字符改變有窮控制器的狀態(tài)；將讀頭向的字符改變有窮控制器的狀態(tài)；將讀頭向右移動一格。右移動一格。 2021-12-21103.1 語言的識別語言的識別 有窮狀態(tài)自動機的物理模型有窮狀態(tài)自動機的物理模型 2021-12-21113.2有窮狀態(tài)自動機有窮狀態(tài)自動機 有窮狀態(tài)自動機有

8、窮狀態(tài)自動機(finite automaton,FA) M=(Q，q0，F(xiàn))Q狀態(tài)的非空有窮集合。狀態(tài)的非空有窮集合。 qQ，q稱為稱為M的一個的一個狀態(tài)狀態(tài)(state)。輸入字母表輸入字母表(Input alphabet)。輸入字。輸入字符串都是符串都是上的字符串。上的字符串。 q0q0Q，是，是M的的開始狀態(tài)開始狀態(tài)(initial state)，也可叫做初始狀態(tài)或者啟動狀態(tài)。也可叫做初始狀態(tài)或者啟動狀態(tài)。2021-12-21123.2有窮狀態(tài)自動機有窮狀態(tài)自動機 狀態(tài)狀態(tài)轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)(transition function)，有時候又叫做狀態(tài)轉(zhuǎn)換函數(shù)或者移動函數(shù)。有時候又叫做狀態(tài)轉(zhuǎn)

9、換函數(shù)或者移動函數(shù)。：QQ，對，對 (q，a)Q，(q，a)=p表示：表示：M在狀態(tài)在狀態(tài)q讀入字符讀入字符a，將狀態(tài)，將狀態(tài)變成變成p，并將讀頭向右移動一個帶方格而指，并將讀頭向右移動一個帶方格而指向輸入字符串的下一個字符。向輸入字符串的下一個字符。FF Q，是，是M的的終止?fàn)顟B(tài)終止?fàn)顟B(tài)(final state)集集合。合。 qF，q稱為稱為M的的終止?fàn)顟B(tài)，終止?fàn)顟B(tài)，又稱為又稱為接受狀態(tài)接受狀態(tài)(accept state)。 2021-12-21133.2有窮狀態(tài)自動機有窮狀態(tài)自動機 例例 3-1 下面是一個有窮狀態(tài)自動機下面是一個有窮狀態(tài)自動機 M1=(q0，q1，q2，0，1，q0，q2

10、)其中，其中，1(q0,0)= q1，1(q1,0)= q2，1(q2,0)= q1 用表用表3-1表示表示1。狀態(tài)說明狀態(tài)說明狀態(tài)狀態(tài)輸入字符輸入字符0開始狀態(tài)開始狀態(tài)q0q1 q1q2終止?fàn)顟B(tài)終止?fàn)顟B(tài)q2q12021-12-21143.2有窮狀態(tài)自動機有窮狀態(tài)自動機 例例 3-1 下面是一個有窮狀態(tài)自動機下面是一個有窮狀態(tài)自動機 M1=(q0，q1，q2，0，1，q0，q2)其中，其中，1(q0,0)= q1，1(q1,0)= q2，1(q2,0)= q1 2021-12-21153.2有窮狀態(tài)自動機有窮狀態(tài)自動機 M2=(q0，q1，q2，q3，0，1，2，2，q0，q2)2(q0,0)

11、= q1，2(q1,0)= q22(q2,0)= q1，2(q3,0)= q32(q0,1)= q3，2(q1,1)= q32(q2,1)= q3，2(q3,1)= q32(q0,2)= q3，2(q1,2)= q32(q2,2)= q3，2(q3,2)= q3 2021-12-21163.2有窮狀態(tài)自動機有窮狀態(tài)自動機 狀態(tài)說明狀態(tài)說明狀態(tài)狀態(tài)輸入字符輸入字符012開始狀態(tài)開始狀態(tài)q0q1q3q3 q1q2q3q3終止?fàn)顟B(tài)終止?fàn)顟B(tài)q2q1q3q3 q3q3q3q3表表3-2 2轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù) 2021-12-21173.2有窮狀態(tài)自動機有窮狀態(tài)自動機 2021-12-21183.2有窮狀態(tài)

12、自動機有窮狀態(tài)自動機 將將擴充為擴充為QQ*:對任意的對任意的qQ，w*，a，定義，定義 ),(),()2(),() 1 (awqwaqqq2021-12-21193.2有窮狀態(tài)自動機有窮狀態(tài)自動機 ),(),(),(),(aqaqaqaq兩值相同，不用區(qū)分這兩個符號。兩值相同，不用區(qū)分這兩個符號。 2021-12-21203.2有窮狀態(tài)自動機有窮狀態(tài)自動機 確定的有窮狀態(tài)自動機確定的有窮狀態(tài)自動機 由于對于任意的由于對于任意的qQ， a，(q，a)均有均有確定的值，所以，將這種確定的值，所以，將這種FA稱為稱為確定的有窮狀確定的有窮狀態(tài)自動機態(tài)自動機(deterministic finite

13、 automaton，DFA) 2021-12-21213.2有窮狀態(tài)自動機有窮狀態(tài)自動機 M接受接受(識別識別)的語言的語言 對于對于 x*如果如果(q，w)F，則稱，則稱x被被M接受，接受，如果如果(q，w) F，則稱，則稱M不接受不接受x。L(M)=x| x*且且(q，w)F稱為由稱為由M接受接受(識別識別)的語言的語言 如果如果L(M1)=L(M2)，則稱，則稱M1與與M2等價。等價。 L(M1)= L(M2)=02n|n1 2021-12-2122M1M223S10ACB100,1101是下面是下面DFA語言中的字符串。語言中的字符串。從從A出發(fā)：出發(fā)：3.2有窮狀態(tài)自動機有窮狀態(tài)自

14、動機 例子: 識別語言中的串24101是下面是下面DFA語言中的字符串。語言中的字符串。跟隨標(biāo)記為跟隨標(biāo)記為1的弧的弧3.2有窮狀態(tài)自動機有窮狀態(tài)自動機 例子: 識別語言中的串Start10ACB100,125101是下面是下面DFA語言中的字符串。語言中的字符串。從從B出發(fā)，跟隨標(biāo)記為出發(fā)，跟隨標(biāo)記為0的弧的弧3.2有窮狀態(tài)自動機有窮狀態(tài)自動機 例子: 識別語言中的串Start10ACB100,126101是下面是下面DFA語言中的字符串。語言中的字符串。最后從最后從A出發(fā)，跟隨標(biāo)記為出發(fā)，跟隨標(biāo)記為1的弧，達(dá)到接的弧，達(dá)到接受狀態(tài)受狀態(tài)B，所以，所以101是該語言的字符串。是該語言的字符串

15、。3.2有窮狀態(tài)自動機有窮狀態(tài)自動機 例子: 識別語言中的串Start10ACB100,1273.2有窮狀態(tài)自動機有窮狀態(tài)自動機 該例子中DFA對應(yīng)的語言為：w | w 0,1* 且 w 不包含連續(xù)的兩個1。S10ACB100,128 等價性證明 我們經(jīng)常需要證明兩個集合等價 這里，一個集合是 “該DFA接收的語言” 另一個集合是 “w | w 0,1* 且 w 不包含連續(xù)的兩個1”3.2有窮狀態(tài)自動機有窮狀態(tài)自動機 S10ACB100,129證明集合S=T, 需要證明: S T and T S:如果w在集合S中, 那么w在集合T中；如果w在集合T中, 那么w在集合S中。1. 設(shè)S = “該D

16、FA接收的語言”, T = “不包含連續(xù)的1”3.2有窮狀態(tài)自動機有窮狀態(tài)自動機 S10ACB100,130 Part 1: S T 證明: if w 被該DFA接受，那么w 不包含連續(xù)的1. 按照w的長度歸納證明。3.2有窮狀態(tài)自動機有窮狀態(tài)自動機 S10ACB100,131歸納假設(shè)：歸納假設(shè)： 如果(A, w) = A, 那么w 沒有連續(xù)的1并且不以1結(jié)尾. 如果(A, w) = B, 那么w 沒有連續(xù)的1并且以單個1結(jié)尾.Basis: |w| = 0; i.e., w = .(1) 成立，因為 未有任何元素1. (2) 成立，因為 (A, ) 不等同于B3.2有窮狀態(tài)自動機有窮狀態(tài)自動機

17、 S10ACB100,1歸納步驟歸納步驟132 假設(shè)|x| 長度為n，且(1)和(2)對于x成立 證明w = xa, |w|=n+1時(1)和(2)成立3.2有窮狀態(tài)自動機有窮狀態(tài)自動機 S10ACB100,1歸納步驟歸納步驟233 (1) 如果(A, w) = A。因為w = xa，由DFA可知，(A, x) 必須是A或者B, a必須是0. 根據(jù)歸納假設(shè), x不包含11. 因此w不包含11，也不以1結(jié)尾，假設(shè)（1）對w成立。S10ACB100,13.2有窮狀態(tài)自動機有窮狀態(tài)自動機 歸納步驟歸納步驟234 (2)如果(A, w) = B。因為w = xa，由DFA可知，(A, x) 必須是A,

18、 a必須是1。 根據(jù)歸納假設(shè), x不包含11并且不以1結(jié)尾。 因此，w沒有連續(xù)的1并且以單個1結(jié)尾，歸納假設(shè)（2）對w成立.3.2有窮狀態(tài)自動機有窮狀態(tài)自動機 S10ACB100,1歸納步驟歸納步驟235 Part 2: S T 下面我們需要證明, 如果w不包含連續(xù)的1, 那么w被該DFA接受。 換言之: 如果w不被該DFA接受，則w一定包含連續(xù)的1“if X then Y”=“if not Y then not X.”3.2有窮狀態(tài)自動機有窮狀態(tài)自動機 S10ACB100,136 w不被DFA接收的充要條件是(A, w) = C. 因此, w = x1y, x引導(dǎo)DFA到B, 1引導(dǎo)DFA到

19、C,y是到達(dá)C以后產(chǎn)生的后綴。 如果(A,x) = B，根據(jù)之前的證明，x以單個1結(jié)尾，因此x = z1（z為不包含11的前綴） 因此, w = z11y，包含連續(xù)的1, 得證。3.2有窮狀態(tài)自動機有窮狀態(tài)自動機 S10ACB100,13.2有窮狀態(tài)自動機有窮狀態(tài)自動機 例例 3-2 構(gòu)造一個構(gòu)造一個DFA，它接受的語言為，它接受的語言為x000y|x，y0，1*q0M的啟動狀態(tài)；的啟動狀態(tài)；q1M讀到了一個讀到了一個0，這個，這個0可能是子串可能是子串“000”的的第第1個個0；q2M在在q1后緊接著又讀到了一個后緊接著又讀到了一個0，這個，這個0可能可能是子串是子串“000”的第的第2個個

20、0；q3M在在q2后緊接著又讀到了一個后緊接著又讀到了一個0，發(fā)現(xiàn)輸入字，發(fā)現(xiàn)輸入字符串含有子串符串含有子串“000”；因此，這個狀態(tài)應(yīng)該是終；因此，這個狀態(tài)應(yīng)該是終止?fàn)顟B(tài)。止?fàn)顟B(tài)。2021-12-21373.2有窮狀態(tài)自動機有窮狀態(tài)自動機 (q0,1)= q0M在在q0讀到了一個讀到了一個1，它需要，它需要繼續(xù)在繼續(xù)在q0 “等待等待”可能是子串可能是子串“000”的第的第1個個0的輸入字符的輸入字符0；(q1,1)= q0M在剛剛讀到了一個在剛剛讀到了一個0后，讀后，讀到了一個到了一個1，表明在讀入這個，表明在讀入這個1之前所讀入之前所讀入的的0并不是子串并不是子串“000”的第的第1個個

21、0，因此，因此，M需要重新回到狀態(tài)需要重新回到狀態(tài)q0，以尋找子串，以尋找子串“000”的的第第1個個0；2021-12-21383.2有窮狀態(tài)自動機有窮狀態(tài)自動機 (q2,1)= q0M在剛剛發(fā)現(xiàn)了在剛剛發(fā)現(xiàn)了00后，讀到了后，讀到了一個一個1，表明在讀入這個，表明在讀入這個1之前所讀入的之前所讀入的00并并不是子串不是子串“000”的前兩個的前兩個0，因此，因此，M需要重需要重新回到狀態(tài)新回到狀態(tài)q0，以尋找子串，以尋找子串“000”的第的第1個個0；(q3,0)= q3M找到了子串找到了子串“000”，只用讀，只用讀入該串的剩余部分。入該串的剩余部分。(q3,1)= q3M找到了子串找到

22、了子串“000”，只用讀，只用讀入該串的剩余部分。入該串的剩余部分。2021-12-21393.2有窮狀態(tài)自動機有窮狀態(tài)自動機 M=(q0，q1，q2，q3，0，1， (q0,0)= q1，(q1,0)= q2，(q2,0)= q3，(q0,1)= q0，(q1,1)= q0，(q2,1)= q0，(q3,0)= q3，(q3,1)= q3，q0，q3) 狀態(tài)說明狀態(tài)說明狀態(tài)狀態(tài)輸入字符輸入字符01開始狀態(tài)開始狀態(tài)q0q1q0 q1q2q0 q2q3q0終止?fàn)顟B(tài)終止?fàn)顟B(tài)q3q3q32021-12-21403.2有窮狀態(tài)自動機有窮狀態(tài)自動機 一種更為直觀的表示一種更為直觀的表示2021-12-2

23、1413.2有窮狀態(tài)自動機有窮狀態(tài)自動機 例例 3-3構(gòu)造一個構(gòu)造一個DFA，它接受的語言為，它接受的語言為x000|x0，1*。 狀態(tài)狀態(tài)q0讀到的讀到的0可能是輸入字符串的最后三個可能是輸入字符串的最后三個0的第的第1個個0； 在狀態(tài)在狀態(tài)q1緊接著讀到的緊接著讀到的0可能是輸入字符串的最可能是輸入字符串的最后三個后三個0的第的第2個個0； 在狀態(tài)在狀態(tài)q2緊接著讀到的緊接著讀到的0可能是輸入字符串的最可能是輸入字符串的最后三個后三個0的第的第3個個0；2021-12-21423.2有窮狀態(tài)自動機有窮狀態(tài)自動機 在狀態(tài)在狀態(tài)q3緊接著讀到的緊接著讀到的0也可能是輸入字符串的也可能是輸入字符

24、串的最后三個最后三個0的第的第3個個0； 如果在狀態(tài)如果在狀態(tài)q1，q2，q3讀到的是讀到的是1，則要重新檢，則要重新檢查輸入串是否以三個查輸入串是否以三個0結(jié)尾。結(jié)尾。 2021-12-21433.2有窮狀態(tài)自動機有窮狀態(tài)自動機 幾點值得注意幾點值得注意 定義定義FA時，常常只給出時，常常只給出FA相應(yīng)的狀態(tài)轉(zhuǎn)相應(yīng)的狀態(tài)轉(zhuǎn)移圖就可以了。移圖就可以了。 對于對于DFA來說，并行的弧按其上的標(biāo)記字來說，并行的弧按其上的標(biāo)記字符的個數(shù)計算，對于每個頂點來說，它的符的個數(shù)計算，對于每個頂點來說，它的出度恰好等于輸入字母表中所含的字符的出度恰好等于輸入字母表中所含的字符的個數(shù)。個數(shù)。 2021-12-

25、21443.2有窮狀態(tài)自動機有窮狀態(tài)自動機 不難看出，字符串不難看出，字符串x被被FA M接受的充分必接受的充分必要條件是，在要條件是，在M的狀態(tài)轉(zhuǎn)移圖中存在一條的狀態(tài)轉(zhuǎn)移圖中存在一條從開始狀態(tài)到某一個終止?fàn)顟B(tài)的有向路，從開始狀態(tài)到某一個終止?fàn)顟B(tài)的有向路，該有向路上從第該有向路上從第1條邊到最后一條邊的標(biāo)記條邊到最后一條邊的標(biāo)記依次并置而構(gòu)成的字符串依次并置而構(gòu)成的字符串x。簡稱此路的標(biāo)。簡稱此路的標(biāo)記為記為x。 一個一個FA可以有多于可以有多于1個的終止?fàn)顟B(tài)。個的終止?fàn)顟B(tài)。 2021-12-21453.2有窮狀態(tài)自動機有窮狀態(tài)自動機 例例 3-4 構(gòu)造一個構(gòu)造一個DFA，它接受的語言，它接受

26、的語言為為0n1m2k|n,m,k1。 q0M的啟動狀態(tài)；的啟動狀態(tài)；q1M讀到至少一個讀到至少一個0，并等待讀更多的，并等待讀更多的0；q2M讀到至少一個讀到至少一個0后，讀到了至少一個后，讀到了至少一個1，并等待讀更多的，并等待讀更多的1；q3M讀到至少一個讀到至少一個0后跟至少一個后跟至少一個1后，后，并且接著讀到了至少一個并且接著讀到了至少一個2。 2021-12-21463.2有窮狀態(tài)自動機有窮狀態(tài)自動機 先設(shè)計先設(shè)計“主體框架主體框架”再補充細(xì)節(jié)再補充細(xì)節(jié)2021-12-2147 3.2有窮狀態(tài)自動機有窮狀態(tài)自動機 當(dāng)當(dāng)FA一旦進入狀態(tài)一旦進入狀態(tài)qt，它就無法離開此狀，它就無法離

27、開此狀態(tài)。所以，態(tài)。所以，qt相當(dāng)于一個陷阱狀態(tài)相當(dāng)于一個陷阱狀態(tài)(trap)。一般地，我們將陷阱狀態(tài)用作在其他狀態(tài)一般地，我們將陷阱狀態(tài)用作在其他狀態(tài)下發(fā)現(xiàn)輸入串不可能是該下發(fā)現(xiàn)輸入串不可能是該FA所識別的語言所識別的語言的句子時進入的狀態(tài)。在此狀態(tài)下，的句子時進入的狀態(tài)。在此狀態(tài)下，F(xiàn)A讀讀完輸入串中剩余的字符。完輸入串中剩余的字符。 2021-12-21483.2有窮狀態(tài)自動機有窮狀態(tài)自動機 在構(gòu)造一個識別給定語言的在構(gòu)造一個識別給定語言的FA時，用畫時，用畫圖的方式比較方便、直觀。我們可以先根圖的方式比較方便、直觀。我們可以先根據(jù)語言的主要特征畫出該據(jù)語言的主要特征畫出該FA的的“主體

28、框主體框架架”，然后再去考慮畫出一些細(xì)節(jié)要求的，然后再去考慮畫出一些細(xì)節(jié)要求的內(nèi)容。內(nèi)容。2021-12-21493.2有窮狀態(tài)自動機有窮狀態(tài)自動機 FA的狀態(tài)具有一定的記憶功能：不同的狀的狀態(tài)具有一定的記憶功能：不同的狀態(tài)對應(yīng)于不同的情況，由于態(tài)對應(yīng)于不同的情況，由于FA只有有窮個只有有窮個狀態(tài)，所以，在識別一個語言的過程中，狀態(tài)，所以，在識別一個語言的過程中，如果有無窮種情況需要記憶，我們肯定是如果有無窮種情況需要記憶，我們肯定是無法構(gòu)造出相應(yīng)的無法構(gòu)造出相應(yīng)的FA的。的。 2021-12-21503.2有窮狀態(tài)自動機有窮狀態(tài)自動機 例例 3-5構(gòu)造一個構(gòu)造一個DFA，它接受的語言，它接受

29、的語言為為x|x0，1*，且當(dāng)把，且當(dāng)把x看成二進制看成二進制數(shù)時，數(shù)時，x模模3與與0同余同余。 q0對應(yīng)除以對應(yīng)除以3余數(shù)為余數(shù)為0的的x組成的等價類；組成的等價類； q1對應(yīng)除以對應(yīng)除以3余數(shù)為余數(shù)為1的的x組成的等價類；組成的等價類； q2對應(yīng)除以對應(yīng)除以3余數(shù)為余數(shù)為2的的x組成的等價類；組成的等價類； qsM的開始狀態(tài)。的開始狀態(tài)。2021-12-21513.2有窮狀態(tài)自動機有窮狀態(tài)自動機 qs在此狀態(tài)下讀入在此狀態(tài)下讀入0時，有時，有x=0，所以應(yīng)，所以應(yīng)該進入狀態(tài)該進入狀態(tài)q0；讀入；讀入1時，有時，有x=1，所以應(yīng)，所以應(yīng)該進入狀態(tài)該進入狀態(tài)q1。即：。即：(qs，0)= q

30、0；(qs，1)= q1 。2021-12-21523.2有窮狀態(tài)自動機有窮狀態(tài)自動機 q0能引導(dǎo)能引導(dǎo)M到達(dá)此狀態(tài)的到達(dá)此狀態(tài)的x除以除以3余余0，所以有：所以有：x=3*n+0。 讀入讀入0時，引導(dǎo)時，引導(dǎo)M到達(dá)下一個狀態(tài)的字符串到達(dá)下一個狀態(tài)的字符串為為x0，x0=2*(3*n+0)=3*2*n+0。所以，。所以，(q0，0)= q0； 讀入讀入1時，時，M到達(dá)下一個狀態(tài)的字符串為到達(dá)下一個狀態(tài)的字符串為x1，x1=2*(3*n+0)+1=3*2*n+1。所以，。所以，(q0，1)= q1；2021-12-21533.2有窮狀態(tài)自動機有窮狀態(tài)自動機 q1能引導(dǎo)能引導(dǎo)M到達(dá)此狀態(tài)的到達(dá)此狀

31、態(tài)的x除以除以3余余1，所以有：所以有：x=3*n+1。 讀入讀入0時，引導(dǎo)時，引導(dǎo)M到達(dá)下一個狀態(tài)的字符串到達(dá)下一個狀態(tài)的字符串為為x0，x0=2*(3*n+1)=3*2*n+2。所以即：。所以即：(q1，0)= q2； 讀入讀入1時，引導(dǎo)時，引導(dǎo)M到達(dá)下一個狀態(tài)的字符串到達(dá)下一個狀態(tài)的字符串為為x1，x1=2*(3*n+1)+1=3*2*n+2+1=3*(2*n+1)。所以所以(q1，1)= q0 2021-12-21543.2有窮狀態(tài)自動機有窮狀態(tài)自動機 q2能引導(dǎo)能引導(dǎo)M到達(dá)此狀態(tài)的到達(dá)此狀態(tài)的x除以除以3余余2，所以：，所以：x=3*n+2。 讀入讀入0時，引導(dǎo)時，引導(dǎo)M到達(dá)下一個狀

32、態(tài)的字符串為到達(dá)下一個狀態(tài)的字符串為x0，x0=2*(3*n+2)=3*2*n+4=3*(2*n+1)+1。所以。所以(q2，0)= q1； 讀入讀入1時，引導(dǎo)時，引導(dǎo)M到達(dá)下一個狀態(tài)的字符串為到達(dá)下一個狀態(tài)的字符串為x1，x1=2*(3*n+2)+1=3*2*n+4+1=3*(2*n+1)+2。所以，。所以，(q2，1)= q2 。2021-12-21553.2有窮狀態(tài)自動機有窮狀態(tài)自動機 接受語言接受語言x|x0，1*，且當(dāng)把，且當(dāng)把x看成二進看成二進制數(shù)時，制數(shù)時，x模模3與與0同余同余的的DFA如下：如下： 2021-12-21563.2有窮狀態(tài)自動機有窮狀態(tài)自動機 例例 3-6 構(gòu)造

33、一個構(gòu)造一個DFA，它接受的語言，它接受的語言L=x|x0，1*，且對，且對x中任意一個中任意一個長度不大于長度不大于5的子串的子串a(chǎn)1a2an，a1+a2+an3，n5 。 輸入串為輸入串為 a1a2aiai+4ai+5am2021-12-21573.2有窮狀態(tài)自動機有窮狀態(tài)自動機 當(dāng)當(dāng)i=1，2，3，也就是，也就是M讀到輸入串的第讀到輸入串的第1、2、3個字符時，它需要將這些字符記下來。個字符時，它需要將這些字符記下來。因為因為a1ai可能需要用來判定輸入串的最可能需要用來判定輸入串的最初初45個字符組成的子串是否滿足語言的要個字符組成的子串是否滿足語言的要求。求。 當(dāng)當(dāng)i=4，5，也就是

34、，也就是M讀到輸入串的第讀到輸入串的第4、5個個字符時，在字符時，在a1+a2+ai3的情況下，的情況下，M需要將需要將a1ai記下來；在記下來；在a1+a2+ai3時，時，M應(yīng)該進入陷阱狀態(tài)應(yīng)該進入陷阱狀態(tài)qt。 2021-12-21583.2有窮狀態(tài)自動機有窮狀態(tài)自動機 當(dāng)當(dāng)i=6，也就是，也就是M讀到輸入串的第讀到輸入串的第6個字符，個字符，此時，以前讀到的第此時，以前讀到的第1個字符個字符a1就沒有用了，就沒有用了，此時它要看此時它要看a2+a3+a63是否成立，如果是否成立，如果成立，成立，M需要將需要將a2a6記下來；在記下來；在a2+a3+ai3時，時，M應(yīng)該進入陷阱狀態(tài)應(yīng)該進入

35、陷阱狀態(tài)qt。 2021-12-21593.2有窮狀態(tài)自動機有窮狀態(tài)自動機 當(dāng)當(dāng)M完成對子串完成對子串a(chǎn)1a2aiai+4的考察，并發(fā)的考察，并發(fā)現(xiàn)它滿足語言的要求時，現(xiàn)它滿足語言的要求時，M記下來的是記下來的是aiai+4，此時它讀入輸入串的第，此時它讀入輸入串的第i+5個字符個字符ai+5，以前讀到的第，以前讀到的第i個字符個字符ai就沒有用了，就沒有用了，此時它要看此時它要看ai+1+ai+2+ai+53是否成立，是否成立，如果成立，如果成立，M需要將需要將ai+1，ai+2，ai+5記下記下來；在來；在ai+1+ai+2+ai+53時，時，M應(yīng)該進入陷應(yīng)該進入陷阱狀態(tài)阱狀態(tài)qt。 20

36、21-12-21603.2有窮狀態(tài)自動機有窮狀態(tài)自動機 M需要記憶的內(nèi)容有：需要記憶的內(nèi)容有： 什么都未讀入什么都未讀入20=1種；種； 記錄有記錄有1個字符個字符21=2種；種； 記錄有記錄有2個字符個字符22=4種；種； 記錄有記錄有3個字符個字符23=8種；種； 記錄有記錄有4個字符個字符24-1=15種；種； 記錄有記錄有5個字符個字符25-6=26種；種； 記錄當(dāng)前的輸入串不是句子記錄當(dāng)前的輸入串不是句子1種。種。 2021-12-21613.2有窮狀態(tài)自動機有窮狀態(tài)自動機狀態(tài)設(shè)置狀態(tài)設(shè)置qM還未讀入任何字符；還未讀入任何字符；qt陷阱狀態(tài)；陷阱狀態(tài)；qa1a2aiM記錄有記錄有i個

37、字符，個字符，1i5。a1，a2，ai0，1。取取DFA M=(Q，0，1，q，F(xiàn))F= q qa1a2ai| a1，a2，ai0，1且且1i5且且a1+a2+ai3Q=qt F 2021-12-21623.2有窮狀態(tài)自動機有窮狀態(tài)自動機 (q，a1)=qa1 (qa1，a2)=qa1a2 (qa1a2，a3)=qa1a2a3 qa1a2a3a如果a1+a2+a3+a3(qa1a2a3，a)= qt如果a1+a2+a3+a3 2021-12-21633.2有窮狀態(tài)自動機有窮狀態(tài)自動機 qa1a2a3a4a 如果a1+a2+a3+a4+a3(qa1a2a3a4，a)= qt如果a1+a2+a3+

38、a4+a3qa2a3a4a5a a2+a3+a4+ a5+a3(qa1a2a3a4a5，a)=qt如果a2+a3+a4+ a5+a3(qt，a1)=qt2021-12-21643.2有窮狀態(tài)自動機有窮狀態(tài)自動機 接受語言接受語言x000|x0，1*x001|x0，1*的的FA 2021-12-21653.2有窮狀態(tài)自動機有窮狀態(tài)自動機 能引導(dǎo)能引導(dǎo)FA從開始狀態(tài)到達(dá)從開始狀態(tài)到達(dá)q的字符串的集合為：的字符串的集合為：set(q)=x | x*，(q0，x)=q對圖對圖3-5所給的所給的DFA 中的所有中的所有q，求，求set(q)。2021-12-2166set(q0)=x | x*，x=或者

39、或者x以以1但不是但不是001結(jié)尾結(jié)尾set(q1)=x | x*，x=0或者或者x以以10結(jié)尾結(jié)尾set(q2)=x | x*，x=00或者或者x以以100結(jié)尾結(jié)尾set(q3)=x | x*，x以以000結(jié)尾結(jié)尾set(q4)=x | x*， x以以001結(jié)尾結(jié)尾這這5個集合是兩兩互不相交。個集合是兩兩互不相交。 2021-12-21673.2有窮狀態(tài)自動機有窮狀態(tài)自動機 對于任意一個對于任意一個FA M=(Q，q0，F(xiàn))我們可以按照如下方式定義關(guān)系我們可以按照如下方式定義關(guān)系RM： 對對 x，y*，xRMy qQ，使得，使得xset(q)和和yset(q)同時成立。同時成立。 按照這個定

40、義所得到的關(guān)系實際上是按照這個定義所得到的關(guān)系實際上是*上上的一個等價關(guān)系。利用這個關(guān)系，可以將的一個等價關(guān)系。利用這個關(guān)系，可以將*劃分成不多于劃分成不多于|Q|個等價類。個等價類。 2021-12-21683.2有窮狀態(tài)自動機有窮狀態(tài)自動機 即時描述即時描述(instantaneous description，ID ） x，y*，(q0，x)=q, xqy稱為稱為M的一個的一個即即時描述，時描述，表示表示xy是是M正在處理的一個字符串，正在處理的一個字符串，x引導(dǎo)引導(dǎo)M從從q0啟動并到達(dá)狀態(tài)啟動并到達(dá)狀態(tài)q，M當(dāng)前正注視當(dāng)前正注視著著y的首字符。的首字符。 如果如果xqay是是M的一個即時

41、描述，且的一個即時描述，且(q，a)=p，則則xqay M xapy。 2021-12-21693.2有窮狀態(tài)自動機有窮狀態(tài)自動機 Mn ：表示：表示M從即時描述從即時描述經(jīng)過經(jīng)過n次移動到次移動到達(dá)即時描述達(dá)即時描述。 M存在即時描述存在即時描述1，2，n-1，使得，使得 M 1，1M 2，n-1M 當(dāng)當(dāng)n=0n=0時，有時，有=。即。即M M 0 0 。 M M + + ：表示：表示M M從即時描述從即時描述經(jīng)過至少經(jīng)過至少1 1次移動到次移動到達(dá)即時描述達(dá)即時描述。 M M * * ：表示：表示M M從即時描述從即時描述經(jīng)過若干步移動經(jīng)過若干步移動到達(dá)即時描述到達(dá)即時描述。 2021-1

42、2-21703.2有窮狀態(tài)自動機有窮狀態(tài)自動機 當(dāng)意義清楚時，我們將符號當(dāng)意義清楚時，我們將符號M、Mn、M*、M+中的中的M省去，分別用省去，分別用、n、*、+表示。表示。 2021-12-21713.2有窮狀態(tài)自動機有窮狀態(tài)自動機 對下圖所示的對下圖所示的DFA有如下的有如下的ID轉(zhuǎn)換：轉(zhuǎn)換：2021-12-21723.2有窮狀態(tài)自動機有窮狀態(tài)自動機 q01010010001 1q0010010001 10q110010001 101q00010001 1010q1010001 10100q210001 101001q00001 1010010q1001 10100100q201 2021

43、-12-21733.2有窮狀態(tài)自動機有窮狀態(tài)自動機 101001000q31 1010010001q0即 q0101001000110 1010010001q0 q01010010001+ 1010010001q0 q01010010001* 1010010001q0 2021-12-21743.2有窮狀態(tài)自動機有窮狀態(tài)自動機 對于x*, q0 x1+ x1q0 q0 x10+ x10q1 q0 x100+ x100q2 q0 x000+ x000q3 2021-12-21753.3 NFA 3.3.1 作為對作為對DFA的修改的修改 希望是接受希望是接受x|x0，1*，且，且x含有子串含有子

44、串00或或11的的FA如下：如下：2021-12-21763.3.1 作為對作為對DFA的修改的修改 希望是接受希望是接受x|x0，1*，且，且x 的倒數(shù)第的倒數(shù)第10個字符為個字符為1的的FA如下如下 ：2021-12-21773.3.1 作為對作為對DFA的修改的修改 這兩個圖所給的這兩個圖所給的“FA”與前面我們所定義與前面我們所定義的的FA，即，即DFA，的區(qū)別在于：，的區(qū)別在于： 并不是對于所有的并不是對于所有的(q，a)Q,(q，a)都有一個狀態(tài)與它對應(yīng)；都有一個狀態(tài)與它對應(yīng)； 并不是對于所有的并不是對于所有的(q，a)Q,(q，a)只對應(yīng)一個狀態(tài)。只對應(yīng)一個狀態(tài)。 “FA”在任意

45、時刻可以處于有窮多個狀態(tài)。在任意時刻可以處于有窮多個狀態(tài)。 “FA”具有具有“智能智能”。2021-12-21783.3.2 NFA的形式定義的形式定義 不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機(non-deterministic finite automaton ,NFA) M是一個五元組是一個五元組M=(Q，q0，F(xiàn)) Q、q0、F的意義同的意義同DFA。 ：Q2Q，對，對 (q，a)Q，(q，a)= p1，p2，pm表示表示M在狀態(tài)在狀態(tài)q讀入字符讀入字符a，可，可以選擇地將狀態(tài)變成以選擇地將狀態(tài)變成p1、或者、或者p2、或者、或者pm ，并將讀頭向右移動一個帶方格而指向輸入字符并將

46、讀頭向右移動一個帶方格而指向輸入字符串的下一個字符。串的下一個字符。 2021-12-21793.3.2 NFA的形式定義的形式定義 FA的狀態(tài)轉(zhuǎn)移圖、的狀態(tài)轉(zhuǎn)移圖、FA的狀態(tài)對應(yīng)的等價類、的狀態(tài)對應(yīng)的等價類、FA的即時描述對的即時描述對NFA都有效。都有效。 接受接受x|x0，1*，且，且x含有子串含有子串00或或11的的FA對應(yīng)的移動函數(shù)定義表。對應(yīng)的移動函數(shù)定義表。2021-12-21803.3.2 NFA的形式定義的形式定義 狀態(tài)說明狀態(tài)說明狀態(tài)狀態(tài)輸入字符輸入字符01啟動狀態(tài)啟動狀態(tài)q0q0，q1 q0，q2 q1q3 q2q3終止?fàn)顟B(tài)終止?fàn)顟B(tài)q3q3q32021-12-21813.

47、3.2 NFA的形式定義的形式定義 接受接受x|x0，1*，且，且x 的倒數(shù)第的倒數(shù)第10個字符個字符為為1的的FA對應(yīng)的移動函數(shù)定義表。對應(yīng)的移動函數(shù)定義表。2021-12-21823.3.2 NFA的形式定義的形式定義 狀態(tài)說明狀態(tài)說明狀態(tài)狀態(tài)輸入字符輸入字符01啟動狀態(tài)啟動狀態(tài)q0q0 q0，q1 q1q2q2 q2q3q3 q3q4q4 q4q5q5 q5q6q6 q6q7q7 q7q8q8 q8q9 q9 q9q10 q10終止?fàn)顟B(tài)終止?fàn)顟B(tài)q102021-12-21833.3.2 NFA的形式定義的形式定義 將將擴充為擴充為QQ2:*對任意的對任意的qQ，w*，a，定義，定義 a)，

48、(rp，使得w)，(q r|p),()2(),()1 (waqqq2021-12-21843.3.2 NFA的形式定義的形式定義 M接受接受(識別識別)的語言的語言 對于對于 x*，如果如果(q0，w) F，則稱則稱x被被M接受，如果接受，如果(q0，w)F=，則稱則稱M不接受不接受x。L(M)=x| x*且且(q0，w) F，稱為由稱為由M接受接受(識別識別)的語言。的語言。 2021-12-218586DFA例子: Chessboard1257934861rbb42153751397 r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5

49、,94,8 54,6 5,7,916,8 5包含了終止?fàn)顟B(tài)，接收啟動狀態(tài)啟動狀態(tài)終止?fàn)顟B(tài)終止?fàn)顟B(tài)873.3.3 NFA與與DFA等價等價 任意任意DFA可以轉(zhuǎn)換成接收相同語言的可以轉(zhuǎn)換成接收相同語言的NFA。 如果DFA中有D(q, a) = p, 在NFA中使得 N(q, a) = p. 那么NFA總與DFA讀取輸入后處于相同的狀態(tài)。 DFANFA88 類似的，對于任意NFA，可以找到一個對應(yīng)的DFA接收相同的語言。 證明方法：子集構(gòu)造（subset construction）。3.3.3 NFA與與DFA等價等價 NFADFA3.3.3 NFA與與DFA等價等價 對于一個輸入字符，對于一個

50、輸入字符，NFA與與DFA的差異是的差異是前者可以進入若干個狀態(tài)，而后者只能進前者可以進入若干個狀態(tài)，而后者只能進入一個惟一的狀態(tài)。雖然從入一個惟一的狀態(tài)。雖然從DFA看待問題看待問題的角度來說，的角度來說，NFA在某一時刻同時進入若在某一時刻同時進入若干個狀態(tài)，但是，這若干個狀態(tài)合在一起干個狀態(tài)，但是，這若干個狀態(tài)合在一起的的“總效果總效果”相當(dāng)于它處于這些狀態(tài)對應(yīng)相當(dāng)于它處于這些狀態(tài)對應(yīng)的一個的一個“綜合狀態(tài)綜合狀態(tài)”。因此，我們考慮讓。因此，我們考慮讓DFA用一個狀態(tài)去對應(yīng)用一個狀態(tài)去對應(yīng)NFA的一組狀態(tài)。的一組狀態(tài)。 2021-12-21892021-12-2190狀態(tài)說明狀態(tài)說明狀態(tài)

51、狀態(tài)輸入字符輸入字符01啟動狀態(tài)啟動狀態(tài)q0q0，q1 q0，q2 q1q3 q2q3終止?fàn)顟B(tài)終止?fàn)顟B(tài)q3q3q33.3.3 NFA與與DFA等價等價 q0，q1q0，q2q03.3.3 NFA與與DFA等價等價 NFA M1=(Q，1，q0，F(xiàn)1)與與DFA M2=(Q2，2，q0，F(xiàn)2)的對應(yīng)關(guān)系：的對應(yīng)關(guān)系： NFA從開始狀態(tài)從開始狀態(tài)q0啟動，我們就讓相應(yīng)的啟動，我們就讓相應(yīng)的DFA從狀態(tài)從狀態(tài)q0啟動。所以啟動。所以q0= q0。 對于對于NFA 的一個狀態(tài)組的一個狀態(tài)組q1，q2，qn，如，如果果NFA在此狀態(tài)組時在此狀態(tài)組時讀入字符讀入字符a后可以后可以進入狀進入狀態(tài)組態(tài)組p1，

52、p2，pm,則讓相應(yīng)的則讓相應(yīng)的DFA在狀態(tài)在狀態(tài)q1，q2，qn讀入字符讀入字符a時，時，進入狀態(tài)進入狀態(tài)p1，p2，pm。 2021-12-21911=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm 92子集構(gòu)造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*r b12,4 51=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p

53、2，pm 93子集構(gòu)造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*r b12,4 52,451=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm 94子集構(gòu)造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*1=(=(q1，q2，qn,a)

54、=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm r b12,4,6,852,42,4,6,8 1,3,5,71,3,5,72,4 595子集構(gòu)造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*1=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm r b1 * 1,3,7,92,4,6,82,4,6,8 1,3,7,952,42,4,6,8 1,3,5,

55、71,3,5,72,4 596子集構(gòu)造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*1=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm r b1 * 1,3,5,7,9 * 1,3,7,92,4,6,8 1,3,5,7,92,4,6,82,4,6,8 1,3,7,952,42,4,6,8 1,3,5,71,3,5,72,4 597子集構(gòu)造: Subset Construction r

56、 b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*1=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm r b1 * 1,3,5,7,9 * 1,3,7,92,4,6,8 1,3,5,7,92,4,6,82,4,6,8 1,3,7,952,42,4,6,8 1,3,5,71,3,5,72,4 52,4,6,8 1,3,5,7,998子集構(gòu)造: Subset Construction r b2,4 54,6 1,3,52,6 52,8

57、1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*1=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm r b1 * 1,3,5,7,9 * 1,3,7,92,4,6,8 52,4,6,8 1,3,5,7,92,4,6,82,4,6,8 1,3,7,952,42,4,6,8 1,3,5,71,3,5,72,4 52,4,6,8 1,3,5,7,999Example: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8

58、1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*r b1 * 1,3,5,7,92,4,6,8 1,3,5,7,9 * 1,3,7,92,4,6,8 52,4,6,8 1,3,5,7,92,4,6,82,4,6,8 1,3,7,952,42,4,6,8 1,3,5,71,3,5,72,4 52,4,6,8 1,3,5,7,91=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm 3.3.3 NFA與與DFA等價等價 定理定理 3-1 NFA與與DFA等價。等價。證明：證明：構(gòu)造與構(gòu)造與M1等價的等價的DFA M2 。 M1=(Q，1，q0，F(xiàn)1) M2=(Q2，2，q0，F(xiàn)2) Q2=2Q F2=p1，p2，pm|p1，p2，pm Q&p1，p2，pmF1 2021-12-211003.3.3 NFA與與DFA等價等價 2(q1，q2，qn，a)=p1，p2，pm1(q1，q2，qn，a)= p1，p2，pm (2) 證明證明1(q0，x)= p1，p2，pm 2(q0，x)=p1，p2，pm。 設(shè)設(shè)x*，施歸納于，施歸納于|x| x=，1(q0，)= q0,2(q0，)