第03章 有窮狀態(tài)自動機-16、17、18節(jié)課-2013-10-15

1、圖圖3-5接受語言接受語言x000| x 0, 1* x001| x 0, 1*的的DFASq00q11q2q310001q4101定義定義3-6n設(shè)設(shè)M = (Q, , , q0, F)為一個為一個FA，對，對 q Q，能引導(dǎo)，能引導(dǎo)FA從開始狀態(tài)從開始狀態(tài)q0 到達到達q的字符串的集合為的字符串的集合為set(q) = x| x *, (q0, x) = q根據(jù)狀態(tài)進行劃分根據(jù)狀態(tài)進行劃分n 根據(jù)根據(jù)圖圖3-5所給的所給的DFA，set(q0) = x| x 0, 1*, x = 或或x以以1但不包括但不包括001結(jié)尾結(jié)尾set(q1) = x| x 0, 1 *, x = 0或或x以以1

2、0結(jié)尾結(jié)尾set(q2) = x| x 0, 1 *, x = 00或或x以以100結(jié)尾結(jié)尾set(q3) = x| x 0, 1 *, x以以000結(jié)尾結(jié)尾set(q4) = x| x 0, 1 *, x以以001結(jié)尾結(jié)尾它們是對它們是對0, 1*的劃分的劃分例例3-5構(gòu)造一個接受語言構(gòu)造一個接受語言x | x 0, 1*, 且當(dāng)把且當(dāng)把x看成看成二進制數(shù)時，二進制數(shù)時，x模模3與與0同余同余的的DFA分析：模分析：模3同余自然就構(gòu)成了二進制數(shù)的一個劃分。同余自然就構(gòu)成了二進制數(shù)的一個劃分。該劃分導(dǎo)致該劃分導(dǎo)致3個集合：個集合：3n| n為非負整數(shù)為非負整數(shù)，其元素包括，其元素包括0, 11

3、, 110, 1001,;3n + 1| n為非負整數(shù)為非負整數(shù)，其元素包括，其元素包括1, 100, 111, 1010,;3n + 2| n為非負整數(shù)為非負整數(shù) ，其元素包括，其元素包括10, 101, 1000, 1011,。例例3-5(續(xù)續(xù))先畫出如下三個狀態(tài)。先畫出如下三個狀態(tài)。 q0 : 希望能代表希望能代表3n| n為非負整數(shù)為非負整數(shù)q1 : 希望能代表希望能代表3n + 1 | n為非負整數(shù)為非負整數(shù)q2 : 希望能代表希望能代表3n + 2 | n為非負整數(shù)為非負整數(shù)q0q1q2例例3-5(續(xù)續(xù)) 當(dāng)當(dāng) x = 3n時，時， x0 = 2*3n + 0，仍然應(yīng)由，仍然應(yīng)由q

4、0代表代表 x1 = 2*3n + 1，應(yīng)由，應(yīng)由q1代表代表 當(dāng)當(dāng) x = 3n + 1時，時， x0 = 2*(3n + 1) + 0 = 6n + 2，應(yīng)由，應(yīng)由q2代表代表 x1 = 2*(3n + 1) + 1 = 6n + 3，應(yīng)由，應(yīng)由q0代表代表 當(dāng)當(dāng) x = 3n + 2時，時， x0 = 2*(3n + 2) + 0 = 6n + 3 + 1,應(yīng)由應(yīng)由q1代表代表 x1 = 2*(3n + 2) + 1 = 6n + 3 + 2，應(yīng)由，應(yīng)由q2代表代表例例3-5(續(xù)續(xù))其狀態(tài)轉(zhuǎn)移圖其狀態(tài)轉(zhuǎn)移圖(部分部分)如下所示：如下所示：q01q1q200110例例3-5(續(xù)續(xù))n應(yīng)將應(yīng)

