有限自動(dòng)機(jī)理論03章有限狀態(tài)自動(dòng)機(jī)

1、第三章第三章有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī) 定義語言定義語言可以從兩個(gè)方面可以從兩個(gè)方面進(jìn)行進(jìn)行： ）從）從產(chǎn)生產(chǎn)生語言的角度；語言的角度；）從）從接收接收(或識別或識別)語言的角度。語言的角度。形式語言研究內(nèi)容形式語言研究內(nèi)容產(chǎn)生產(chǎn)生一個(gè)語言一個(gè)語言:1)定義語言中的定義語言中的基本句子基本句子;2)根據(jù)根據(jù)其余句子其余句子的的形成規(guī)則形成規(guī)則，產(chǎn)生產(chǎn)生出該語言所包含的所有出該語言所包含的所有句子句子。有限自動(dòng)機(jī)有限自動(dòng)機(jī)研究內(nèi)容研究內(nèi)容 使用某種使用某種自動(dòng)機(jī)模型自動(dòng)機(jī)模型來接收字符串來接收字符串 接收接收的所有字符串形成的集合，也的所有字符串形成的集合，也是一個(gè)語言是一個(gè)語言統(tǒng)一的理論 形

2、式語言與自動(dòng)機(jī)作為統(tǒng)一的理論形式語言與自動(dòng)機(jī)作為統(tǒng)一的理論,實(shí)實(shí)際上包括際上包括3個(gè)方面的內(nèi)容個(gè)方面的內(nèi)容:1) 形式語言形式語言理論理論(文法產(chǎn)生語言文法產(chǎn)生語言)2) 自動(dòng)機(jī)自動(dòng)機(jī)理論理論(自動(dòng)機(jī)接收語言自動(dòng)機(jī)接收語言)3) 形式語言與自動(dòng)機(jī)的形式語言與自動(dòng)機(jī)的等價(jià)性等價(jià)性理論理論 (文文法與自動(dòng)機(jī)等價(jià)轉(zhuǎn)換法與自動(dòng)機(jī)等價(jià)轉(zhuǎn)換)有限自動(dòng)機(jī)分為有限自動(dòng)機(jī)分為3類類l有限有限狀態(tài)狀態(tài)自動(dòng)機(jī)自動(dòng)機(jī)FAl下推自動(dòng)機(jī)下推自動(dòng)機(jī)PDAl圖靈機(jī)圖靈機(jī)TM有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī) FA(Finite state Automaton)FA是為研究是為研究 有限存儲有限存儲的機(jī)制的機(jī)制 和和 正則語言正則語

3、言而抽象出的一種模型。而抽象出的一種模型。兩類有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī)接收器接收器 判斷是否判斷是否接收接收輸入串；輸入串；轉(zhuǎn)換器轉(zhuǎn)換器 對給定輸入串對給定輸入串產(chǎn)生輸出產(chǎn)生輸出。FA還可以分為還可以分為 確定的確定的FA-DFA Deterministic Finite state Automaton 非確定非確定FA- NFANon-deterministic Finite state Automaton等價(jià)性等價(jià)性 有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī)接收接收的語言稱的語言稱為為有限狀態(tài)語言有限狀態(tài)語言-FSL 從從產(chǎn)生產(chǎn)生語言角度而言，語言角度而言， FSL就就是是右線性語言右線性語言-R

4、LL 從從(正則正則)運(yùn)算運(yùn)算角度而言，角度而言， FSL就是就是正則語言正則語言-RL 有限狀態(tài)自動(dòng)機(jī)除在理論上的研有限狀態(tài)自動(dòng)機(jī)除在理論上的研究價(jià)值外究價(jià)值外 還在還在數(shù)字電路設(shè)計(jì)數(shù)字電路設(shè)計(jì)、編譯技術(shù)、編譯技術(shù)(詞詞法分析法分析)、系統(tǒng)輔助軟件、系統(tǒng)輔助軟件(文本編輯文本編輯程序程序)、漏洞檢測漏洞檢測、交通控制交通控制等應(yīng)等應(yīng)用領(lǐng)域得到廣泛應(yīng)用用領(lǐng)域得到廣泛應(yīng)用3.1 有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī) 有限狀態(tài)自動(dòng)機(jī)是具有有限狀態(tài)自動(dòng)機(jī)是具有離散離散輸入和輸入和離散離散輸出的一種輸出的一種數(shù)學(xué)模型數(shù)學(xué)模型。l有限狀態(tài)自動(dòng)機(jī)是否有限狀態(tài)自動(dòng)機(jī)是否接收串接收串wl有限狀態(tài)自動(dòng)機(jī)是否有限狀態(tài)自動(dòng)

5、機(jī)是否接收語言接收語言L有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī)物理模型物理模型a1a2a3 aj anan+1FSC 一個(gè)輸入一個(gè)輸入存儲帶（輸入帶）存儲帶（輸入帶），帶，帶被分解為被分解為單元單元，每個(gè)單元存放一個(gè)，每個(gè)單元存放一個(gè)輸入符號輸入符號(字母表上的符號字母表上的符號)。 整個(gè)輸入串從帶的左端點(diǎn)開始存整個(gè)輸入串從帶的左端點(diǎn)開始存放，而帶的右端可以放，而帶的右端可以無限擴(kuò)充無限擴(kuò)充； 一個(gè)有窮狀態(tài)控制器（一個(gè)有窮狀態(tài)控制器（FSC） 該控制器的狀態(tài)只能是有限多個(gè)該控制器的狀態(tài)只能是有限多個(gè) FSC通過通過讀頭讀頭讀取讀取當(dāng)前帶上單元當(dāng)前帶上單元的字符。的字符。 初始時(shí)，讀頭對應(yīng)帶的初始時(shí)，讀頭

6、對應(yīng)帶的最左最左單元單元，每讀取一個(gè)字符，讀頭，每讀取一個(gè)字符，讀頭向右向右自動(dòng)移動(dòng)一個(gè)單元。自動(dòng)移動(dòng)一個(gè)單元。 讀頭（暫時(shí)）讀頭（暫時(shí)）不不允許允許向左移動(dòng)向左移動(dòng)。有限狀態(tài)自動(dòng)機(jī)的一個(gè)有限狀態(tài)自動(dòng)機(jī)的一個(gè)動(dòng)作動(dòng)作為：為： 讀頭讀取帶上當(dāng)前單元的字符讀頭讀取帶上當(dāng)前單元的字符 FSC根據(jù)當(dāng)前根據(jù)當(dāng)前FSC的的狀態(tài)狀態(tài)和讀取和讀取的的字符字符，進(jìn)行進(jìn)行狀態(tài)改變狀態(tài)改變； 將讀頭將讀頭向右移動(dòng)向右移動(dòng)一個(gè)單元。一個(gè)單元。有限態(tài)自動(dòng)機(jī)的動(dòng)作可以有限態(tài)自動(dòng)機(jī)的動(dòng)作可以簡化簡化為：為： FSC根據(jù)根據(jù) 當(dāng)前狀態(tài)當(dāng)前狀態(tài) 和和 當(dāng)前讀取的帶上當(dāng)前讀取的帶上字符字符 進(jìn)行進(jìn)行狀態(tài)改變狀態(tài)改變。定義定義3-

7、1 有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī)FAFA是一個(gè)五元式是一個(gè)五元式 FA=(Q，q0，F(xiàn)) Q是有限狀態(tài)的集合是有限狀態(tài)的集合 是字母表，即輸入帶上的字是字母表，即輸入帶上的字符集合符集合 q0Q是開始狀態(tài)是開始狀態(tài) F Q是接收狀態(tài)是接收狀態(tài)(終終止?fàn)钪範(fàn)顟B(tài)態(tài))集合集合是是QQ的狀態(tài)轉(zhuǎn)換函數(shù)的狀態(tài)轉(zhuǎn)換函數(shù) 即即(q，x)= q代表代表FA在狀態(tài)在狀態(tài)q時(shí)，掃描字符時(shí)，掃描字符x后后狀態(tài)改變?yōu)闋顟B(tài)改變?yōu)閝（也稱到達(dá)狀態(tài)（也稱到達(dá)狀態(tài)q ） 有限狀態(tài)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函有限狀態(tài)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)的數(shù)的個(gè)數(shù)個(gè)數(shù)應(yīng)該為應(yīng)該為 |Q|*| 對于對于Q中的每個(gè)中的每個(gè)狀態(tài)狀態(tài)，需要定，需要定義對應(yīng)義對應(yīng)每

