自動(dòng)機(jī)與形式語(yǔ)言_第三章_DFA_NFA

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

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

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

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

5、串中讀入一個(gè)字符，根據(jù)當(dāng)前狀輸入字符串中讀入一個(gè)字符，根據(jù)當(dāng)前狀態(tài)和讀入的這個(gè)字符轉(zhuǎn)到新的狀態(tài)。當(dāng)前態(tài)和讀入的這個(gè)字符轉(zhuǎn)到新的狀態(tài)。當(dāng)前狀態(tài)和新的狀態(tài)可以是同一個(gè)狀態(tài)，也可狀態(tài)和新的狀態(tài)可以是同一個(gè)狀態(tài)，也可以是不同的狀態(tài)；當(dāng)系統(tǒng)從輸入字符串中以是不同的狀態(tài)；當(dāng)系統(tǒng)從輸入字符串中讀入一個(gè)字符后，它下一次再讀時(shí)，會(huì)讀讀入一個(gè)字符后，它下一次再讀時(shí)，會(huì)讀入下一個(gè)字符。這就是說(shuō)，相當(dāng)于系統(tǒng)維入下一個(gè)字符。這就是說(shuō)，相當(dāng)于系統(tǒng)維持有一個(gè)讀寫(xiě)指針，該指針在系統(tǒng)讀入一持有一個(gè)讀寫(xiě)指針，該指針在系統(tǒng)讀入一個(gè)字符后指向輸入串的下一個(gè)字符。個(gè)字符后指向輸入串的下一個(gè)字符。 2022-1-1483.1 語(yǔ)言的識(shí)別

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

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

8、te automaton,FA) M=(Q，q0，F(xiàn))Q狀態(tài)的非空有窮集合。狀態(tài)的非空有窮集合。 qQ，q稱(chēng)為稱(chēng)為M的一個(gè)的一個(gè)狀態(tài)狀態(tài)(state)。輸入字母表輸入字母表(Input alphabet)。輸入字。輸入字符串都是符串都是上的字符串。上的字符串。 q0q0Q，是，是M的的開(kāi)始狀態(tài)開(kāi)始狀態(tài)(initial state)，也可叫做初始狀態(tài)或者啟動(dòng)狀態(tài)。也可叫做初始狀態(tài)或者啟動(dòng)狀態(tài)。2022-1-14123.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 狀態(tài)狀態(tài)轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)(transition function)，有時(shí)候又叫做狀態(tài)轉(zhuǎn)換函數(shù)或者移動(dòng)函數(shù)。有時(shí)候又叫做狀態(tài)轉(zhuǎn)換函數(shù)或者移動(dòng)函數(shù)。：Q

9、Q，對(duì)，對(duì) (q，a)Q，(q，a)=p表示：表示：M在狀態(tài)在狀態(tài)q讀入字符讀入字符a，將狀態(tài)，將狀態(tài)變成變成p，并將讀頭向右移動(dòng)一個(gè)帶方格而指，并將讀頭向右移動(dòng)一個(gè)帶方格而指向輸入字符串的下一個(gè)字符。向輸入字符串的下一個(gè)字符。FF Q，是，是M的的終止?fàn)顟B(tài)終止?fàn)顟B(tài)(final state)集集合。合。 qF，q稱(chēng)為稱(chēng)為M的的終止?fàn)顟B(tài)，終止?fàn)顟B(tài)，又稱(chēng)為又稱(chēng)為接受狀態(tài)接受狀態(tài)(accept state)。 2022-1-14133.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 例例 3-1 下面是一個(gè)有窮狀態(tài)自動(dòng)機(jī)下面是一個(gè)有窮狀態(tài)自動(dòng)機(jī) M1=(q0，q1，q2，0，1，q0，q2)其中，其中，1(q0,0

10、)= q1，1(q1,0)= q2，1(q2,0)= q1 用表用表3-1表示表示1。狀態(tài)說(shuō)明狀態(tài)說(shuō)明狀態(tài)狀態(tài)輸入字符輸入字符0開(kāi)始狀態(tài)開(kāi)始狀態(tài)q0q1 q1q2終止?fàn)顟B(tài)終止?fàn)顟B(tài)q2q12022-1-14143.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 例例 3-1 下面是一個(gè)有窮狀態(tài)自動(dòng)機(jī)下面是一個(gè)有窮狀態(tài)自動(dòng)機(jī) M1=(q0，q1，q2，0，1，q0，q2)其中，其中，1(q0,0)= q1，1(q1,0)= q2，1(q2,0)= q1 2022-1-14153.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) M2=(q0，q1，q2，q3，0，1，2，2，q0，q2)2(q0,0)= q1，2(q1,0)= q