5、將q0設(shè)置為終止?fàn)顟B(tài)。設(shè)置為終止?fàn)顟B(tài)。n空句子不可能代表二進制數(shù)，所以應(yīng)設(shè)置空句子不可能代表二進制數(shù)，所以應(yīng)設(shè)置一個新的狀態(tài)一個新的狀態(tài)qs作為初始狀態(tài)，在作為初始狀態(tài)，在qs下讀入下讀入0應(yīng)轉(zhuǎn)到狀態(tài)應(yīng)轉(zhuǎn)到狀態(tài)q0 ，讀入，讀入1則應(yīng)轉(zhuǎn)到狀態(tài)則應(yīng)轉(zhuǎn)到狀態(tài)q1。例例3-5(續(xù)續(xù))其完整狀態(tài)轉(zhuǎn)移圖如下所示：其完整狀態(tài)轉(zhuǎn)移圖如下所示：q01q1q200110S01qs思考思考n為表示模為表示模3與與1同余，應(yīng)怎樣畫狀態(tài)圖？同余，應(yīng)怎樣畫狀態(tài)圖？n模模4與與0同余呢？同余呢？n只需要改變其終止?fàn)顟B(tài)。只需要改變其終止?fàn)顟B(tài)。n同樣的方法可得，其狀態(tài)要多一個，同樣的方法可得，其狀態(tài)要多一個， 轉(zhuǎn)移也不同。轉(zhuǎn)

6、移也不同。練習(xí)練習(xí)(補充補充)n構(gòu)造一個接受語言構(gòu)造一個接受語言x | x 0, 1, 且當(dāng)把且當(dāng)把x看成二進制數(shù)時，看成二進制數(shù)時，x模模4與與0同余同余的的DFAn分析：本題實際上比例分析：本題實際上比例3-5簡單，考慮模簡單，考慮模4余數(shù)，只需要考慮最后兩位：余數(shù)，只需要考慮最后兩位： 00表示與表示與0同余，同余， 01表示與表示與1同余，同余，10表示與表示與2同余，同余，11表示與表示與3同余。特別地，單個的同余。特別地，單個的0表示與表示與0同余，單個的同余，單個的1表示與表示與1同余。同余。習(xí)題評講習(xí)題評講100Sqsq0q1q2q30101101例例3-4接受語言接受語言0n

7、1m2k |n, m, k 1的的DFAq0 : 啟動狀態(tài)，未讀入任何字符啟動狀態(tài)，未讀入任何字符q1 : 已讀入一個或多個已讀入一個或多個0q2 : 到達到達q1狀態(tài)后讀入一個或多個狀態(tài)后讀入一個或多個1q3 : 到達到達q2狀態(tài)后讀入一個或多個狀態(tài)后讀入一個或多個2Sq00q1q2q312012例例3-4(續(xù)續(xù))出現(xiàn)該語言不能接受的序列時進入陷井狀態(tài)出現(xiàn)該語言不能接受的序列時進入陷井狀態(tài)qt (t表示表示trap)Sq00q1q2q3120121,2qt200,10,1,2注意注意n當(dāng)當(dāng)FA進入陷井狀態(tài)后，就無法離開。進入陷井狀態(tài)后，就無法離開。n用畫圖的方式構(gòu)造用畫圖的方式構(gòu)造FA比較方

8、便、直觀。比較方便、直觀。 可以先根據(jù)語言的主要特征畫出其可以先根據(jù)語言的主要特征畫出其 “主體框架主體框架”，再考慮一些細節(jié)要求。，再考慮一些細節(jié)要求。nFA的狀態(tài)具有一定的記憶功能，不同的的狀態(tài)具有一定的記憶功能，不同的 狀態(tài)對應(yīng)于不同的情況。狀態(tài)對應(yīng)于不同的情況。FA的記憶功能的記憶功能n如：構(gòu)造語言如：構(gòu)造語言 x000y| x, y 0, 1*的的FA時，時，需要記憶需要記憶已經(jīng)讀入已經(jīng)讀入0個連續(xù)的個連續(xù)的0，已經(jīng)讀入，已經(jīng)讀入1個連續(xù)的個連續(xù)的0，已經(jīng)讀入，已經(jīng)讀入2個連續(xù)的個連續(xù)的0，已經(jīng)讀，已經(jīng)讀入至少入至少3個連續(xù)的個連續(xù)的0等至少等至少4個狀態(tài)。個狀態(tài)。n當(dāng)需要記憶無窮個