8、個(gè)每個(gè)字母字母的的狀態(tài)轉(zhuǎn)換狀態(tài)轉(zhuǎn)換。DFA 這種有限狀態(tài)自動(dòng)機(jī)為這種有限狀態(tài)自動(dòng)機(jī)為確定的有確定的有限狀態(tài)自動(dòng)機(jī)限狀態(tài)自動(dòng)機(jī)DFA。例3-1定義定義DFA為：為： DFA=(q0,q1,0,1,q0,q0)其中其中：的表示的表示：函數(shù)形式函數(shù)形式(q0，0)=q1(q0，1)=q1(q1，0)= q1(q1，1)= q0的表示的表示：狀態(tài)矩陣：狀態(tài)矩陣 Q 0q01q1q1q1q1q0的表示的表示:狀態(tài)圖形式狀態(tài)圖形式狀態(tài)圖是一個(gè)狀態(tài)圖是一個(gè)有向有向、有、有循環(huán)循環(huán)的圖的圖一個(gè)節(jié)點(diǎn)表示一個(gè)狀態(tài)；一個(gè)節(jié)點(diǎn)表示一個(gè)狀態(tài)；若有若有(q，x)= q，則，則狀態(tài)狀態(tài)q到狀態(tài)到狀態(tài)q有一條有一條有向邊有向

9、邊，并，并用字母用字母x作標(biāo)記。作標(biāo)記。的表示 指向的狀態(tài)是開始狀態(tài)指向的狀態(tài)是開始狀態(tài) 兩個(gè)圓圈兩個(gè)圓圈代表代表接收狀態(tài)接收狀態(tài)；的表示：狀態(tài)圖狀態(tài)圖q11010q0 用狀態(tài)圖表示一個(gè)用狀態(tài)圖表示一個(gè)DFADFA 有向邊的有向邊的數(shù)目數(shù)目就是狀態(tài)轉(zhuǎn)換函數(shù)就是狀態(tài)轉(zhuǎn)換函數(shù)的個(gè)數(shù)。的個(gè)數(shù)。 默認(rèn)有默認(rèn)有(q q,)=,)=q q但但不是狀態(tài)轉(zhuǎn)換函數(shù)不是狀態(tài)轉(zhuǎn)換函數(shù) why?why?3.2 3.2 有限狀態(tài)自動(dòng)機(jī)接收語言有限狀態(tài)自動(dòng)機(jī)接收語言對于對于DFADFA，給定串，給定串w=xw=x1 1x x2 2xxn n 初始時(shí)，初始時(shí)， DFADFA處于開始狀態(tài)處于開始狀態(tài)q q0 0 從左到右逐個(gè)

10、字符地掃描串從左到右逐個(gè)字符地掃描串w w 在在(q(q0 0，x x1 1)= q)= q1 1的作用下的作用下 DFADFA處于狀態(tài)處于狀態(tài)q q1 1 在在(q(q1 1，x x2 2)=q)=q2 2的的作用下的的作用下 DFADFA處于狀態(tài)處于狀態(tài)q q2 2 當(dāng)將串當(dāng)將串w w掃描結(jié)束掃描結(jié)束后，后， 若若DFADFA處于某一個(gè)處于某一個(gè)接收狀態(tài)接收狀態(tài)， 則有限狀態(tài)自動(dòng)機(jī)能夠則有限狀態(tài)自動(dòng)機(jī)能夠接收接收串串w w對于對于可接收串可接收串DFADFA從從開始狀態(tài)開始狀態(tài)開始，在掃描開始，在掃描串串的的過程中，過程中， 狀態(tài)逐個(gè)地變化狀態(tài)逐個(gè)地變化, ,串掃描結(jié)束后，串掃描結(jié)束后，

11、處于處于某個(gè)某個(gè)接收狀態(tài)接收狀態(tài)。對于對于不可接收串不可接收串DFADFA從從開始狀態(tài)開始狀態(tài)開始，在掃描開始，在掃描串串的的過程中，過程中， 狀態(tài)逐個(gè)地變化狀態(tài)逐個(gè)地變化, ,串掃描結(jié)束后，串掃描結(jié)束后， 處于處于某個(gè)某個(gè)非接收狀態(tài)非接收狀態(tài)。對于字母表對于字母表上的上的DFADFA 能夠接收的所有串的集合，就是能夠接收的所有串的集合，就是DFADFA能接收的語言，記為能接收的語言，記為L(DFA)L(DFA) 也稱為有限狀態(tài)語言（也稱為有限狀態(tài)語言（FSLFSL）思考思考如何如何形式化形式化定義定義L(DFA)L(DFA)? ?定義3-4 擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù)擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù)給定給定DFA

12、DFA，擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù)，擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù) * *：Q Q* *QQ 即即 * *(q,(q,w w)=q)=q即即DFADFA在一個(gè)狀態(tài)在一個(gè)狀態(tài)q q時(shí)，掃描串時(shí)，掃描串w w后后到達(dá)唯一到達(dá)唯一確定確定的狀態(tài)的狀態(tài)qq遞歸擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù) * *( (q q, ,)=)=q q * *(q,(q,a a)=(q,a)=(q,a) 其中其中a a對于串對于串w=w=a a（+ +）* *（q q， w w） = =* *(q(q，a a） = =( (* *(q,(q,),),a a) )或者或者 對于串對于串w= w= a a * *(q(q，w w) ) = =* *(q(q，a

13、 a) ) = =* *( (q(q，a a),),) )定義定義3-6 DFA3-6 DFA接收的語言接收的語言DFA=(Q,qDFA=(Q,q0 0，F(xiàn))F)接收的語言接收的語言 L(DFA)=w| L(DFA)=w|* *(q(q0 0,w),w)FF思考思考如何描述如何描述 在某個(gè)在某個(gè)時(shí)刻時(shí)刻，DFA所處的情況？所處的情況？定義定義3-7 DFA3-7 DFA的瞬時(shí)描述（格局）的瞬時(shí)描述（格局）格局是一個(gè)二元式：格局是一個(gè)二元式：q qy y q q是是DFADFA當(dāng)前狀態(tài)當(dāng)前狀態(tài) y y是輸入帶上還沒有被掃描到的串是輸入帶上還沒有被掃描到的串 讀頭將掃描讀頭將掃描y y串的第串的第

14、1 1個(gè)字母個(gè)字母 在掃描串的過程中，格局在發(fā)在掃描串的過程中，格局在發(fā)生轉(zhuǎn)換生轉(zhuǎn)換( (改變改變) ) 格局的格局的( (一次一次) )轉(zhuǎn)換的原因是由轉(zhuǎn)換的原因是由于于函數(shù)函數(shù)的的( (一次一次) )作用作用 如果當(dāng)前格局為：如果當(dāng)前格局為：q qa ar r 有有函數(shù)：函數(shù)：(q(q，a)= qa)= q 則下一格局為：則下一格局為： qrqr 格局的轉(zhuǎn)換可以記為：格局的轉(zhuǎn)換可以記為：qar qar = qr qrDFA的特殊格局初始格局為：初始格局為： q q0 0w w接收格局為：接收格局為： q qf f其中，其中，q qf f是某個(gè)接收狀態(tài)是某個(gè)接收狀態(tài) 使用使用=* *代表格局的

15、代表格局的任意次任意次轉(zhuǎn)換轉(zhuǎn)換使用使用=+ +代表格局的代表格局的多次多次轉(zhuǎn)換轉(zhuǎn)換可以使用可以使用格局的轉(zhuǎn)換格局的轉(zhuǎn)換方式定義方式定義FSLFSLDFADFA接收的語言接收的語言 L(DFA)=L(DFA)= w|q w|q0 0w=w=* *q qf f；ww* *且且q qf fFF定義3-8 DFA停機(jī)DFA將輸入串掃描結(jié)束時(shí)將輸入串掃描結(jié)束時(shí) (自動(dòng)自動(dòng))停機(jī)停機(jī)這是這是DFA唯一的停機(jī)情況唯一的停機(jī)情況注意1：DFA將輸入串掃描結(jié)束停機(jī)時(shí)，將輸入串掃描結(jié)束停機(jī)時(shí)， 如果如果DFA處于某一個(gè)處于某一個(gè)接收狀態(tài)接收狀態(tài)， 則表示接收整個(gè)輸入串；則表示接收整個(gè)輸入串； 反之，則表示反之，則

16、表示不接收不接收整個(gè)輸入串整個(gè)輸入串;注意2： 對于狀態(tài)對于狀態(tài)q,如果如果不能接收不能接收字母字母a 則將狀態(tài)轉(zhuǎn)換到一個(gè)特殊的狀態(tài)：則將狀態(tài)轉(zhuǎn)換到一個(gè)特殊的狀態(tài)：陷阱狀態(tài)陷阱狀態(tài)qt 陷阱陷阱狀態(tài)狀態(tài)qt不能夠改變?yōu)槠渌麪顟B(tài)不能夠改變?yōu)槠渌麪顟B(tài) 即即 對于對于a (qt ，a)=qtqt不能夠不能夠接收接收任意字母任意字母構(gòu)造構(gòu)造DFA，分別接收語言，分別接收語言、0、01、 0* *、 0+ +(0+1)* *、(0+1)+ +01* *0 、1 * *00(0+1) * *(0+1) * *00(0+1) * *0(0+1) * *10(0+1) * *0+1(0+1)* *1 定理3-