11、22(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 2022-1-14163.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 狀態(tài)說(shuō)明狀態(tài)說(shuō)明狀態(tài)狀態(tài)輸入字符輸入字符012開(kāi)始狀態(tài)開(kā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ù) 2022-1-14173.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 2022-1-14183.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 將將擴(kuò)充為擴(kuò)充

12、為QQ*:對(duì)任意的對(duì)任意的qQ，w*，a，定義，定義 ),(),()2(),() 1 (awqwaqqq2022-1-14193.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) ),(),(),(),(aqaqaqaq兩值相同，不用區(qū)分這兩個(gè)符號(hào)。兩值相同，不用區(qū)分這兩個(gè)符號(hào)。 2022-1-14203.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 確定的有窮狀態(tài)自動(dòng)機(jī)確定的有窮狀態(tài)自動(dòng)機(jī) 由于對(duì)于任意的由于對(duì)于任意的qQ， a，(q，a)均有均有確定的值，所以，將這種確定的值，所以，將這種FA稱(chēng)為稱(chēng)為確定的有窮狀確定的有窮狀態(tài)自動(dòng)機(jī)態(tài)自動(dòng)機(jī)(deterministic finite automaton，DFA) 2022

13、-1-14213.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) M接受接受(識(shí)別識(shí)別)的語(yǔ)言的語(yǔ)言 對(duì)于對(duì)于 x*如果如果(q，w)F，則稱(chēng)，則稱(chēng)x被被M接受，接受，如果如果(q，w) F，則稱(chēng)，則稱(chēng)M不接受不接受x。L(M)=x| x*且且(q，w)F稱(chēng)為由稱(chēng)為由M接受接受(識(shí)別識(shí)別)的語(yǔ)言的語(yǔ)言 如果如果L(M1)=L(M2)，則稱(chēng)，則稱(chēng)M1與與M2等價(jià)。等價(jià)。 L(M1)= L(M2)=02n|n1 2022-1-1422M1M223S10ACB100,1101是下面是下面DFA語(yǔ)言中的字符串。語(yǔ)言中的字符串。從從A出發(fā)：出發(fā)：3.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 例子: 識(shí)別語(yǔ)言中的串24101是下面

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

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

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

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

18、并且不以1結(jié)尾。 因此，w沒(méi)有連續(xù)的1并且以單個(gè)1結(jié)尾，歸納假設(shè)（2）對(duì)w成立.3.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 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)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) S10ACB100,136 w不被DFA接收的充要條件是(A, w) = C. 因此, w = x1y, x引導(dǎo)DFA到B, 1引導(dǎo)DFA到C,y是到達(dá)C以后產(chǎn)生的后綴。 如果(A,x

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

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

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

22、。入該串的剩余部分。2022-1-14393.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 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)說(shuō)明狀態(tài)說(shuō)明狀態(tài)狀態(tài)輸入字符輸入字符01開(kāi)始狀態(tài)開(kāi)始狀態(tài)q0q1q0 q1q2q0 q2q3q0終止?fàn)顟B(tài)終止?fàn)顟B(tài)q3q3q32022-1-14403.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 一種更為直觀的表示一種更為直觀的表示2022-1-14413.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 例例 3-3

23、構(gòu)造一個(gè)構(gòu)造一個(gè)DFA，它接受的語(yǔ)言為，它接受的語(yǔ)言為x000|x0，1*。 狀態(tài)狀態(tài)q0讀到的讀到的0可能是輸入字符串的最后三個(gè)可能是輸入字符串的最后三個(gè)0的第的第1個(gè)個(gè)0； 在狀態(tài)在狀態(tài)q1緊接著讀到的緊接著讀到的0可能是輸入字符串的最可能是輸入字符串的最后三個(gè)后三個(gè)0的第的第2個(gè)個(gè)0； 在狀態(tài)在狀態(tài)q2緊接著讀到的緊接著讀到的0可能是輸入字符串的最可能是輸入字符串的最后三個(gè)后三個(gè)0的第的第3個(gè)個(gè)0；2022-1-14423.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 在狀態(tài)在狀態(tài)q3緊接著讀到的緊接著讀到的0也可能是輸入字符串的也可能是輸入字符串的最后三個(gè)最后三個(gè)0的第的第3個(gè)個(gè)0； 如果在狀態(tài)如果