9、狀態(tài)時，就無法構(gòu)造相當(dāng)需要記憶無窮個狀態(tài)時，就無法構(gòu)造相應(yīng)的應(yīng)的FA。如語言。如語言 0n1n| n 1 。n語言語言 0m1n| m, n 1 需要需要4個狀態(tài)。個狀態(tài)。附加附加 DFA接收語言的例子接收語言的例子 構(gòu)造構(gòu)造DFA，接收語言接收語言 L=ab 附加附加 DFA接收語言的例子（續(xù)）接收語言的例子（續(xù)）基本結(jié)構(gòu)（接收基本句子）基本結(jié)構(gòu)（接收基本句子）q1abq0q2附加附加 DFA接收語言的例子（續(xù)）接收語言的例子（續(xù)）增加陷阱狀態(tài)后的DFAq1abq0qtbaa, ba, bq2思考思考1 如果將該如果將該DFADFA的的所有狀態(tài)所有狀態(tài)都設(shè)置都設(shè)置為為接收狀態(tài)接收狀態(tài)( (包

10、括陷阱狀態(tài)包括陷阱狀態(tài)) )， 接收的語言是接收的語言是？ 思考思考2 如果將該自動機的接收狀態(tài)和如果將該自動機的接收狀態(tài)和非接收非接收狀態(tài)對調(diào)，狀態(tài)對調(diào)， 接收的語言是接收的語言是？例例3-6n例例 3-6 構(gòu)造一個構(gòu)造一個DFA，它接受的語言，它接受的語言L=x|x0，1*，且對，且對x中任意一個中任意一個長度不大于長度不大于5的子串的子串a(chǎn)1a2an， a1+a2+an3，n5 。n輸入串為輸入串為 a1a2aiai+4ai+5am例例3-6(續(xù)續(xù))n當(dāng)當(dāng)i=1，2，3，也就是，也就是M讀到輸入串的第讀到輸入串的第1、2、3個字符時，它需要將這些字符記下來。個字符時，它需要將這些字符記下

11、來。 因為因為a1ai可能需要用來判定輸入串的最初可能需要用來判定輸入串的最初45個字符組成的子串是否滿足語言的要求。個字符組成的子串是否滿足語言的要求。 n當(dāng)當(dāng)i=4，5，即，即M讀到輸入串的第讀到輸入串的第4、5個字符時個字符時 在在a1+a2+ai3的情況下，的情況下， M需要將需要將a1ai記下來；記下來； 當(dāng)當(dāng)a1+a2+ai3時，時， M應(yīng)該進入陷阱狀態(tài)應(yīng)該進入陷阱狀態(tài)qt。 例例3-6(續(xù)續(xù))n當(dāng)當(dāng)i=6，也就是，也就是M讀到輸入串的第讀到輸入串的第6個字符，個字符，此時，以前讀到的第此時，以前讀到的第1個字符個字符a1沒有用了，沒有用了，此時它要看此時它要看a2+a3+a63是

12、否成立，是否成立， 如果成立，如果成立，M需要將需要將a2a6記下來；記下來； 在在a2+a3+ai3時，時，M應(yīng)進入陷阱狀態(tài)應(yīng)進入陷阱狀態(tài)qt。n當(dāng)當(dāng)i=7，類似，類似 n例例3-6(續(xù)續(xù))n當(dāng)當(dāng)M完成對子串完成對子串a(chǎn)1a2aiai+4的考察，并發(fā)現(xiàn)的考察，并發(fā)現(xiàn)它滿足語言的要求時，它滿足語言的要求時，M記下來的是記下來的是aiai+4，此時它讀入輸入串的第此時它讀入輸入串的第i+5個字符個字符ai+5，以前讀，以前讀到的第到的第i個字符個字符ai就沒有用了，就沒有用了， 此時它要看此時它要看ai+1+ai+2+ai+53是否成立，是否成立， 如果成立，如果成立，M需要將需要將ai+1，a

13、i+2，ai+5記下；記下； 當(dāng)當(dāng)ai+1+ai+2+ai+53時，時，M進入陷阱狀態(tài)進入陷阱狀態(tài)qt。 例例3-6(續(xù)續(xù))nM需要記憶的內(nèi)容有：需要記憶的內(nèi)容有：n什么都未讀入什么都未讀入20=1種；種；n記錄有記錄有1個字符個字符21=2種；種；n記錄有記錄有2個字符個字符22=4種；種；n記錄有記錄有3個字符個字符23=8種；種；n記錄有記錄有4個字符個字符24-1=15種；種；n記錄有記錄有5個字符個字符25-6=26種；種；n記錄當(dāng)前的輸入串不是句子記錄當(dāng)前的輸入串不是句子1種。種。 例例3-6(續(xù)續(xù))狀態(tài)設(shè)置狀態(tài)設(shè)置qM還未讀入任何字符；還未讀入任何字符；qt陷阱狀態(tài)；陷阱狀態(tài)；q