17、1 每個(gè)每個(gè)FSLFSL都是一個(gè)都是一個(gè)右線性語言右線性語言分析：分析： 已知已知 接收接收FSL的的DFA 需要需要 構(gòu)造構(gòu)造RLG，使得使得 L(RLG)=FSL等價(jià)等價(jià)思路思路DFA最重要的部分是狀態(tài)轉(zhuǎn)換函數(shù)最重要的部分是狀態(tài)轉(zhuǎn)換函數(shù)文法最重要的部分是產(chǎn)生式文法最重要的部分是產(chǎn)生式狀態(tài)轉(zhuǎn)換函數(shù)和產(chǎn)生式是狀態(tài)轉(zhuǎn)換函數(shù)和產(chǎn)生式是等價(jià)的等價(jià)的可以將可以將狀態(tài)轉(zhuǎn)換函數(shù)狀態(tài)轉(zhuǎn)換函數(shù)改造改造為產(chǎn)生式為產(chǎn)生式等價(jià)等價(jià)思路思路狀態(tài)轉(zhuǎn)換函數(shù)和產(chǎn)生式的狀態(tài)轉(zhuǎn)換函數(shù)和產(chǎn)生式的等價(jià)等價(jià)作用作用 (q, a)=q AaB 接收接收a 產(chǎn)生產(chǎn)生a 狀態(tài)狀態(tài)變化變化 非終結(jié)符號非終結(jié)符號變化變化結(jié)論結(jié)論:DFA:DF

18、A狀態(tài)狀態(tài)等價(jià)于文法等價(jià)于文法非終結(jié)符非終結(jié)符 狀態(tài)轉(zhuǎn)換函數(shù)等價(jià)于產(chǎn)生式狀態(tài)轉(zhuǎn)換函數(shù)等價(jià)于產(chǎn)生式 構(gòu)造文法的基本思路：構(gòu)造文法的基本思路：l將將的的DFA的的狀態(tài)狀態(tài)當(dāng)作是當(dāng)作是RLG的的非終結(jié)非終結(jié)符符(開始狀態(tài)就是開始符號開始狀態(tài)就是開始符號)l對于某個(gè)句子：對于某個(gè)句子： DFA通過狀態(tài)的改變，逐步通過狀態(tài)的改變，逐步（自左向（自左向右）右）接收接收句子的每個(gè)字母；句子的每個(gè)字母； RLG通過非終結(jié)符號的改變通過非終結(jié)符號的改變，逐步，逐步（自左向右）（自左向右）產(chǎn)生產(chǎn)生句子的每個(gè)字母。句子的每個(gè)字母。思考思考 DFA的接收狀態(tài)的作用的接收狀態(tài)的作用證明假設(shè)假設(shè)L L是字母表是字母表上的