24、在狀態(tài)q1，q2，q3讀到的是讀到的是1，則要重新檢，則要重新檢查輸入串是否以三個(gè)查輸入串是否以三個(gè)0結(jié)尾。結(jié)尾。 2022-1-14433.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 幾點(diǎn)值得注意幾點(diǎn)值得注意 定義定義FA時(shí)，常常只給出時(shí)，常常只給出FA相應(yīng)的狀態(tài)轉(zhuǎn)相應(yīng)的狀態(tài)轉(zhuǎn)移圖就可以了。移圖就可以了。 對(duì)于對(duì)于DFA來(lái)說(shuō)，并行的弧按其上的標(biāo)記字來(lái)說(shuō)，并行的弧按其上的標(biāo)記字符的個(gè)數(shù)計(jì)算，對(duì)于每個(gè)頂點(diǎn)來(lái)說(shuō)，它的符的個(gè)數(shù)計(jì)算，對(duì)于每個(gè)頂點(diǎn)來(lái)說(shuō)，它的出度恰好等于輸入字母表中所含的字符的出度恰好等于輸入字母表中所含的字符的個(gè)數(shù)。個(gè)數(shù)。 2022-1-14443.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 不難看出，字符串

25、不難看出，字符串x被被FA M接受的充分必接受的充分必要條件是，在要條件是，在M的狀態(tài)轉(zhuǎn)移圖中存在一條的狀態(tài)轉(zhuǎn)移圖中存在一條從開(kāi)始狀態(tài)到某一個(gè)終止?fàn)顟B(tài)的有向路，從開(kāi)始狀態(tài)到某一個(gè)終止?fàn)顟B(tài)的有向路，該有向路上從第該有向路上從第1條邊到最后一條邊的標(biāo)記條邊到最后一條邊的標(biāo)記依次并置而構(gòu)成的字符串依次并置而構(gòu)成的字符串x。簡(jiǎn)稱(chēng)此路的標(biāo)。簡(jiǎn)稱(chēng)此路的標(biāo)記為記為x。 一個(gè)一個(gè)FA可以有多于可以有多于1個(gè)的終止?fàn)顟B(tài)。個(gè)的終止?fàn)顟B(tài)。 2022-1-14453.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 例例 3-4 構(gòu)造一個(gè)構(gòu)造一個(gè)DFA，它接受的語(yǔ)言，它接受的語(yǔ)言為為0n1m2k|n,m,k1。 q0M的啟動(dòng)狀態(tài)；的啟

26、動(dòng)狀態(tài)；q1M讀到至少一個(gè)讀到至少一個(gè)0，并等待讀更多的，并等待讀更多的0；q2M讀到至少一個(gè)讀到至少一個(gè)0后，讀到了至少一個(gè)后，讀到了至少一個(gè)1，并等待讀更多的，并等待讀更多的1；q3M讀到至少一個(gè)讀到至少一個(gè)0后跟至少一個(gè)后跟至少一個(gè)1后，后，并且接著讀到了至少一個(gè)并且接著讀到了至少一個(gè)2。 2022-1-14463.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 先設(shè)計(jì)先設(shè)計(jì)“主體框架主體框架”再補(bǔ)充細(xì)節(jié)再補(bǔ)充細(xì)節(jié)2022-1-1447 3.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 當(dāng)當(dāng)FA一旦進(jìn)入狀態(tài)一旦進(jìn)入狀態(tài)qt，它就無(wú)法離開(kāi)此狀，它就無(wú)法離開(kāi)此狀態(tài)。所以，態(tài)。所以，qt相當(dāng)于一個(gè)陷阱狀態(tài)相當(dāng)于一個(gè)陷阱狀態(tài)

27、(trap)。一般地，我們將陷阱狀態(tài)用作在其他狀態(tài)一般地，我們將陷阱狀態(tài)用作在其他狀態(tài)下發(fā)現(xiàn)輸入串不可能是該下發(fā)現(xiàn)輸入串不可能是該FA所識(shí)別的語(yǔ)言所識(shí)別的語(yǔ)言的句子時(shí)進(jìn)入的狀態(tài)。在此狀態(tài)下，的句子時(shí)進(jìn)入的狀態(tài)。在此狀態(tài)下，F(xiàn)A讀讀完輸入串中剩余的字符。完輸入串中剩余的字符。 2022-1-14483.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 在構(gòu)造一個(gè)識(shí)別給定語(yǔ)言的在構(gòu)造一個(gè)識(shí)別給定語(yǔ)言的FA時(shí)，用畫(huà)時(shí)，用畫(huà)圖的方式比較方便、直觀。我們可以先根圖的方式比較方便、直觀。我們可以先根據(jù)語(yǔ)言的主要特征畫(huà)出該據(jù)語(yǔ)言的主要特征畫(huà)出該FA的的“主體框主體框架架”，然后再去考慮畫(huà)出一些細(xì)節(jié)要求的，然后再去考慮畫(huà)出一些