14、a1a2aiM記錄有記錄有i個字符，個字符，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 例例3-6(續(xù)續(xù))n(q，a1)=qa1n(qa1，a2)=qa1a2n(qa1a2，a3)=qa1a2a3 qa1a2a3a 如果a1+a2+a3+a3(qa1a2a3，a)= qt如果a1+a2+a3+a3 例例3-6(續(xù)續(xù)) qa1a2a3a4a 如果a1+a2+a3+a4+a3(qa1a2a3a4，a)= qt如果a1+a2+a3+a4+a3 qa2a3a4a5aa2+a3+a

15、4+ a5+a3(qa1a2a3a4a5，a)= qt如果a2+a3+a4+ a5+a3(qt，a)=qt作業(yè)作業(yè)(見習(xí)題見習(xí)題)n2. (3) (9)3.3 不確定的有窮狀態(tài)自動機不確定的有窮狀態(tài)自動機構(gòu)造接受語言構(gòu)造接受語言L=x| x 0,1*,且且 x含有子串含有子串00或或11的的DFA狀態(tài)說明狀態(tài)說明狀態(tài)狀態(tài)輸入字符輸入字符01開始狀態(tài)開始狀態(tài)qq0q1剛讀入的字符為剛讀入的字符為0q0q00q1剛讀入的字符為剛讀入的字符為1q1q0q11含含00，終止?fàn)顟B(tài)，終止?fàn)顟B(tài)q00q00q00含含11，終止?fàn)顟B(tài)，終止?fàn)顟B(tài)q11q11q113.3.1 作為對作為對DFA的修改的修改Sq00q

16、1q2q300,10,111希望是接受語言希望是接受語言L=x| x 0,1*,且且 x含有子串含有子串00或或11的的FA3.3.1 作為對作為對DFA的修改的修改n希望是接受希望是接受x|x0，1*，且，且x 的倒數(shù)第的倒數(shù)第10個字符為個字符為1的的FA與與DFA的區(qū)別的區(qū)別n并不是對于所有的并不是對于所有的(q, a) Q ， (q, a)都有一個狀態(tài)與之對應(yīng)都有一個狀態(tài)與之對應(yīng) (相當(dāng)于相當(dāng)于f(x)對某些對某些x沒有函數(shù)值沒有函數(shù)值) ；n并不是對于所有的并不是對于所有的 (q, a) Q ， (q, a)都只對應(yīng)一個狀態(tài)都只對應(yīng)一個狀態(tài)(相當(dāng)于相當(dāng)于f(x)對某對某些些x有多個函

17、數(shù)值有多個函數(shù)值)。理解這種理解這種“FA”n (q, a)對應(yīng)的是狀態(tài)的一個子集，即對應(yīng)的是狀態(tài)的一個子集，即x 2Q 當(dāng)這個子集為空時，表示沒有狀態(tài)與之對應(yīng)；當(dāng)這個子集為空時，表示沒有狀態(tài)與之對應(yīng)；當(dāng)這個子集的元素個數(shù)大于當(dāng)這個子集的元素個數(shù)大于1時，表示有多個時，表示有多個 狀態(tài)與之對應(yīng)。狀態(tài)與之對應(yīng)。當(dāng)這個子集元素個數(shù)為當(dāng)這個子集元素個數(shù)為1時，退化為時，退化為DFA。n從這個意義上，從這個意義上， (q, a)仍是通常意義下的仍是通常意義下的 一個函數(shù)，只是其值域發(fā)生了改變。一個函數(shù)，只是其值域發(fā)生了改變。這種這種“FA”的特點的特點Sq00q1q2q300,10,111具有具有“智

18、能智能”：可根據(jù)當(dāng)前從輸入字符串讀入：可根據(jù)當(dāng)前從輸入字符串讀入的的字符自動地選擇進入一個正確的狀態(tài)。字符自動地選擇進入一個正確的狀態(tài)。這種這種“FA”的特點的特點n具有具有“智能智能”n只要在只要在FA中中存在一條存在一條從開始狀態(tài)出發(fā)，從開始狀態(tài)出發(fā)， 最終到達某一個終止?fàn)顟B(tài)的標記為最終到達某一個終止?fàn)顟B(tài)的標記為x的路徑，的路徑，認為它接受了串認為它接受了串x，否則認為它不接受串，否則認為它不接受串x。n從這個意義上來說，這類從這個意義上來說，這類FA與與DFA的作用的作用 是一致的是一致的(識別句子是否合法識別句子是否合法)。NFA的形式定義的形式定義n 定義定義3-7 不確定的有窮狀態(tài)