19、上的FSLFSL，則，則 L=L(DFA) L=L(DFA) DFA= DFA=（Q Q，q q0 0，F(xiàn) F） 構(gòu)造構(gòu)造右線性右線性文法文法G=(,G=(,Q,Q,q q0 0，P P） 其中其中P P為：為： qaqqaq|(q|(q，a)=qa)=q U U qaqa| |(q(q，a)Fa)F 特別，若特別，若q q0 0是接收狀態(tài)，則是接收狀態(tài)，則 q q0 0對于句子w=x1x2xnDFA： 則文法有則文法有(q0, x1)=q1 q0 x1q1(q1, x2)=q2 q1x2q2 (qn-2,xn-1)=qn-1 qn-2xn-1qn-1(qn-1, xn)=qn qn-1xnq

20、n 或或 qn-1xn 所以 DFA 文法文法*(q，)=q q=*q*(q0， w)F q0=*w注意：注意：陷進(jìn)狀態(tài)在文法中是無用非終結(jié)符陷進(jìn)狀態(tài)在文法中是無用非終結(jié)符例例3-2 DFA與文法的轉(zhuǎn)換與文法的轉(zhuǎn)換FSLFSL=(0,1)1=(0,1)1* *00* * 接收該語言的接收該語言的DFADFA為：為：q11001q0構(gòu)造構(gòu)造正則正則文法產(chǎn)生該語言：文法產(chǎn)生該語言： q00q1|1q1| q10q0|1q1| 0定理定理3-2FSL對對補(bǔ)補(bǔ)運(yùn)算封閉運(yùn)算封閉證明：設(shè)設(shè)L L1 1是是上的上的FSL,FSL,且且L L1 1=L(DFA=L(DFA1 1) )， DFA DFA1 1=

21、 =（Q Q，q q0 0，F(xiàn) F）構(gòu)造構(gòu)造 DFA DFA2 2= =（Q Q，q q0 0，Q Q）DFADFA2 2接收的語言是接收的語言是 L L1 1的對應(yīng)的全集的對應(yīng)的全集, ,即即* *構(gòu)造構(gòu)造 DFA DFA3 3=(Q=(Q，q q0 0，Q-FQ-F) ) L L3 3=L(DFA=L(DFA3 3) ) L L3 3接收的語言是接收的語言是L L1 1( (關(guān)于關(guān)于* *) )的的補(bǔ)補(bǔ) L L3 3也是也是FSLFSL語言。語言。注意此時(shí)的此時(shí)的DFADFA1 1的的函數(shù)的個(gè)數(shù)為函數(shù)的個(gè)數(shù)為 |Q|Q|* *|基本的等價(jià)替換基本的等價(jià)替換l對于狀態(tài)轉(zhuǎn)換圖，有基本的等價(jià)替換

22、對于狀態(tài)轉(zhuǎn)換圖，有基本的等價(jià)替換l變換為00,113.3 DFA3.3 DFA接收語言的例子接收語言的例子 構(gòu)造構(gòu)造DFA，接收語言接收語言 L=ab 基本結(jié)構(gòu)（接收基本句子）基本結(jié)構(gòu)（接收基本句子）q1abq0q2增加增加陷阱狀態(tài)陷阱狀態(tài)后的后的DFADFAq1abq0qtbaa, ba, bq2思考思考1 1 如果將該如果將該DFADFA的的所有狀態(tài)所有狀態(tài)都設(shè)置都設(shè)置為為接收狀態(tài)接收狀態(tài)( (包括陷阱狀態(tài)包括陷阱狀態(tài)) )， 接收的語言是接收的語言是？ 思考思考2 2 如果將該自動(dòng)機(jī)的接收狀態(tài)和非如果將該自動(dòng)機(jī)的接收狀態(tài)和非接收接收狀態(tài)對調(diào)狀態(tài)對調(diào) 接收的語言是接收的語言是？例3-4構(gòu)造

23、DFA接收語言接收語言L=L=x000yx000y|x,y0,1|x,y0,1* * 分析 該語言的特點(diǎn)是該語言的特點(diǎn)是 語言中的每個(gè)串都包含連續(xù)的語言中的每個(gè)串都包含連續(xù)的3 3個(gè)個(gè)0 0（即每個(gè)串都包含子串（即每個(gè)串都包含子串000000） 因此，對于任何輸入串，有限狀因此，對于任何輸入串，有限狀態(tài)自動(dòng)機(jī)的任務(wù)就是要態(tài)自動(dòng)機(jī)的任務(wù)就是要檢查檢查該輸入該輸入串中是否存在子串串中是否存在子串000000， 一旦發(fā)現(xiàn)輸入串包含有一旦發(fā)現(xiàn)輸入串包含有000000，則，則表示表示整個(gè)輸入串整個(gè)輸入串是是句子句子。因此，在確認(rèn)輸入串包含因此，在確認(rèn)輸入串包含000000后，后， 就可以逐一地讀入就可以

24、逐一地讀入000000后面的全后面的全部字符，并接收該輸入串。部字符，并接收該輸入串。思考思考問題的關(guān)鍵是問題的關(guān)鍵是？ 如何如何發(fā)現(xiàn)發(fā)現(xiàn)子串子串000000。由于字符是逐一讀入的，當(dāng)從輸入由于字符是逐一讀入的，當(dāng)從輸入串中讀入一個(gè)串中讀入一個(gè)0 0時(shí)，時(shí)， 它它有可能有可能是是000000的的第第1 1個(gè)個(gè)0 0， 需要需要記住記住已經(jīng)出現(xiàn)過一個(gè)已經(jīng)出現(xiàn)過一個(gè)0 0；如果緊接著讀入的是字符如果緊接著讀入的是字符1 1，則剛讀入的則剛讀入的0 0就不是就不是000000的第的第1 1個(gè)個(gè)0 0需要需要重新尋找重新尋找000000子串的第子串的第1 1個(gè)個(gè)0 0；如果緊接著讀入的還是如果緊接著讀

25、入的還是0 0，它，它有可能有可能是是000000的的第第2 2個(gè)個(gè)0 0， 也需要也需要記住記住這個(gè)這個(gè)0 0， 繼續(xù)讀入字符，若是繼續(xù)讀入字符，若是0 0，則，則發(fā)現(xiàn)發(fā)現(xiàn)000000否則，需要否則，需要重新重新尋找尋找000000。初始狀態(tài)：初始狀態(tài)：q q0 0接收接收0 0，到達(dá)狀態(tài)，到達(dá)狀態(tài)q q1 1接收接收00 ,00 ,到達(dá)狀態(tài)到達(dá)狀態(tài)q q2 2接收接收000,000,到達(dá)狀態(tài)到達(dá)狀態(tài)q q3 3因此，因此，基本的基本的狀態(tài)轉(zhuǎn)移函數(shù)為：狀態(tài)轉(zhuǎn)移函數(shù)為： (q(q0 0，0)=q0)=q1 1 (q (q1 1，0)=q0)=q2 2 (q (q2 2，0)=q0)=q3 3用

26、于接收基本句子用于接收基本句子000000接收接收000000的狀態(tài)圖的狀態(tài)圖q0000q1q2q3其他狀態(tài)轉(zhuǎn)移函數(shù)為：其他狀態(tài)轉(zhuǎn)移函數(shù)為： (q(q0 0，1)=q1)=q0 0 期待期待0 0的出現(xiàn)的出現(xiàn) (q(q1 1，1)=q1)=q0 0 重新尋找重新尋找000000 (q(q2 2，1)=q1)=q0 0 重新尋找重新尋找000000 (q (q3 3，0)=q0)=q3 3 掃描后續(xù)字符掃描后續(xù)字符 (q (q3 3，1)=q1)=q3 3 掃描后續(xù)字符掃描后續(xù)字符狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移圖q00111000,1q1q2q3思考思考如果需要接收語言如果需要接收語言 L 如何修改有限狀態(tài)

27、自動(dòng)機(jī)如何修改有限狀態(tài)自動(dòng)機(jī)? 思路：思路：考慮考慮開始狀態(tài)開始狀態(tài)的作用的作用思考思考:如果如果 DFA的的開始狀態(tài)開始狀態(tài)只負(fù)責(zé)接收輸入只負(fù)責(zé)接收輸入串的第一個(gè)字母；串的第一個(gè)字母； 文法的文法的開始符號開始符號只負(fù)責(zé)串的推導(dǎo)只負(fù)責(zé)串的推導(dǎo)的開始；的開始； 優(yōu)點(diǎn)是？優(yōu)點(diǎn)是？狀態(tài)圖為狀態(tài)圖為10qs01000,1q1q2q3q011例3-5構(gòu)造DFA 接收語言接收語言 L= L=x x001001y y|x|x，y0y0，11* * 分析： 對于任何輸入串，對于任何輸入串，DFADFA的任務(wù)就的任務(wù)就是要檢查該輸入串中是否存在是要檢查該輸入串中是否存在001001 初始狀態(tài)：初始狀態(tài)：q q

28、0 0q q1 1 已接收已接收0 0q q2 2 已接收已接收00 00 q q3 3 已接收已接收001 001 q2q1q0狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移圖01q31010,10例3-6 構(gòu)造DFA接收語言接收語言L=L=x x000000|x0|x0，11* * q2q3q1q001110001例3-7構(gòu)造DFA接收語言接收語言L=L= x x000000 x x001001其中，其中，x0 x0，11* *q2q1q001q310001q4101例3-8構(gòu)造DFA接收語言接收語言L=L=0 02k+3m2k+3m|m,k=0|m,k=0 實(shí)際上：實(shí)際上： 2k+3m2k+3m可以表示任意的可以表

29、示任意的非負(fù)整數(shù)非負(fù)整數(shù)( (除除1 1外外) ) 該語言為該語言為0*-0 狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移圖000q1q2q0思考：構(gòu)造DFA接收語言接收語言L=0L=02k+3m2k+3m| |m,k0m,k0 考查題考查題1 1 例3-9構(gòu)造DFA 接收接收00，11上的語言，該語言的上的語言，該語言的 每個(gè)句子以每個(gè)句子以0 0開頭，以開頭，以1 1結(jié)尾。結(jié)尾。 狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移圖010q1q210qt0,11q0例3-10 構(gòu)造DFA接收接收00，11上的語言，該語言的每上的語言，該語言的每個(gè)字符串個(gè)字符串 不包含不包含0000子串子串( (語言允許語言允許 ) )000,1qtq1q0q21

30、011或或000,1qtq1q011構(gòu)造DFA接收接收00，11上的語言，上的語言， 該語言的每個(gè)字符串不包含該語言的每個(gè)字符串不包含0000（語言不允許語言不允許 ）例3-11構(gòu)造DFA接收接收00，1 1，22上的語言，上的語言， 該語言的每個(gè)字符串代表的數(shù)字該語言的每個(gè)字符串代表的數(shù)字能整除能整除3 3。分析 如果一個(gè)十進(jìn)制整數(shù)的所有位的如果一個(gè)十進(jìn)制整數(shù)的所有位的數(shù)字的和數(shù)字的和能夠整除能夠整除3 3，那么，那么， 這個(gè)十進(jìn)制整數(shù)就能夠整除這個(gè)十進(jìn)制整數(shù)就能夠整除3 3；一個(gè)十進(jìn)制整數(shù)除以一個(gè)十進(jìn)制整數(shù)除以3 3，余數(shù)只能，余數(shù)只能是是1 1、2 2和和0 0； 將整數(shù)當(dāng)作一個(gè)字符串，

31、從左到將整數(shù)當(dāng)作一個(gè)字符串，從左到右逐一地讀入；右逐一地讀入； 使用使用3 3個(gè)狀態(tài)個(gè)狀態(tài)分別代表已讀入的分別代表已讀入的數(shù)字的數(shù)字的和和除以除以3 3的的余數(shù)情況余數(shù)情況：( (即讀入的整數(shù)對即讀入的整數(shù)對3 3的余數(shù)情況）的余數(shù)情況）q q0 0：已已讀入的整數(shù)除以讀入的整數(shù)除以3 3，余數(shù)為余數(shù)為0 0q q1 1：已已讀入的整數(shù)除以讀入的整數(shù)除以3 3，余數(shù)為余數(shù)為1 1q q2 2：已已讀入的整數(shù)除以讀入的整數(shù)除以3 3，余數(shù)為余數(shù)為2 2思考思考 已知已知qi(i =0,1,2)，x=0,1,2 應(yīng)該如何確定應(yīng)該如何確定 j？ qiqjx 掃描子串掃描子串w w后后, ,處于某個(gè)狀

32、態(tài)處于某個(gè)狀態(tài)q qi i，讀入當(dāng)前數(shù)字讀入當(dāng)前數(shù)字, , 狀態(tài)轉(zhuǎn)換情況為狀態(tài)轉(zhuǎn)換情況為q0l在此狀態(tài)讀入在此狀態(tài)讀入0 0，引導(dǎo)，引導(dǎo)DFADFA到達(dá)下到達(dá)下一狀態(tài)的輸入串為一狀態(tài)的輸入串為w0w0, ,lw0w0的各位數(shù)字和除以的各位數(shù)字和除以3 3，余數(shù)為余數(shù)為0 0。所以，所以， DFADFA在在q q0 0狀態(tài)讀入狀態(tài)讀入0 0，應(yīng)該，應(yīng)該繼續(xù)保持繼續(xù)保持q q0 0狀態(tài)；狀態(tài)；q0l在此狀態(tài)讀入在此狀態(tài)讀入1 1，引導(dǎo)，引導(dǎo)DFADFA到達(dá)下到達(dá)下一狀態(tài)的輸入串為一狀態(tài)的輸入串為w1w1，w1w1的各位的各位數(shù)字和除以數(shù)字和除以3 3，余數(shù)為余數(shù)為1 1。l所以，所以， DFADF

33、A在在q q0 0狀態(tài)讀入狀態(tài)讀入1 1，應(yīng)該，應(yīng)該到達(dá)到達(dá)q q1 1狀態(tài)；狀態(tài)； q0l在此狀態(tài)讀入在此狀態(tài)讀入2 2，引導(dǎo)，引導(dǎo)DFADFA到達(dá)下到達(dá)下一狀態(tài)的輸入串為一狀態(tài)的輸入串為w2w2，w2w2的各位的各位數(shù)字和除以數(shù)字和除以3 3，余數(shù)為余數(shù)為2 2。l所以，所以， DFADFA在在q q0 0狀態(tài)讀入狀態(tài)讀入2 2，應(yīng)該，應(yīng)該到達(dá)到達(dá)q q2 2狀態(tài)；狀態(tài)； l 0 0 1 2 1 2 2 1 0 q0 q1 q2 存在的問題 接收的串包括以接收的串包括以0開始開始的數(shù)字串；的數(shù)字串； 還能夠接收還能夠接收空串空串思考如何進(jìn)行改進(jìn)，使得如何進(jìn)行改進(jìn)，使得 接收的串不能以接收的

34、串不能以0開始，開始， 不能接收不能接收空串空串。定義3-9 set集合對于狀態(tài)對于狀態(tài)q，能將，能將DFA從從q0轉(zhuǎn)換到轉(zhuǎn)換到q狀態(tài)的所有字符串的集合為：狀態(tài)的所有字符串的集合為： set(q) set(q)=w|w=w|w* *, ,* *(q(q0 0,w)=q,w)=q 則則有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī)DFADFA接收的接收的語言語言可以定義為：可以定義為： L(DFA)= set(q)其中：其中： q qFF按狀態(tài)進(jìn)行劃分按狀態(tài)進(jìn)行劃分對于對于DFADFA，可以定義關(guān)系可以定義關(guān)系R R 若若 x,yx,y* * ，qQ qQ 則則 xRy xRy 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) xset(q),

35、yset(q)xset(q),yset(q) 即即R=(x,y)|xset(q),yset(q)xset(q),yset(q) ；qQqQ 是* *上的二元關(guān)系上的二元關(guān)系 該關(guān)系是集合該關(guān)系是集合* *上的一個(gè)上的一個(gè)等價(jià)等價(jià)關(guān)系關(guān)系，利用該關(guān)系，利用該關(guān)系， 可以將可以將* *劃分為不多于劃分為不多于|Q|Q|個(gè)的個(gè)的等價(jià)類等價(jià)類。 DFA DFA可以按照語言的特點(diǎn)給出字可以按照語言的特點(diǎn)給出字母表母表* *的一個(gè)的一個(gè)劃分劃分，這種劃分相，這種劃分相當(dāng)于當(dāng)于* *上的一個(gè)等價(jià)分類。上的一個(gè)等價(jià)分類。 DFA DFA每個(gè)每個(gè)狀態(tài)狀態(tài)對應(yīng)著一個(gè)對應(yīng)著一個(gè)等價(jià)類等價(jià)類 利用一個(gè)利用一個(gè)狀態(tài)狀態(tài)

36、去表示一個(gè)去表示一個(gè)等價(jià)等價(jià)類類是構(gòu)造是構(gòu)造DFADFA的一條的一條有效思路有效思路。例3-12構(gòu)造DFA,接收 0,1,2,4,5,6,7,8,9 0,1,2,4,5,6,7,8,9上的語言，上的語言， 該語言的每個(gè)字符串代表的數(shù)字該語言的每個(gè)字符串代表的數(shù)字能整除能整除3 3。 仍然仍然只使用只使用3 3個(gè)狀態(tài)分別代表已個(gè)狀態(tài)分別代表已經(jīng)讀入的整數(shù)字的和除以經(jīng)讀入的整數(shù)字的和除以3 3的不同的不同的余數(shù)的情況：的余數(shù)的情況：狀態(tài)與對應(yīng)的等價(jià)類狀態(tài)與對應(yīng)的等價(jià)類q q0 0：余數(shù)為余數(shù)為0 0的輸入串的等價(jià)類的輸入串的等價(jià)類q q1 1：余數(shù)為余數(shù)為1 1的輸入串的等價(jià)類的輸入串的等價(jià)類q

37、q2 2：余數(shù)為余數(shù)為2 2的輸入串的等價(jià)類的輸入串的等價(jià)類 0,3,6,9 0,3,6,9 1,4,7 2,5,8 1,4,7 2,5,8 2,5,8 1,4,7 0,3,6,9 q0 q1 q2 例3-13構(gòu)造DFA,接收00，11上的語言，該語言的每個(gè)字上的語言，該語言的每個(gè)字符串擋成符串擋成二進(jìn)制數(shù)二進(jìn)制數(shù)時(shí)，時(shí)， 代表的數(shù)字能代表的數(shù)字能整除整除3 3。 DFA DFA的每個(gè)狀態(tài)對應(yīng)一個(gè)等價(jià)類的每個(gè)狀態(tài)對應(yīng)一個(gè)等價(jià)類 利用一個(gè)狀態(tài)去表示一個(gè)等價(jià)類利用一個(gè)狀態(tài)去表示一個(gè)等價(jià)類 除以除以3 3的的余數(shù)只能為余數(shù)只能為0 0、1 1和和2 2q q0 0：余數(shù)為余數(shù)為0 0的輸入串的等價(jià)類

38、；的輸入串的等價(jià)類；q q1 1：余數(shù)為余數(shù)為1 1的輸入串的等價(jià)類；的輸入串的等價(jià)類；q q2 2：余數(shù)為余數(shù)為2 2的輸入串的等價(jià)類；的輸入串的等價(jià)類；不能接收空串，所以，不能接收空串，所以，還需要一個(gè)開始狀態(tài)還需要一個(gè)開始狀態(tài)q qS S人們習(xí)慣人們習(xí)慣使用十進(jìn)制數(shù)使用十進(jìn)制數(shù)w=x1x2x3xn(x1x2x3xn)2=(x1*2n-1+ x2*2n-2+ xn-1*2+xn)10當(dāng)串長度增加當(dāng)串長度增加1時(shí)：時(shí)：(x1x2x3xnxn+1)2= (x1*2n+ x2*2n-1+ xn-1*22+ xn*2+xn+1)10 =(2*(w)10+xn+1)10(w)10=3n+i(wx)1

39、0 =(2*(w)10+x)10 =6*n+2*i+x實(shí)際上實(shí)際上 2*i+x 對對3的余數(shù)就是的余數(shù)就是wx對對3的余數(shù)的余數(shù)設(shè)設(shè)w是當(dāng)前是當(dāng)前已經(jīng)讀入已經(jīng)讀入的輸入串；的輸入串；qS：開始狀態(tài)：開始狀態(tài)讀入讀入0時(shí)，進(jìn)入狀態(tài)時(shí)，進(jìn)入狀態(tài)q0讀入讀入1時(shí)，進(jìn)入狀態(tài)時(shí)，進(jìn)入狀態(tài)q1q0 能引導(dǎo)能引導(dǎo)DFA到達(dá)此狀態(tài)的到達(dá)此狀態(tài)的w除以除以3余數(shù)為余數(shù)為0，因此，因此 (w)10=3n+0q0 在此狀態(tài)讀入在此狀態(tài)讀入0，引導(dǎo)，引導(dǎo)DFA到達(dá)下到達(dá)下一狀態(tài)的輸入串為一狀態(tài)的輸入串為w0，則，則 (w0)10=2(3n+0)+0=32n+0 表明表明w0也屬于也屬于q0對應(yīng)的等價(jià)類。對應(yīng)的等價(jià)類。

40、所以，所以，DFA在在q0狀態(tài)讀入狀態(tài)讀入0，應(yīng)該，應(yīng)該繼續(xù)保持繼續(xù)保持q0狀態(tài)；狀態(tài)；q0 在此狀態(tài)讀入在此狀態(tài)讀入1，引導(dǎo)，引導(dǎo)DFA到達(dá)到達(dá)下一狀態(tài)的輸入串為下一狀態(tài)的輸入串為w1，則，則 (w1)10=2(3n+0)+1=32n+1 表明表明w1屬于屬于q1對應(yīng)的等價(jià)類。所以，對應(yīng)的等價(jià)類。所以， DFA在在q0狀態(tài)讀入狀態(tài)讀入1，應(yīng)該到達(dá)，應(yīng)該到達(dá)q1狀狀態(tài)；態(tài)； q1 能引導(dǎo)能引導(dǎo)DFA到達(dá)此狀態(tài)的到達(dá)此狀態(tài)的w除除以以3余數(shù)為余數(shù)為1，因此，因此 (w)10=3n+1q1 在此狀態(tài)讀入在此狀態(tài)讀入0，引導(dǎo)，引導(dǎo)DFA到達(dá)下到達(dá)下一狀態(tài)的輸入串為一狀態(tài)的輸入串為w0，則，則 (w0

41、)10=2(3n+1)+0=32n+2 表明表明w0屬于屬于q2對應(yīng)的等價(jià)類。所對應(yīng)的等價(jià)類。所以，以， DFA在在q1狀態(tài)讀入狀態(tài)讀入0，應(yīng)該，應(yīng)該到達(dá)到達(dá)q2狀態(tài)；狀態(tài)；q1 在此狀態(tài)讀入在此狀態(tài)讀入1，引導(dǎo)，引導(dǎo)DFA到達(dá)下到達(dá)下一狀態(tài)的輸入串為一狀態(tài)的輸入串為w1，則，則 (w1)10=2(3n+1)+1=32n+3 表明表明w1屬于屬于q0對應(yīng)的等價(jià)類。所對應(yīng)的等價(jià)類。所以，以， DFA在在q1狀態(tài)讀入狀態(tài)讀入1，應(yīng)該到，應(yīng)該到達(dá)達(dá)q0狀態(tài)；狀態(tài)；q2 能引導(dǎo)能引導(dǎo)DFA到達(dá)此狀態(tài)的到達(dá)此狀態(tài)的w除以除以3余數(shù)為余數(shù)為2，因此，因此， (w)10=3n+2q2 在此狀態(tài)讀入在此狀態(tài)讀

42、入0，引導(dǎo)，引導(dǎo)DFA到達(dá)下到達(dá)下一狀態(tài)的輸入串為一狀態(tài)的輸入串為w0，則，則 (w0)10=2(3n+2)+0=32n+4 表明表明w0屬于屬于q1對應(yīng)的等價(jià)類。所對應(yīng)的等價(jià)類。所以，以，DFA在在q2狀態(tài)讀入狀態(tài)讀入0，應(yīng)該到，應(yīng)該到達(dá)達(dá)q1狀態(tài)；狀態(tài)；q2 在此狀態(tài)讀入在此狀態(tài)讀入1，引導(dǎo)自動(dòng)機(jī)到達(dá)，引導(dǎo)自動(dòng)機(jī)到達(dá)下一狀態(tài)的輸入串為下一狀態(tài)的輸入串為w1，則，則(w1)10=2(3n+2)+1=32n+5 表明表明w1屬于屬于q2對應(yīng)的等價(jià)類。所對應(yīng)的等價(jià)類。所以，自動(dòng)機(jī)在以，自動(dòng)機(jī)在q2狀態(tài)讀入狀態(tài)讀入1，繼續(xù)，繼續(xù)保持保持q2狀態(tài)；狀態(tài)；狀態(tài)圖狀態(tài)圖 0 0 1 1 1 1 0 0

43、qS q1 q2 q0 例3-14構(gòu)造DFA，接收 0，1上的語言，該語言的每個(gè)字上的語言，該語言的每個(gè)字符串為符串為二進(jìn)制數(shù)二進(jìn)制數(shù)時(shí)，時(shí)， 代表的數(shù)字能被代表的數(shù)字能被5整除。整除。分析：分析：l對對5的余數(shù)只能為的余數(shù)只能為0、1、2、3和和4l使用使用5個(gè)狀態(tài)個(gè)狀態(tài)分別代表已經(jīng)讀入的數(shù)字除分別代表已經(jīng)讀入的數(shù)字除以以5的不同的余數(shù)的等價(jià)類：的不同的余數(shù)的等價(jià)類：lqi：已經(jīng)讀入的數(shù)除以：已經(jīng)讀入的數(shù)除以5，余數(shù)為，余數(shù)為i的輸入的輸入串的等價(jià)類；串的等價(jià)類；l其中其中 i=0,1,2,3,4l不能接收空串，需要一個(gè)開始狀態(tài)不能接收空串，需要一個(gè)開始狀態(tài)qS 0 0 1 1 0 1 0

44、0 1 1 1 0 0 qS q1 q0 q3 q2 q4 例3-15構(gòu)造DFA，接收 1,2,3上的語言，該語言的每上的語言，該語言的每個(gè)字符串擋成個(gè)字符串擋成十進(jìn)制數(shù)十進(jìn)制數(shù)時(shí)，時(shí)， 代表的數(shù)字能被代表的數(shù)字能被4整除。整除。 3 1 1 2 2 1 1 2 2 3 3 3 1 2 3 qS q3 q0 q2 q1 思考：思考：構(gòu)造DFA，接收 0 0，1,21,2，3 3，4 4，5 5，6 6，7 7，8 8，99上的語言，該語言的每個(gè)字符串上的語言，該語言的每個(gè)字符串擋成擋成十進(jìn)制十進(jìn)制數(shù)時(shí)，數(shù)時(shí)， 代表的數(shù)字能整除代表的數(shù)字能整除7 7 。l總結(jié)：總結(jié)：構(gòu)造DFA，接收=x=x1

45、1, x, x2 2,x,x3 3, ,x xm m 上的語言上的語言 該語言的每個(gè)字符串擋成該語言的每個(gè)字符串擋成basebase進(jìn)進(jìn)制數(shù)制數(shù)時(shí)時(shí) 代表的數(shù)字能整除代表的數(shù)字能整除N N 或或 代表的數(shù)字對代表的數(shù)字對N N的余數(shù)為的余數(shù)為K K分析： 對對N N的的余數(shù)余數(shù)只能為只能為0 0、1 1、2 2、3 3、和和N-1N-1 使用使用N N個(gè)狀態(tài)個(gè)狀態(tài)分別代表分別代表已經(jīng)讀入已經(jīng)讀入的串（當(dāng)作數(shù)）的串（當(dāng)作數(shù)）對對N N的不同的余數(shù)的不同的余數(shù)的等價(jià)類：的等價(jià)類：q q0 0：余數(shù)為：余數(shù)為0 0的輸入串的等價(jià)類；的輸入串的等價(jià)類； 該類數(shù)十進(jìn)制為該類數(shù)十進(jìn)制為N N* *n+0n

46、+0q q1 1：余數(shù)為：余數(shù)為1 1的輸入串的等價(jià)類；的輸入串的等價(jià)類；該類數(shù)十進(jìn)制為該類數(shù)十進(jìn)制為N N* *n+1n+1q q2 2：余數(shù)為：余數(shù)為2 2的輸入串的等價(jià)類；的輸入串的等價(jià)類；該類數(shù)十進(jìn)制為該類數(shù)十進(jìn)制為N N* *n+2n+2q qN-1N-1：余數(shù)為：余數(shù)為N-1N-1的輸入串的等價(jià)類；的輸入串的等價(jià)類；該類數(shù)十進(jìn)制為該類數(shù)十進(jìn)制為N N* *n+N-1n+N-1注意不能接收空串，不能接收空串， 還需要一個(gè)還需要一個(gè)開始狀態(tài)開始狀態(tài)q qS Sq qS S讀入讀入x x時(shí)，進(jìn)入對應(yīng)狀態(tài)時(shí)，進(jìn)入對應(yīng)狀態(tài)q qi i本質(zhì)本質(zhì) 已知已知qi(i =0，1，2，N-1) x=x

47、 x=x1 1, x, x2 2,x,x3 3, ,x xm m 應(yīng)該如何確定應(yīng)該如何確定 j？ qiqjxq qi i 已經(jīng)讀入的數(shù)為已經(jīng)讀入的數(shù)為w w，對應(yīng)余數(shù)為對應(yīng)余數(shù)為i i的輸入串的等價(jià)類；的輸入串的等價(jià)類； 該類數(shù)十進(jìn)制為該類數(shù)十進(jìn)制為N N* *n+in+i 當(dāng)前讀入的字符為當(dāng)前讀入的字符為x x；則；則wxwx表示表示的十進(jìn)制數(shù)為的十進(jìn)制數(shù)為(wx)10= base base* * (w)10 +x+x =base =base* *（N N* *n+in+i）+x+x = =N N* *basebase* *n+n+basebase* *i+xi+x 該數(shù)對于該數(shù)對于N N取

48、余數(shù)就是取余數(shù)就是basebase* *i+xi+x對于對于N N的余數(shù)，的余數(shù)， 若該余數(shù)為若該余數(shù)為j j， 則相應(yīng)的狀態(tài)就應(yīng)該從則相應(yīng)的狀態(tài)就應(yīng)該從q qi i變換為變換為q qj j其中其中 i=0i=0，1 1，2 2，N-1N-1。 x x = = xx1 1, x, x2 2,x,x3 3, ,x xm m 0, 10, 1， ，base-1base-1例3-16構(gòu)造DFA，接收 0 0，11上的語言上的語言 L= L=0 0n n1 1m m2 2k k|n,m,k=1|n,m,k=1 該語言的串的特點(diǎn)是，該語言的串的特點(diǎn)是，0 0在最前在最前面，面，1 1在中間，在中間，2

49、2在最后，在最后，0 0、1 1和和2 2不能交叉不能交叉，順序也，順序也不能顛倒不能顛倒。 0 0、1 1和和2 2的個(gè)數(shù)都至少為的個(gè)數(shù)都至少為1 1個(gè)；個(gè)； 需要需要4 4個(gè)狀態(tài)個(gè)狀態(tài)：q q0 0：開始狀態(tài)：開始狀態(tài), ,等待接收第等待接收第1 1個(gè)個(gè)0 0q q1 1：已經(jīng)已經(jīng)接收第接收第1 1個(gè)個(gè)0 0，負(fù)責(zé)負(fù)責(zé)接收可接收可能的多個(gè)能的多個(gè)0 0，等待等待接收第接收第1 1個(gè)個(gè)1 1；q q2 2：已經(jīng)接收第已經(jīng)接收第1 1個(gè)個(gè)1 1，負(fù)責(zé)接收可，負(fù)責(zé)接收可能的多個(gè)能的多個(gè)1 1，等待接收第，等待接收第1 1個(gè)個(gè)2 2；q q3 3：已經(jīng)接收第已經(jīng)接收第1 1個(gè)個(gè)2 2，負(fù)責(zé)接收可，

50、負(fù)責(zé)接收可能的多個(gè)能的多個(gè)2 2。狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移圖( (省略陷阱狀態(tài)省略陷阱狀態(tài)) )q0010122q1q2q3思考思考1補(bǔ)充陷阱狀態(tài)及對應(yīng)的狀態(tài)函數(shù)。補(bǔ)充陷阱狀態(tài)及對應(yīng)的狀態(tài)函數(shù)。思考思考2 DFADFA是否可以為是否可以為( (省略陷阱狀態(tài)省略陷阱狀態(tài)) )q0010122q1q2q3.4 .4 不確定的有限狀態(tài)自動(dòng)機(jī)不確定的有限狀態(tài)自動(dòng)機(jī)每個(gè)每個(gè)FSLFSL都是都是右線性語言右線性語言( (定理定理3-13-1) )問題問題 每個(gè)每個(gè)右線性語言右線性語言是不是一個(gè)是不是一個(gè)FSLFSL？ 例例接收語言接收語言aaaa，abab的的FAFA省略省略陷阱狀態(tài)陷阱狀態(tài)q1abq0q2aa

51、q3 該自動(dòng)機(jī)接收的語言該自動(dòng)機(jī)接收的語言L=aaL=aa，abab是右線性語言；是右線性語言； 但自動(dòng)機(jī)但自動(dòng)機(jī)不是不是DFADFA。(q(q0 0，a)=a)=qq1 1，q q2 2 即沒有到達(dá)確定的惟一的狀態(tài)。即沒有到達(dá)確定的惟一的狀態(tài)。 不確定的有限狀態(tài)自動(dòng)機(jī)不確定的有限狀態(tài)自動(dòng)機(jī)-NFANFA3.4.1不確定的有限狀態(tài)自動(dòng)機(jī)不確定的有限狀態(tài)自動(dòng)機(jī)定義定義3-10 NFA是一個(gè)五元式，是一個(gè)五元式， NFA =（Q，Q0，F(xiàn)）其中：其中： Q 是一個(gè)有限狀態(tài)的集合是一個(gè)有限狀態(tài)的集合 是字母表是字母表 Q0 Q 是是開始狀態(tài)集合開始狀態(tài)集合 F Q 是接收狀態(tài)集合是接收狀態(tài)集合是是Q

52、2Q的狀態(tài)轉(zhuǎn)換函數(shù)的狀態(tài)轉(zhuǎn)換函數(shù)即即 (q，a) 2Q NFA在狀態(tài)在狀態(tài)q，掃描字母，掃描字母a后到達(dá)后到達(dá)可能可能的的下一下一狀態(tài)集合狀態(tài)集合。NFA與DFA NFA有一個(gè)有一個(gè)可能的可能的開始狀態(tài)集開始狀態(tài)集合合和可能的下一和可能的下一狀態(tài)集合狀態(tài)集合 其余的同其余的同DFA。 NFA與與DFA的的重要區(qū)別重要區(qū)別在于在于 轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)的不同。的不同。 (q，x)對應(yīng)對應(yīng)的是的是狀態(tài)集合狀態(tài)集合Q的一個(gè)的一個(gè)子集子集FA處于狀態(tài)處于狀態(tài)qDFA對對每個(gè)每個(gè)字母字母只有惟一的狀態(tài)轉(zhuǎn)移只有惟一的狀態(tài)轉(zhuǎn)移NFA對對某個(gè)某個(gè)字母字母可以有可以有多個(gè)狀態(tài)轉(zhuǎn)移多個(gè)狀態(tài)轉(zhuǎn)移；NFA接收該字母時(shí)接收

53、該字母時(shí),從多個(gè)狀態(tài)轉(zhuǎn)移從多個(gè)狀態(tài)轉(zhuǎn)移中中可以可以 非確定非確定地地選擇選擇任意一個(gè)任意一個(gè)。具體地具體地對于對于NFA， (q，a) Q(q，a) 有有3種可能種可能 (q，a) = (q，a) =q1 (q，a) =q1 ，q2，qn或或或或 (q，a)仍是一個(gè)仍是一個(gè)狀態(tài)轉(zhuǎn)換函數(shù)狀態(tài)轉(zhuǎn)換函數(shù)，只是其只是其值域值域發(fā)生了改變。發(fā)生了改變。 所有所有(q，a)對應(yīng)的所有子集元素對應(yīng)的所有子集元素個(gè)數(shù)都為個(gè)數(shù)都為1時(shí)，時(shí)，NFA退化為退化為DFANFA停機(jī)停機(jī)NFANFA在兩種情況下在兩種情況下自動(dòng)停機(jī)自動(dòng)停機(jī)： 將輸入串掃描結(jié)束將輸入串掃描結(jié)束 (q(q，a)=a)=( (即對應(yīng)即對應(yīng)沒有定

54、義沒有定義) ) 或或在掃描一個(gè)串在掃描一個(gè)串w時(shí)，時(shí)，NFA的狀態(tài)發(fā)的狀態(tài)發(fā)生轉(zhuǎn)換，可能會有多種生轉(zhuǎn)換，可能會有多種情況：情況： 可能在可能在接收狀態(tài)接收狀態(tài)時(shí)終止；時(shí)終止； 可能在可能在非接收狀態(tài)非接收狀態(tài)時(shí)終止；時(shí)終止； 也可能在也可能在中途中途停止（停止（中止中止）。 若若至少存在一條路徑至少存在一條路徑可以使可以使NFA在掃描串在掃描串w后到達(dá)接收狀態(tài)后到達(dá)接收狀態(tài) 則串則串w能被能被NFA所接收所接收。 對于字母表對于字母表上的上的NFA，它能接，它能接收的所有串的集合，稱為收的所有串的集合，稱為NFA能接能接收的語言。收的語言。 記為記為 L(NFA)問題問題l如何形式化定義如何

55、形式化定義L(NFA)?定義定義 NFA擴(kuò)展?fàn)顟B(tài)轉(zhuǎn)換函數(shù)擴(kuò)展?fàn)顟B(tài)轉(zhuǎn)換函數(shù)l給定給定NFA，擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù)，擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù) *：2Q*2Q 為為 *(p，w)= Q 即即NFA在狀態(tài)集合在狀態(tài)集合p時(shí)，掃描串時(shí)，掃描串w后到達(dá)可能的的狀態(tài)集合后到達(dá)可能的的狀態(tài)集合QNFA擴(kuò)展?fàn)顟B(tài)轉(zhuǎn)換函數(shù) 若若p= q1，q2，qn *（p，）=pa*(p，a) = (q，a)|qp =(q1, a),(q2, a),(qn, a)對于串對于串w w=a *(p， w) =*(p，a) = (q，a)| q*(p，)或或w= a *(p， w ) =*(p， a ) = *(q,)| q*(p， a )L