28、細(xì)節(jié)要求的內(nèi)容。內(nèi)容。2022-1-14493.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) FA的狀態(tài)具有一定的記憶功能：不同的狀的狀態(tài)具有一定的記憶功能：不同的狀態(tài)對(duì)應(yīng)于不同的情況，由于態(tài)對(duì)應(yīng)于不同的情況，由于FA只有有窮個(gè)只有有窮個(gè)狀態(tài)，所以，在識(shí)別一個(gè)語(yǔ)言的過(guò)程中，狀態(tài)，所以，在識(shí)別一個(gè)語(yǔ)言的過(guò)程中，如果有無(wú)窮種情況需要記憶，我們肯定是如果有無(wú)窮種情況需要記憶，我們肯定是無(wú)法構(gòu)造出相應(yīng)的無(wú)法構(gòu)造出相應(yīng)的FA的。的。 2022-1-14503.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 例例 3-5構(gòu)造一個(gè)構(gòu)造一個(gè)DFA，它接受的語(yǔ)言，它接受的語(yǔ)言為為x|x0，1*，且當(dāng)把，且當(dāng)把x看成二進(jìn)制看成二進(jìn)制數(shù)時(shí)，數(shù)時(shí)

29、，x模模3與與0同余同余。 q0對(duì)應(yīng)除以對(duì)應(yīng)除以3余數(shù)為余數(shù)為0的的x組成的等價(jià)類(lèi)；組成的等價(jià)類(lèi)； q1對(duì)應(yīng)除以對(duì)應(yīng)除以3余數(shù)為余數(shù)為1的的x組成的等價(jià)類(lèi)；組成的等價(jià)類(lèi)； q2對(duì)應(yīng)除以對(duì)應(yīng)除以3余數(shù)為余數(shù)為2的的x組成的等價(jià)類(lèi)；組成的等價(jià)類(lèi)； qsM的開(kāi)始狀態(tài)。的開(kāi)始狀態(tài)。2022-1-14513.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) qs在此狀態(tài)下讀入在此狀態(tài)下讀入0時(shí)，有時(shí)，有x=0，所以應(yīng)，所以應(yīng)該進(jìn)入狀態(tài)該進(jìn)入狀態(tài)q0；讀入；讀入1時(shí)，有時(shí)，有x=1，所以應(yīng)，所以應(yīng)該進(jìn)入狀態(tài)該進(jìn)入狀態(tài)q1。即：。即：(qs，0)= q0；(qs，1)= q1 。2022-1-14523.2有窮狀態(tài)自動(dòng)機(jī)有窮

30、狀態(tài)自動(dòng)機(jī) q0能引導(dǎo)能引導(dǎo)M到達(dá)此狀態(tài)的到達(dá)此狀態(tài)的x除以除以3余余0，所以有：所以有：x=3*n+0。 讀入讀入0時(shí)，引導(dǎo)時(shí)，引導(dǎo)M到達(dá)下一個(gè)狀態(tài)的字符串到達(dá)下一個(gè)狀態(tài)的字符串為為x0，x0=2*(3*n+0)=3*2*n+0。所以，。所以，(q0，0)= q0； 讀入讀入1時(shí)，時(shí)，M到達(dá)下一個(gè)狀態(tài)的字符串為到達(dá)下一個(gè)狀態(tài)的字符串為x1，x1=2*(3*n+0)+1=3*2*n+1。所以，。所以，(q0，1)= q1；2022-1-14533.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) q1能引導(dǎo)能引導(dǎo)M到達(dá)此狀態(tài)的到達(dá)此狀態(tài)的x除以除以3余余1，所以有：所以有：x=3*n+1。 讀入讀入0時(shí)，引導(dǎo)時(shí)

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

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

33、一個(gè)中任意一個(gè)長(zhǎng)度不大于長(zhǎng)度不大于5的子串的子串a(chǎn)1a2an，a1+a2+an3，n5 。 輸入串為輸入串為 a1a2aiai+4ai+5am2022-1-14573.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 當(dāng)當(dāng)i=1，2，3，也就是，也就是M讀到輸入串的第讀到輸入串的第1、2、3個(gè)字符時(shí)，它需要將這些字符記下來(lái)。個(gè)字符時(shí)，它需要將這些字符記下來(lái)。因?yàn)橐驗(yàn)閍1ai可能需要用來(lái)判定輸入串的最可能需要用來(lái)判定輸入串的最初初45個(gè)字符組成的子串是否滿足語(yǔ)言的要個(gè)字符組成的子串是否滿足語(yǔ)言的要求。求。 當(dāng)當(dāng)i=4，5，也就是，也就是M讀到輸入串的第讀到輸入串的第4、5個(gè)個(gè)字符時(shí)，在字符時(shí)，在a1+a2+ai3