19、自動機不確定的有窮狀態(tài)自動機 (non-deterministic finite automaton, NFA) M是一個五元組：是一個五元組：M = (Q, , , q0, F)其中，其中，Q, , q0, F 狀態(tài)的意義同狀態(tài)的意義同DFA(定義定義3-1) 狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù)。 : Q 2Q。 對對 (q, a) Q ， (q, a)=p1, p2, , pm 表示表示M在狀態(tài)在狀態(tài)q讀入字符讀入字符a， 可以選擇地將狀態(tài)變成可以選擇地將狀態(tài)變成p1, p2, ,或者或者pm， 并將讀頭向右移動一個帶方格而指向輸入字符串并將讀頭向右移動一個帶方格而指向輸入字符串 的下一個字符。的下

20、一個字符。擴充擴充 n 將將 擴充為擴充為 ： Q * 2Q。 對對 q Q， w * ，a ：(1) (q, )=q(2) (q, wa)= p| r (q, w), st. p (r, a) n 擴充的作用：擴充的作用：(1) 加入單位元素加入單位元素 (2) 從概念上允許一次接收字母表的任意從概念上允許一次接收字母表的任意 一個字符串，而不僅是一個字符一個字符串，而不僅是一個字符 與與 “兼容兼容” 的定義域的定義域Q 是是 的定義域的的定義域的Q *真子集，需真子集，需要考慮在上要考慮在上Q ， 是否與是否與 有相同的函數(shù)值有相同的函數(shù)值： (q, a) = (q, a) = p| r

21、 (q, ), st. p (r, a) 根據(jù)根據(jù)(2)= p| r q, st. p (r, a) 根據(jù)根據(jù)(1) = p| p (q, a) q是是r唯一可能值唯一可能值= (q, a)因此因此 與與 “兼容兼容”。約定：。約定：以后直接用以后直接用 代替代替 。進一步進一步擴充擴充 n將將 進一步進一步擴充為擴充為 : 2Q * 2Q。 對對 P Q， w * : (P, w) = (q, w) n 擴充的意義：從概念上可以處理一個狀態(tài)集合對擴充的意義：從概念上可以處理一個狀態(tài)集合對某一字符串的某一字符串的“反應(yīng)反應(yīng)”。 如：模如：模4余余0的例子中，無論是什么狀態(tài)下接收了的例子中，無論

22、是什么狀態(tài)下接收了00，都會轉(zhuǎn)到，都會轉(zhuǎn)到q0。n 更深的意義可借助定理更深的意義可借助定理3-1的證明及例的證明及例3-7體會。體會。Pq定義定義3-8n設(shè)設(shè)M = (Q, , , q0, F)為一個為一個NFA。 對于對于 x *：n如果如果 (q0, x) F ，則稱，則稱x 被被M所接受；所接受；如果如果 (q0, x) F = ，則稱，則稱M不接受不接受x。L(M) = x| x *且且 (q0, x) F 稱為由稱為由M接受接受(識別識別)的語言。的語言。練習(xí)練習(xí)(見習(xí)題見習(xí)題)n10. (1) n構(gòu)造識別語言構(gòu)造識別語言 L=x| x 0,1+, 且且 x中不含形如中不含形如00

23、的的子串的子串的NFA習(xí)題評講習(xí)題評講n10. (1)Sq0q20,100,10q1n本答案錯誤，因為任意串均可以到達本答案錯誤，因為任意串均可以到達q0習(xí)題評講習(xí)題評講(續(xù)續(xù))n 10. (1)正確答案與正確答案與2. (3)相同，因為相同，因為DFA是是NFA的特例的特例(把狀態(tài)把狀態(tài)q3去掉也可以去掉也可以)Sq01q110,1q30q2001分析分析nNFA適于構(gòu)造適于構(gòu)造“包含子串包含子串”， “以串以串開始，串開始，串結(jié)束結(jié)束”， “(倒數(shù)倒數(shù))第第個字母是個字母是”， “滿足條件滿足條件”的語言；的語言；nNFA不適于構(gòu)造不適于構(gòu)造“不包含子串不包含子串”， “不滿足條件不滿足條