56、(NFA)表示被表示被NFA所接收的語言所接收的語言L(NFA)=w|w*且且 *(Q0， w)Fl它表示所有串它表示所有串w的集合的集合 在在NFA的狀態(tài)圖中，的狀態(tài)圖中，至少存在一至少存在一條路徑條路徑 以以w為標(biāo)記，能使為標(biāo)記，能使NFA從某個(gè)開從某個(gè)開始狀態(tài)到達(dá)某個(gè)接收狀態(tài)。始狀態(tài)到達(dá)某個(gè)接收狀態(tài)。構(gòu)造構(gòu)造NFA，分別接收語言，分別接收語言0* *、 0+(0+1)* *、(0+1)+ +0、010(0+1) * * 1(0+1)*00(0+1)* 3.4.2 NFA的的確定化確定化DFA可以轉(zhuǎn)換為可以轉(zhuǎn)換為NFANFA可以轉(zhuǎn)換為可以轉(zhuǎn)換為DFA(確定化確定化)定理3-3l*的一個(gè)子集

57、的一個(gè)子集L是一個(gè)是一個(gè)FSL， 充要條件為充要條件為 存在存在NFA，使得，使得L(NFA)=L證明：證明：= 必要性必要性l若若L是是FSL，則有，則有L=L(DFA） DFA=(Q ， ， ， q0 ， F)構(gòu)造構(gòu)造 NFA=(Q，1，q0，F(xiàn)) 1(q，a)=(q，a) 即把即把DFA的一個(gè)狀態(tài)的一個(gè)狀態(tài) 當(dāng)作當(dāng)作 NFA的一個(gè)狀態(tài)集合的一個(gè)狀態(tài)集合 則則 L=L(DFA)=L(NFA)證明證明: 1,w中中最后字母最后字母與與第一個(gè)字母第一個(gè)字母相同相同1)給出該語言的給出該語言的正則表達(dá)式正則表達(dá)式；2)構(gòu)造構(gòu)造NFA接受該語言；接受該語言；3)將將NFA轉(zhuǎn)換為等價(jià)的轉(zhuǎn)換為等價(jià)的D