34、的情況下，的情況下，M需要將需要將a1ai記下來(lái)；在記下來(lái)；在a1+a2+ai3時(shí)，時(shí)，M應(yīng)該進(jìn)入陷阱狀態(tài)應(yīng)該進(jìn)入陷阱狀態(tài)qt。 2022-1-14583.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 當(dāng)當(dāng)i=6，也就是，也就是M讀到輸入串的第讀到輸入串的第6個(gè)字符，個(gè)字符，此時(shí)，以前讀到的第此時(shí)，以前讀到的第1個(gè)字符個(gè)字符a1就沒(méi)有用了，就沒(méi)有用了，此時(shí)它要看此時(shí)它要看a2+a3+a63是否成立，如果是否成立，如果成立，成立，M需要將需要將a2a6記下來(lái)；在記下來(lái)；在a2+a3+ai3時(shí)，時(shí)，M應(yīng)該進(jìn)入陷阱狀態(tài)應(yīng)該進(jìn)入陷阱狀態(tài)qt。 2022-1-14593.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 當(dāng)當(dāng)M完成對(duì)子

35、串完成對(duì)子串a(chǎn)1a2aiai+4的考察，并發(fā)的考察，并發(fā)現(xiàn)它滿足語(yǔ)言的要求時(shí)，現(xiàn)它滿足語(yǔ)言的要求時(shí)，M記下來(lái)的是記下來(lái)的是aiai+4，此時(shí)它讀入輸入串的第，此時(shí)它讀入輸入串的第i+5個(gè)字符個(gè)字符ai+5，以前讀到的第，以前讀到的第i個(gè)字符個(gè)字符ai就沒(méi)有用了，就沒(méi)有用了，此時(shí)它要看此時(shí)它要看ai+1+ai+2+ai+53是否成立，是否成立，如果成立，如果成立，M需要將需要將ai+1，ai+2，ai+5記下記下來(lái)；在來(lái)；在ai+1+ai+2+ai+53時(shí)，時(shí)，M應(yīng)該進(jìn)入陷應(yīng)該進(jìn)入陷阱狀態(tài)阱狀態(tài)qt。 2022-1-14603.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) M需要記憶的內(nèi)容有：需要記憶的內(nèi)容有

36、： 什么都未讀入什么都未讀入20=1種；種； 記錄有記錄有1個(gè)字符個(gè)字符21=2種；種； 記錄有記錄有2個(gè)字符個(gè)字符22=4種；種； 記錄有記錄有3個(gè)字符個(gè)字符23=8種；種； 記錄有記錄有4個(gè)字符個(gè)字符24-1=15種；種； 記錄有記錄有5個(gè)字符個(gè)字符25-6=26種；種； 記錄當(dāng)前的輸入串不是句子記錄當(dāng)前的輸入串不是句子1種。種。 2022-1-14613.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī)狀態(tài)設(shè)置狀態(tài)設(shè)置qM還未讀入任何字符；還未讀入任何字符；qt陷阱狀態(tài)；陷阱狀態(tài)；qa1a2aiM記錄有記錄有i個(gè)字符，個(gè)字符，1i5。a1，a2，ai0，1。取取DFA M=(Q，0，1，q，F(xiàn))F= q

37、qa1a2ai| a1，a2，ai0，1且且1i5且且a1+a2+ai3Q=qt F 2022-1-14623.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) (q，a1)=qa1 (qa1，a2)=qa1a2 (qa1a2，a3)=qa1a2a3 qa1a2a3a如果a1+a2+a3+a3(qa1a2a3，a)= qt如果a1+a2+a3+a3 2022-1-14633.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) qa1a2a3a4a 如果a1+a2+a3+a4+a3(qa1a2a3a4，a)= qt如果a1+a2+a3+a4+a3qa2a3a4a5a a2+a3+a4+ a5+a3(qa1a2a3a4a5，a)=qt

38、如果a2+a3+a4+ a5+a3(qt，a1)=qt2022-1-14643.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 接受語(yǔ)言接受語(yǔ)言x000|x0，1*x001|x0，1*的的FA 2022-1-14653.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 能引導(dǎo)能引導(dǎo)FA從開(kāi)始狀態(tài)到達(dá)從開(kāi)始狀態(tài)到達(dá)q的字符串的集合為：的字符串的集合為：set(q)=x | x*，(q0，x)=q對(duì)圖對(duì)圖3-5所給的所給的DFA 中的所有中的所有q，求，求set(q)。2022-1-1466set(q0)=x | x*，x=或者或者x以以1但不是但不是001結(jié)尾結(jié)尾set(q1)=x | x*，x=0或者或者x以以10結(jié)尾結(jié)尾se