24、件”的語言，在這些情況的語言，在這些情況下它可能退化為下它可能退化為DFA。例例3-7n求與下圖所示求與下圖所示NFA等價的等價的DFA。Sq00q1q2q300,10,111n從從q0開始可以到達的狀態(tài)為開始可以到達的狀態(tài)為可達狀態(tài)可達狀態(tài),對于對于DFA來說，只有可達狀態(tài)才有用。來說，只有可達狀態(tài)才有用。例例3-7(續(xù)續(xù))n分析：分析：DFA的一個狀態(tài)對應(yīng)的一個狀態(tài)對應(yīng)NFA的一個的一個狀態(tài)集合，因此，需要狀態(tài)集合，因此，需要24=16個狀態(tài)。個狀態(tài)。 下表列出其狀態(tài)轉(zhuǎn)移。下表列出其狀態(tài)轉(zhuǎn)移。例例3-7(續(xù)續(xù))狀態(tài)說明狀態(tài)說明狀態(tài)狀態(tài)輸入字符輸入字符01開始狀態(tài)開始狀態(tài) q0q0, q1q

25、0, q2q1q3q2q3終止?fàn)顟B(tài)終止?fàn)顟B(tài)q3q3q3 q0, q1q0, q1, q3 q0, q2 q0, q2q0, q1q0, q2, q3終止?fàn)顟B(tài)終止?fàn)顟B(tài)q0, q3q0, q1, q3 q0, q2, q3例例3-7(續(xù)續(xù))q1, q2q3q3終止?fàn)顟B(tài)終止?fàn)顟B(tài)q1, q3q3q3終止?fàn)顟B(tài)終止?fàn)顟B(tài)q2, q3q3q3q0, q1 , q2q0, q1, q3 q0, q2, q3終止?fàn)顟B(tài)終止?fàn)顟B(tài) q0, q1, q3q0, q1, q3 q0, q2, q3終止?fàn)顟B(tài)終止?fàn)顟B(tài) q0, q2, q3q0, q1, q3 q0, q2, q3終止?fàn)顟B(tài)終止?fàn)顟B(tài)q1, q2, q3q3q3終止

26、狀態(tài)終止?fàn)顟B(tài)q0, q1, q2, q3 q0, q1, q3 q0, q2, q3例例3-7(續(xù)續(xù))n獲得的獲得的DFA。Sq00q0,q1 0011q0,q210q0,q1,q301q0,q2,q31例例3-7(續(xù)續(xù))n減少工作量的方法減少工作量的方法只列出可達狀態(tài)的轉(zhuǎn)移，即填表時不需要填完只列出可達狀態(tài)的轉(zhuǎn)移，即填表時不需要填完填表時可用填表時可用0, 1代替代替q0,q1 總是不可達的，可將該狀態(tài)對應(yīng)的轉(zhuǎn)移去掉總是不可達的，可將該狀態(tài)對應(yīng)的轉(zhuǎn)移去掉n說明說明這種記法主要是為了保持上下文一致，實際這種記法主要是為了保持上下文一致，實際上它與上它與q0,q1應(yīng)有所區(qū)別。應(yīng)有所區(qū)別。定理定理

27、3-1 nNFA與與DFA等價。等價。NFA與與DFA等價等價是指是指NFA和和DFA能識能識別相同的語言類。別相同的語言類?；仡櫥仡櫟葍r等價的概念：的概念： 識別相同的語言識別相同的語言(定義定義3-3)。證明思路證明思路n(1) 顯然，顯然，DFA是是NFA的特殊形式；即所有的的特殊形式；即所有的DFA已經(jīng)用已經(jīng)用NFA的形式表示；的形式表示；n(2) 需要證明對于任意給定的需要證明對于任意給定的NFA，存在與之，存在與之等價的等價的DFA。根據(jù)根據(jù)NFA構(gòu)造構(gòu)造DFA，將狀態(tài)集合從，將狀態(tài)集合從Q變換到變換到2Q，這樣這樣DFA中的任意一個狀態(tài)實際上是中的任意一個狀態(tài)實際上是NFA中某些中某些狀態(tài)的組合狀態(tài)的組合(這里避免使用術(shù)語這里避免使用術(shù)語“集合集合”)。使用歸納法證明使用歸納法證明DFA