58、FA。解l1) 該語言的正則表達(dá)式該語言的正則表達(dá)式: a(a+b+c)*a + b(a+b+c)*b + c(a+b+c)*c解2)構(gòu)造構(gòu)造NFA接受該語言接受該語言解3) 改造為改造為DFA接受該語言：接受該語言： a b c q0 q1 q2 q3 q1 q1,q4 q1 q1 q2 q2 q2,q4 q2 q3 q3 q3 q3,q4 q1,q4 q1,q4 q1 q1 q2,q4 q2 q2,q4 q2 q3,q4 q3 q3 q3,q4思考：思考：構(gòu)造NFA，接收語言語言L= w|wa,b,c+, |w|0,w中中最后字母最后字母與與第一個(gè)字母第一個(gè)字母相同相同l該語言的正則表達(dá)式

59、該語言的正則表達(dá)式: a(R)*a+b(R)*b+c(R)*c+a+b+c例例3-21接收l 語言語言L= w| wa,b+, w中中倒數(shù)第二個(gè)字母倒數(shù)第二個(gè)字母肯定在前肯定在前面面出現(xiàn)過出現(xiàn)過 1)給出該語言的給出該語言的正則表達(dá)式正則表達(dá)式；2)構(gòu)造構(gòu)造NFA接受該語言；接受該語言；3)將將NFA轉(zhuǎn)換為等價(jià)的轉(zhuǎn)換為等價(jià)的DFA。解1) 該語言的正則表達(dá)式該語言的正則表達(dá)式: (a+b)*a(a+b)*a(a+b) + (a+b)*b(a+b)*b(a+b)解2)構(gòu)造構(gòu)造NFA接受該語言接受該語言解3)將將NFA轉(zhuǎn)換為等價(jià)的轉(zhuǎn)換為等價(jià)的DFA 例例:構(gòu)造NFA，接收 0，1上的語言上的語言;

60、 該語言的每個(gè)句子必須包含該語言的每個(gè)句子必須包含00正則表達(dá)式為：正則表達(dá)式為：(0+1)*00(0+1)* NFA 0,1q20q00,1q10構(gòu)造NFA，接收 0，1上的語言，上的語言，該語言的每個(gè)句子必須包含該語言的每個(gè)句子必須包含001正則表達(dá)式為：正則表達(dá)式為：(0+1)*001(0+1)*NFA 0,1q2001q00,1例3-23構(gòu)造NFA，接收 0，1上的語言，上的語言，該語言每個(gè)句子必須該語言每個(gè)句子必須不包含不包含001NFA 0q1011q20q0例例3-24構(gòu)造NFA，接收 0，1上的語言，上的語言， 該語言的每個(gè)句子該語言的每個(gè)句子 以以0開頭，以開頭，以1結(jié)尾結(jié)尾