39、t(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個(gè)集合是兩兩互不相交。個(gè)集合是兩兩互不相交。 2022-1-14673.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 對(duì)于任意一個(gè)對(duì)于任意一個(gè)FA M=(Q，q0，F(xiàn))我們可以按照如下方式定義關(guān)系我們可以按照如下方式定義關(guān)系RM： 對(duì)對(duì) x，y*，xRMy qQ，使得，使得xset(q)和和yset(q)同時(shí)成立。同時(shí)成立。 按照這個(gè)定義所得到的關(guān)系實(shí)際上是按照這個(gè)定義所得到的關(guān)系實(shí)際上是*上上的一個(gè)等價(jià)關(guān)系。利用這個(gè)關(guān)系，可以將的一個(gè)等價(jià)

40、關(guān)系。利用這個(gè)關(guān)系，可以將*劃分成不多于劃分成不多于|Q|個(gè)等價(jià)類(lèi)。個(gè)等價(jià)類(lèi)。 2022-1-14683.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 即時(shí)描述即時(shí)描述(instantaneous description，ID ） x，y*，(q0，x)=q, xqy稱(chēng)為稱(chēng)為M的一個(gè)的一個(gè)即即時(shí)描述，時(shí)描述，表示表示xy是是M正在處理的一個(gè)字符串，正在處理的一個(gè)字符串，x引導(dǎo)引導(dǎo)M從從q0啟動(dòng)并到達(dá)狀態(tài)啟動(dòng)并到達(dá)狀態(tài)q，M當(dāng)前正注視當(dāng)前正注視著著y的首字符。的首字符。 如果如果xqay是是M的一個(gè)即時(shí)描述，且的一個(gè)即時(shí)描述，且(q，a)=p，則則xqay M xapy。 2022-1-14693.2有窮狀態(tài)

41、自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) Mn ：表示：表示M從即時(shí)描述從即時(shí)描述經(jīng)過(guò)經(jīng)過(guò)n次移動(dòng)到次移動(dòng)到達(dá)即時(shí)描述達(dá)即時(shí)描述。 M存在即時(shí)描述存在即時(shí)描述1，2，n-1，使得，使得 M 1，1M 2，n-1M 當(dāng)當(dāng)n=0n=0時(shí)，有時(shí)，有=。即。即M M 0 0 。 M M + + ：表示：表示M M從即時(shí)描述從即時(shí)描述經(jīng)過(guò)至少經(jīng)過(guò)至少1 1次移動(dòng)到次移動(dòng)到達(dá)即時(shí)描述達(dá)即時(shí)描述。 M M * * ：表示：表示M M從即時(shí)描述從即時(shí)描述經(jīng)過(guò)若干步移動(dòng)經(jīng)過(guò)若干步移動(dòng)到達(dá)即時(shí)描述到達(dá)即時(shí)描述。 2022-1-14703.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 當(dāng)意義清楚時(shí)，我們將符號(hào)當(dāng)意義清楚時(shí)，我們將符號(hào)M、Mn、M*、

42、M+中的中的M省去，分別用省去，分別用、n、*、+表示。表示。 2022-1-14713.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 對(duì)下圖所示的對(duì)下圖所示的DFA有如下的有如下的ID轉(zhuǎn)換：轉(zhuǎn)換：2022-1-14723.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) q01010010001 1q0010010001 10q110010001 101q00010001 1010q1010001 10100q210001 101001q00001 1010010q1001 10100100q201 2022-1-14733.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 101001000q31 1010010001q0即 q01010

43、01000110 1010010001q0 q01010010001+ 1010010001q0 q01010010001* 1010010001q0 2022-1-14743.2有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī) 對(duì)于x*, q0 x1+ x1q0 q0 x10+ x10q1 q0 x100+ x100q2 q0 x000+ x000q3 2022-1-14753.3 NFA 3.3.1 作為對(duì)作為對(duì)DFA的修改的修改 希望是接受希望是接受x|x0，1*，且，且x含有子串含有子串00或或11的的FA如下：如下：2022-1-14763.3.1 作為對(duì)作為對(duì)DFA的修改的修改 希望是接受希望是接受x

44、|x0，1*，且，且x 的倒數(shù)第的倒數(shù)第10個(gè)字符為個(gè)字符為1的的FA如下如下 ：2022-1-14773.3.1 作為對(duì)作為對(duì)DFA的修改的修改 這兩個(gè)圖所給的這兩個(gè)圖所給的“FA”與前面我們所定義與前面我們所定義的的FA，即，即DFA，的區(qū)別在于：，的區(qū)別在于： 并不是對(duì)于所有的并不是對(duì)于所有的(q，a)Q,(q，a)都有一個(gè)狀態(tài)與它對(duì)應(yīng)；都有一個(gè)狀態(tài)與它對(duì)應(yīng)； 并不是對(duì)于所有的并不是對(duì)于所有的(q，a)Q,(q，a)只對(duì)應(yīng)一個(gè)狀態(tài)。只對(duì)應(yīng)一個(gè)狀態(tài)。 “FA”在任意時(shí)刻可以處于有窮多個(gè)狀態(tài)。在任意時(shí)刻可以處于有窮多個(gè)狀態(tài)。 “FA”具有具有“智能智能”。2022-1-14783.3.2 N

45、FA的形式定義的形式定義 不確定的有窮狀態(tài)自動(dòng)機(jī)不確定的有窮狀態(tài)自動(dòng)機(jī)(non-deterministic finite automaton ,NFA) M是一個(gè)五元組是一個(gè)五元組M=(Q，q0，F(xiàn)) Q、q0、F的意義同的意義同DFA。 ：Q2Q，對(duì)，對(duì) (q，a)Q，(q，a)= p1，p2，pm表示表示M在狀態(tài)在狀態(tài)q讀入字符讀入字符a，可，可以選擇地將狀態(tài)變成以選擇地將狀態(tài)變成p1、或者、或者p2、或者、或者pm ，并將讀頭向右移動(dòng)一個(gè)帶方格而指向輸入字符并將讀頭向右移動(dòng)一個(gè)帶方格而指向輸入字符串的下一個(gè)字符。串的下一個(gè)字符。 2022-1-14793.3.2 NFA的形式定義的形式定

46、義 FA的狀態(tài)轉(zhuǎn)移圖、的狀態(tài)轉(zhuǎn)移圖、FA的狀態(tài)對(duì)應(yīng)的等價(jià)類(lèi)、的狀態(tài)對(duì)應(yīng)的等價(jià)類(lèi)、FA的即時(shí)描述對(duì)的即時(shí)描述對(duì)NFA都有效。都有效。 接受接受x|x0，1*，且，且x含有子串含有子串00或或11的的FA對(duì)應(yīng)的移動(dòng)函數(shù)定義表。對(duì)應(yīng)的移動(dòng)函數(shù)定義表。2022-1-14803.3.2 NFA的形式定義的形式定義 狀態(tài)說(shuō)明狀態(tài)說(shuō)明狀態(tài)狀態(tài)輸入字符輸入字符01啟動(dòng)狀態(tài)啟動(dòng)狀態(tài)q0q0，q1 q0，q2 q1q3 q2q3終止?fàn)顟B(tài)終止?fàn)顟B(tài)q3q3q32022-1-14813.3.2 NFA的形式定義的形式定義 接受接受x|x0，1*，且，且x 的倒數(shù)第的倒數(shù)第10個(gè)字符個(gè)字符為為1的的FA對(duì)應(yīng)的移動(dòng)函數(shù)定義

47、表。對(duì)應(yīng)的移動(dòng)函數(shù)定義表。2022-1-14823.3.2 NFA的形式定義的形式定義 狀態(tài)說(shuō)明狀態(tài)說(shuō)明狀態(tài)狀態(tài)輸入字符輸入字符01啟動(dòng)狀態(tài)啟動(dòng)狀態(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)q102022-1-14833.3.2 NFA的形式定義的形式定義 將將擴(kuò)充為擴(kuò)充為QQ2:*對(duì)任意的對(duì)任意的qQ，w*，a，定義，定義 a)，(rp，使得w)，(q r|p),()2(),()1 (waqqq2022-1-14843.3.2 NFA的形式定義的形式定義 M接受接受

48、(識(shí)別識(shí)別)的語(yǔ)言的語(yǔ)言 對(duì)于對(duì)于 x*，如果如果(q0，w) F，則稱(chēng)則稱(chēng)x被被M接受，如果接受，如果(q0，w)F=，則稱(chēng)則稱(chēng)M不接受不接受x。L(M)=x| x*且且(q0，w) F，稱(chēng)為由稱(chēng)為由M接受接受(識(shí)別識(shí)別)的語(yǔ)言。的語(yǔ)言。 2022-1-148586DFA例子: 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,94,8 54,6 5,7,916,8 5包含了終止?fàn)顟B(tài)，接收啟動(dòng)狀態(tài)啟動(dòng)狀態(tài)終止?fàn)顟B(tài)終止?fàn)顟B(tài)873.3.3 NFA與與DFA等價(jià)等價(jià) 任意

49、任意DFA可以轉(zhuǎn)換成接收相同語(yǔ)言的可以轉(zhuǎn)換成接收相同語(yǔ)言的NFA。 如果DFA中有D(q, a) = p, 在NFA中使得 N(q, a) = p. 那么NFA總與DFA讀取輸入后處于相同的狀態(tài)。 DFANFA88 類(lèi)似的，對(duì)于任意NFA，可以找到一個(gè)對(duì)應(yīng)的DFA接收相同的語(yǔ)言。 證明方法：子集構(gòu)造（subset construction）。3.3.3 NFA與與DFA等價(jià)等價(jià) NFADFA3.3.3 NFA與與DFA等價(jià)等價(jià) 對(duì)于一個(gè)輸入字符，對(duì)于一個(gè)輸入字符，NFA與與DFA的差異是的差異是前者可以進(jìn)入若干個(gè)狀態(tài)，而后者只能進(jìn)前者可以進(jìn)入若干個(gè)狀態(tài)，而后者只能進(jìn)入一個(gè)惟一的狀態(tài)。雖然從入一

50、個(gè)惟一的狀態(tài)。雖然從DFA看待問(wèn)題看待問(wèn)題的角度來(lái)說(shuō)，的角度來(lái)說(shuō)，NFA在某一時(shí)刻同時(shí)進(jìn)入若在某一時(shí)刻同時(shí)進(jìn)入若干個(gè)狀態(tài)，但是，這若干個(gè)狀態(tài)合在一起干個(gè)狀態(tài)，但是，這若干個(gè)狀態(tài)合在一起的的“總效果總效果”相當(dāng)于它處于這些狀態(tài)對(duì)應(yīng)相當(dāng)于它處于這些狀態(tài)對(duì)應(yīng)的一個(gè)的一個(gè)“綜合狀態(tài)綜合狀態(tài)”。因此，我們考慮讓。因此，我們考慮讓DFA用一個(gè)狀態(tài)去對(duì)應(yīng)用一個(gè)狀態(tài)去對(duì)應(yīng)NFA的一組狀態(tài)。的一組狀態(tài)。 2022-1-14892022-1-1490狀態(tài)說(shuō)明狀態(tài)說(shuō)明狀態(tài)狀態(tài)輸入字符輸入字符01啟動(dòng)狀態(tài)啟動(dòng)狀態(tài)q0q0，q1 q0，q2 q1q3 q2q3終止?fàn)顟B(tài)終止?fàn)顟B(tài)q3q3q33.3.3 NFA與與DFA等價(jià)

51、等價(jià) q0，q1q0，q2q03.3.3 NFA與與DFA等價(jià)等價(jià) NFA M1=(Q，1，q0，F(xiàn)1)與與DFA M2=(Q2，2，q0，F(xiàn)2)的對(duì)應(yīng)關(guān)系：的對(duì)應(yīng)關(guān)系： NFA從開(kāi)始狀態(tài)從開(kāi)始狀態(tài)q0啟動(dòng)，我們就讓相應(yīng)的啟動(dòng)，我們就讓相應(yīng)的DFA從狀態(tài)從狀態(tài)q0啟動(dòng)。所以啟動(dòng)。所以q0= q0。 對(duì)于對(duì)于NFA 的一個(gè)狀態(tài)組的一個(gè)狀態(tài)組q1，q2，qn，如，如果果NFA在此狀態(tài)組時(shí)在此狀態(tài)組時(shí)讀入字符讀入字符a后可以后可以進(jìn)入狀進(jìn)入狀態(tài)組態(tài)組p1，p2，pm,則讓相應(yīng)的則讓相應(yīng)的DFA在狀態(tài)在狀態(tài)q1，q2，qn讀入字符讀入字符a時(shí)，時(shí)，進(jìn)入狀態(tài)進(jìn)入狀態(tài)p1，p2，pm。 2022-1-14

52、911=(=(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，p2，pm 93子集構(gòu)造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,

53、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)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm r b12,4,6,852,42,4,6,8 1,3,5,71,

54、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,71,3,5,72,4 596子集構(gòu)造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,

55、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 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

56、*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 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，p

57、2，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 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

58、,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等價(jià)等價(jià) 定理定理 3-1 NFA與與DFA等價(jià)。等價(jià)。證明：證明：構(gòu)造與構(gòu)造與M1等價(jià)的等價(jià)的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 2022-1-141003.3.3 NFA與與DFA等價(jià)等價(jià) 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(q