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

第三章,有限狀態(tài)自動(dòng)機(jī),定義語(yǔ)言,可以從兩個(gè)方面進(jìn)行： ）從產(chǎn)生語(yǔ)言的角度； ）從接收(或識(shí)別)語(yǔ)言的角度。,形式語(yǔ)言研究?jī)?nèi)容,產(chǎn)生一個(gè)語(yǔ)言: 1)定義語(yǔ)言中的基本句子; 2)根據(jù)其余句子的形成規(guī)則，產(chǎn)生出該語(yǔ)言所包含的所有句子。,有限自動(dòng)機(jī)研究?jī)?nèi)容,使用某種自動(dòng)機(jī)模型來(lái)接收字符串 接收的所有字符串形成的集合，也是一個(gè)語(yǔ)言,統(tǒng)一的理論,形式語(yǔ)言與自動(dòng)機(jī)作為統(tǒng)一的理論,實(shí)際上包括3個(gè)方面的內(nèi)容: 1) 形式語(yǔ)言理論(文法產(chǎn)生語(yǔ)言) 2) 自動(dòng)機(jī)理論(自動(dòng)機(jī)接收語(yǔ)言) 3) 形式語(yǔ)言與自動(dòng)機(jī)的等價(jià)性理論 (文法與自動(dòng)機(jī)等價(jià)轉(zhuǎn)換),有限狀態(tài)自動(dòng)機(jī) FA (Finite state Automaton),FA是為研究 有限存儲(chǔ)的計(jì)算過(guò)程 正則語(yǔ)言 而抽象出的一種計(jì)算模型。,兩類有限狀態(tài)自動(dòng)機(jī),接收器 判斷是否接收輸入串； 轉(zhuǎn)換器 對(duì)給定輸入串產(chǎn)生輸出。,FA還可以分為,確定的FA-DFA Deterministic Finite state Automaton 非確定FA- NFA Non-deterministic Finite state Automaton,等價(jià)性,有限狀態(tài)自動(dòng)機(jī)接收的語(yǔ)言稱為有限狀態(tài)語(yǔ)言-FSL 從產(chǎn)生語(yǔ)言角度而言， FSL就是右線性語(yǔ)言-RLL 從(正則)運(yùn)算角度而言， FSL就是正則語(yǔ)言-RL,有限狀態(tài)自動(dòng)機(jī)除在理論上的研究?jī)r(jià)值外 還在數(shù)字電路設(shè)計(jì)、編譯技術(shù)(詞法分析)、系統(tǒng)輔助軟件(文本編輯程序)、漏洞檢測(cè)、交通控制等應(yīng)用領(lǐng)域得到廣泛應(yīng)用,3.1 有限狀態(tài)自動(dòng)機(jī),有限狀態(tài)自動(dòng)機(jī)是具有離散輸入和離散輸出的一種數(shù)學(xué)模型。 有限狀態(tài)自動(dòng)機(jī)是否接收串w 有限狀態(tài)自動(dòng)機(jī)是否接收語(yǔ)言L,有限狀態(tài)自動(dòng)機(jī)物理模型,a1,a2,a3,aj,an,an+1,FSC,一個(gè)輸入存儲(chǔ)帶（輸入帶），帶被分解為單元，每個(gè)單元存放一個(gè)輸入符號(hào)(字母表上的符號(hào))。 整個(gè)輸入串從帶的左端點(diǎn)開(kāi)始存放，而帶的右端可以無(wú)限擴(kuò)充；,一個(gè)有窮狀態(tài)控制器（FSC） 該控制器的狀態(tài)只能是有限多個(gè) FSC通過(guò)讀頭讀取當(dāng)前帶上單元的字符。,初始時(shí)，讀頭對(duì)應(yīng)帶的最左單元，每讀取一個(gè)字符，讀頭向右自動(dòng)移動(dòng)一個(gè)單元。 讀頭不允許向左移動(dòng)。,有限狀態(tài)自動(dòng)機(jī)的一個(gè)動(dòng)作為： 讀頭讀取帶上當(dāng)前單元的字符 FSC根據(jù)當(dāng)前FSC的狀態(tài)和讀取的字符，進(jìn)行狀態(tài)改變； 將讀頭向右移動(dòng)一個(gè)單元。,有限態(tài)自動(dòng)機(jī)的動(dòng)作簡(jiǎn)化為： FSC根據(jù) 當(dāng)前狀態(tài) 和 當(dāng)前讀取的帶上字符 進(jìn)行狀態(tài)改變。,定義3-1 有限狀態(tài)自動(dòng)機(jī)FA,FA是一個(gè)五元式 FA=(Q，q0，F(xiàn)) Q是有限狀態(tài)的集合 是字母表，即輸入帶上的字符集合,q0Q是開(kāi)始狀態(tài) FQ是接收狀態(tài)(終止?fàn)顟B(tài))集合,是QQ的狀態(tài)轉(zhuǎn)換函數(shù) 即(q，x)= q 代表自動(dòng)機(jī)在狀態(tài)q時(shí)，掃描字符x后到達(dá)狀態(tài)q,有限狀態(tài)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)的個(gè)數(shù)應(yīng)該為 |Q|*| 對(duì)于Q中的每個(gè)狀態(tài)，需要定義對(duì)應(yīng)每個(gè)字母的狀態(tài)轉(zhuǎn)換。,DFA,這種有限狀態(tài)自動(dòng)機(jī)為確定的有限狀態(tài)自動(dòng)機(jī)DFA。,例3-1,定義DFA為： DFA=(q0,q1,0,1,q0,q0) 其中：,的表示：函數(shù)形式,(q0，0)=q1 (q0，1)=q1 (q1，0)= q1 (q1，1)= q0,的表示：狀態(tài)矩陣,Q ,0,q0,1,q1,q1,q1,q1,q0,的表示:狀態(tài)圖形式,狀態(tài)圖是一個(gè)有向、有循環(huán)的圖 一個(gè)節(jié)點(diǎn)表示一個(gè)狀態(tài)； 若有(q，x)= q，則 狀態(tài)q到狀態(tài)q有一條有向邊，并用字母x作標(biāo)記。,的表示,指向的狀態(tài)是開(kāi)始狀態(tài) 兩個(gè)圓圈代表接收狀態(tài)；,的表示：狀態(tài)圖,q1,1,0,1,0,q0,用狀態(tài)圖表示一個(gè)DFA 有向邊的數(shù)目就是狀態(tài)轉(zhuǎn)換函數(shù)的個(gè)數(shù)。,默認(rèn),(q,)=q 不是狀態(tài)轉(zhuǎn)換函數(shù),3.2 有限狀態(tài)自動(dòng)機(jī)接收語(yǔ)言,對(duì)于DFA，給定串w=x1x2xn 初始時(shí)， DFA處于開(kāi)始狀態(tài)q0 從左到右逐個(gè)字符地掃描串w,在(q0，x1)= q1的作用下 DFA處于狀態(tài)q1 在(q1，x2)=q2的的作用下 DFA處于狀態(tài)q2 ,當(dāng)將串w掃描結(jié)束后， 若DFA處于某一個(gè)接收狀態(tài)， 則有限狀態(tài)自動(dòng)機(jī)能夠接收串w,對(duì)于可接收串,DFA從開(kāi)始狀態(tài)開(kāi)始，在掃描串的過(guò)程中， 狀態(tài)逐個(gè)地變化,串掃描結(jié)束后， 到達(dá)某個(gè)接收狀態(tài)。,對(duì)于不可接收串,DFA從開(kāi)始狀態(tài)開(kāi)始，在掃描串的過(guò)程中， 狀態(tài)逐個(gè)地變化,串掃描結(jié)束后， 處于非接收狀態(tài)。,對(duì)于字母表上的DFA 能夠接收的所有串的集合，就是 DFA能接收的語(yǔ)言，記為L(zhǎng)(DFA) 也稱為有限狀態(tài)語(yǔ)言（FSL）,思考,如何形式化定義L(DFA)?,定義3-4 擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù),給定DFA，擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù) *：Q*Q 即 *(q,w)=q 即DFA在一個(gè)狀態(tài)q時(shí)，掃描串w后到達(dá)唯一確定的狀態(tài)q,遞歸擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù),*(q,)=q *(q,a)=(q,a) 其中a,對(duì)于串w=a（+） *（q， w） =*(q，a） =(*(q,),a),或者,對(duì)于串w= a *(q，w) =*(q，a) =*(q，a),),定義3-6 DFA接收的語(yǔ)言,DFA=(Q,q0，F(xiàn))接收的語(yǔ)言 L(DFA)=w|*(q0,w)F,思考,如何描述 在某個(gè)時(shí)刻，DFA所處的情況？,定義3-7 DFA的瞬時(shí)描述（格局）,格局是一個(gè)二元式：qy q是DFA當(dāng)前狀態(tài) y是輸入帶上還沒(méi)有被掃描到的串 讀頭將掃描y串的第1個(gè)字母,在掃描串的過(guò)程中，格局在發(fā)生轉(zhuǎn)換(改變) 格局的(一次)轉(zhuǎn)換的原因是由于函數(shù)的(一次)作用,如果當(dāng)前格局為：qar 有函數(shù)：(q，a)= q 則下一格局為： qr 格局的轉(zhuǎn)換可以記為： qar = qr,DFA的特殊格局,初始格局為： q0w 接收格局為： qf 其中，qf是某個(gè)接收狀態(tài),使用=*代表格局的任意次轉(zhuǎn)換 使用=+代表格局的多次轉(zhuǎn)換,可以使用格局的轉(zhuǎn)換方式定義FSL,DFA接收的語(yǔ)言 L(DFA)= w|q0w=*qf；w*且qfF,定義3-8 DFA停機(jī),DFA將輸入串掃描結(jié)束時(shí) (自動(dòng))停機(jī) 這是DFA唯一的停機(jī)情況,注意1：,DFA將輸入串掃描結(jié)束停機(jī)時(shí)， 如果DFA處于某一個(gè)接收狀態(tài)， 則表示接收整個(gè)輸入串； 反之，則表示不接收整個(gè)輸入串;,注意2：,對(duì)于狀態(tài)q,如果不能接收字母a 則將狀態(tài)轉(zhuǎn)換到一個(gè)特殊的狀態(tài)：陷阱狀態(tài)qt,陷阱狀態(tài)qt不能夠改變?yōu)槠渌麪顟B(tài) 即 對(duì)于a (qt ，a)=qt qt不能夠接收任意字母,構(gòu)造DFA，分別接收語(yǔ)言,、0、01、 0*、 0+ (0+1)*、(0+1)+ 01*0 、1 *00(0+1) * (0+1) *00(0+1) * 0(0+1) *1 0(0+1) *0+1(0+1)*1 ,定理3-1,每個(gè)FSL都是一個(gè)右線性語(yǔ)言 分析： 已知 接收FSL的DFA 需要 構(gòu)造RLG，使得 L(RLG)=FSL,等價(jià)思路,DFA最重要的部分是狀態(tài)轉(zhuǎn)換函數(shù) 文法最重要的部分是產(chǎn)生式 考慮狀態(tài)轉(zhuǎn)換函數(shù)和產(chǎn)生式的等價(jià)作用: 將狀態(tài)轉(zhuǎn)換函數(shù)改造為產(chǎn)生式,等價(jià)思路,狀態(tài)轉(zhuǎn)換函數(shù)和產(chǎn)生式的等價(jià)作用 (q, a)=q AaB 接收a 產(chǎn)生a 狀態(tài)變化 非終結(jié)符號(hào)變化 結(jié)論:DFA狀態(tài)等價(jià)于文法非終結(jié)符 狀態(tài)轉(zhuǎn)換函數(shù)等價(jià)于產(chǎn)生式,構(gòu)造文法的基本思路：,將的DFA的狀態(tài)當(dāng)作是RLG的非終結(jié)符(開(kāi)始狀態(tài)就是開(kāi)始符號(hào)) 對(duì)于某個(gè)句子： DFA通過(guò)狀態(tài)的改變，逐步（自左向右）接收句子的每個(gè)字母； RLG通過(guò)非終結(jié)符號(hào)的改變，逐步（自左向右）產(chǎn)生句子的每個(gè)字母。,思考,DFA的接收狀態(tài)的作用,證明,假設(shè)L是字母表上的FSL，則 L=L(DFA),DFA=（Q，q0，F(xiàn)） 構(gòu)造右線性文法G=(,Q,q0，P） 其中P為：,qaq|(q，a)=q U qa|(q，a)F 特別，若q0是接收狀態(tài)，則 q0,對(duì)于句子w=x1x2xn,DFA： 則文法有 (q0, x1)=q1 q0x1q1 (q1, x2)=q2 q1x2q2 (qn-2,xn-1)=qn-1 qn-2xn-1qn-1 (qn-1, xn)=qn qn-1xnqn 或 qn-1xn,所以,DFA 文法 *(q，)=q q=*q *(q0， w)F q0=*w 注意： 陷進(jìn)狀態(tài)在文法中是無(wú)用非終結(jié)符,例3-2 DFA與文法的轉(zhuǎn)換,FSL=(0,1)1*0* 接收該語(yǔ)言的DFA為：,q1,1,0,0,1,q0,構(gòu)造正則文法產(chǎn)生該語(yǔ)言： q00q1|1q1| q10q0|1q1| 0,定理3-2,FSL對(duì)補(bǔ)運(yùn)算封閉,證明：,設(shè)L1是上的FSL,且L1=L(DFA1)， DFA1=（Q，q0，F(xiàn)）,構(gòu)造 DFA2=（Q，q0，Q） DFA2接收的語(yǔ)言是 L1的對(duì)應(yīng)的全集,即*,構(gòu)造 DFA3=(Q，q0，Q-F) L3=L(DFA3) L3接收的語(yǔ)言是L1(關(guān)于*)的補(bǔ) L3也是FSL語(yǔ)言。,注意,此時(shí)的DFA1的函數(shù)的個(gè)數(shù)為 |Q|*|,基本的等價(jià)替換,對(duì)于狀態(tài)轉(zhuǎn)換圖，有基本的等價(jià)替換 變換為,0,1,1,3.3 DFA接收語(yǔ)言的例子,構(gòu)造DFA，接收語(yǔ)言 L=ab,基本結(jié)構(gòu)（接收基本句子）,q1,a,b,q0,q2,增加陷阱狀態(tài)后的DFA,q1,a,b,q0,qt,b,a,a, b,a, b,q2,思考1,如果將該DFA的所有狀態(tài)都設(shè)置為接收狀態(tài)(包括陷阱狀態(tài))， 接收的語(yǔ)言是？,思考2,如果將該自動(dòng)機(jī)的接收狀態(tài)和非接收狀態(tài)對(duì)調(diào) 接收的語(yǔ)言是？,例3-4構(gòu)造DFA,接收語(yǔ)言L=x000y|x,y0,1*,分析,該語(yǔ)言的特點(diǎn)是 語(yǔ)言中的每個(gè)串都包含連續(xù)的3個(gè)0（即每個(gè)串都包含子串000）,因此，對(duì)于任何輸入串，有限狀態(tài)自動(dòng)機(jī)的任務(wù)就是要檢查該輸入串中是否存在子串000， 一旦發(fā)現(xiàn)輸入串包含有000，則表示整個(gè)輸入串是句子。,因此，在確認(rèn)輸入串包含000后， 就可以逐一地讀入000后面的全部字符，并接收該輸入串。,思考,問(wèn)題的關(guān)鍵是？ 如何發(fā)現(xiàn)子串000。,由于字符是逐一讀入的，當(dāng)從輸入串中讀入一個(gè)0時(shí)， 它有可能是000的第1個(gè)0， 需要記住已經(jīng)出現(xiàn)過(guò)一個(gè)0；,如果緊接著讀入的是字符1， 則剛讀入的0就不是000的第1個(gè)0 需要重新尋找000子串的第1個(gè)0；,如果緊接著讀入的還是0，它有可能是000的第2個(gè)0， 也需要記住這個(gè)0， 繼續(xù)讀入字符，若是0，則發(fā)現(xiàn)000 否則，需要重新尋找000。,初始狀態(tài)：q0 接收0，到達(dá)狀態(tài)q1 接收00 ,到達(dá)狀態(tài)q2 接收000,到達(dá)狀態(tài)q3,因此，基本的狀態(tài)轉(zhuǎn)移函數(shù)為： (q0，0)=q1 (q1，0)=q2 (q2，0)=q3 用于接收基本句子000,接收000的狀態(tài)圖,q0,0,0,0,q1,q2,q3,其他狀態(tài)轉(zhuǎn)移函數(shù)為： (q0，1)=q0 期待0的出現(xiàn) (q1，1)=q0 重新尋找000 (q2，1)=q0 重新尋找000 (q3，0)=q3 掃描后續(xù)字符 (q3，1)=q3 掃描后續(xù)字符,狀態(tài)轉(zhuǎn)移圖,q0,0,1,1,1,0,0,0,1,q1,q2,q3,思考,如果需要接收語(yǔ)言 L 如何修改有限狀態(tài)自動(dòng)機(jī)? 思路：考慮開(kāi)始狀態(tài)的作用,思考:如果,DFA的開(kāi)始狀態(tài)只負(fù)責(zé)接收輸入串的第一個(gè)字母； 文法的開(kāi)始符號(hào)只負(fù)責(zé)串的推導(dǎo)的開(kāi)始； 優(yōu)點(diǎn)是？,狀態(tài)圖為,例3-5構(gòu)造DFA,接收語(yǔ)言 L=x001y|x，y0，1*,分析：,對(duì)于任何輸入串，DFA的任務(wù)就是要檢查該輸入串中是否存在001,初始狀態(tài)：q0 q1 已接收0 q2 已接收00 q3 已接收001,q2,q1,q0,狀態(tài)轉(zhuǎn)移圖,0,1,q3,1,0,1,0,1,0,例3-6 構(gòu)造DFA,接收語(yǔ)言L=x000|x0，1*,q2,q3,q1,q0,0,1,1,1,0,0,0,1,例3-7構(gòu)造DFA,接收語(yǔ)言L=x000x001 其中，x0，1*,q2,q1,q0,0,1,q3,1,0,0,0,1,q4,1,0,1,例3-8構(gòu)造DFA,接收語(yǔ)言L=02k+3m|m,k=0,實(shí)際上： 2k+3m 可以表示任意的非負(fù)整數(shù)(除1外) 該語(yǔ)言為0*-0,狀態(tài)轉(zhuǎn)移圖,0,0,0,q1,q2,q0,思考：構(gòu)造DFA,接收語(yǔ)言L=02k+3m|m,k0,例3-9構(gòu)造DFA,接收0，1上的語(yǔ)言，該語(yǔ)言的 每個(gè)句子以0開(kāi)頭，以1結(jié)尾。,狀態(tài)轉(zhuǎn)移圖,0,1,0,q1,q2,1,0,qt,0,1,1,q0,例3-10 構(gòu)造DFA,接收0，1上的語(yǔ)言，該語(yǔ)言的每個(gè)字符串 不包含00子串(語(yǔ)言允許 ),0,0,0,1,qt,q1,q0,q2,1,0,1,1,或,0,0,0,1,qt,q1,q0,1,1,構(gòu)造DFA,接收0，1上的語(yǔ)言， 該語(yǔ)言的每個(gè)字符串不包含00 （語(yǔ)言不允許 ）,例3-11構(gòu)造DFA,接收0，1，2上的語(yǔ)言， 該語(yǔ)言的每個(gè)字符串代表的數(shù)字能整除3。,分析,如果一個(gè)十進(jìn)制整數(shù)的所有位的數(shù)字的和能夠整除3，那么， 這個(gè)十進(jìn)制整數(shù)就能夠整除3；,一個(gè)十進(jìn)制整數(shù)除以3，余數(shù)只能是1、2和0；,將整數(shù)當(dāng)作一個(gè)字符串，從左到右逐一地讀入； 使用3個(gè)狀態(tài)分別代表已讀入的數(shù)字的和除以3的余數(shù)情況： (即讀入的整數(shù)對(duì)3的余數(shù)情況）,q0：已讀入的整數(shù)除以3，余數(shù)為0 q1：已讀入的整數(shù)除以3，余數(shù)為1 q2：已讀入的整數(shù)除以3，余數(shù)為2,思考,已知 qi(i =0,1,2)，k=0,1,2 應(yīng)該如何確定 j？,qi,qj,k,掃描子串w后,處于某個(gè)狀態(tài)qi， 讀入當(dāng)前數(shù)字, 狀態(tài)轉(zhuǎn)換情況為,q0,在此狀態(tài)讀入0，引導(dǎo)DFA到達(dá)下一狀態(tài)的輸入串為w0, w0的各位數(shù)字和除以3，余數(shù)為0。所以， DFA在q0狀態(tài)讀入0，應(yīng)該繼續(xù)保持q0狀態(tài)；,q0,在此狀態(tài)讀入1，引導(dǎo)DFA到達(dá)下一狀態(tài)的輸入串為w1，w1的各位數(shù)字和除以3，余數(shù)為1。 所以， DFA在q0狀態(tài)讀入1，應(yīng)該到達(dá)q1狀態(tài)；,q0,在此狀態(tài)讀入2，引導(dǎo)DFA到達(dá)下一狀態(tài)的輸入串為w2，w2的各位數(shù)字和除以3，余數(shù)為2。 所以， DFA在q0狀態(tài)讀入2，應(yīng)該到達(dá)q2狀態(tài)； ,存在的問(wèn)題,接收的串包括以0開(kāi)始的數(shù)字串； 還能夠接收空串,思考,如何進(jìn)行改進(jìn)，使得 接收的串不能以0開(kāi)始， 不能接收空串。,定義3-9 set集合,對(duì)于狀態(tài)q，能將DFA從q0轉(zhuǎn)換到q狀態(tài)的所有字符串的集合為： set(q)=w|w*,*(q0,w)=q,則有限狀態(tài)自動(dòng)機(jī)DFA接收的語(yǔ)言可以定義為： L(DFA)= set(q) 其中： qF,按狀態(tài)進(jìn)行劃分,對(duì)于DFA，可以定義關(guān)系R 若 x,y* ，qQ 則 xRy 當(dāng)且僅當(dāng) xset(q),yset(q) 即R=(x,y)|xset(q),yset(q) ；qQ 是*上的二元關(guān)系,該關(guān)系是集合*上的一個(gè)等價(jià)關(guān)系，利用該關(guān)系， 可以將*劃分為不多于|Q|個(gè)的等價(jià)類。,DFA可以按照語(yǔ)言的特點(diǎn)給出字母表*的一個(gè)劃分，這種劃分相當(dāng)于*上的一個(gè)等價(jià)分類。 DFA每個(gè)狀態(tài)對(duì)應(yīng)著一個(gè)等價(jià)類,利用一個(gè)狀態(tài)去表示一個(gè)等價(jià)類是構(gòu)造DFA的一條有效思路。,例3-12構(gòu)造DFA,接收,0,1,2,4,5,6,7,8,9上的語(yǔ)言， 該語(yǔ)言的每個(gè)字符串代表的數(shù)字能整除3。,仍然只使用3個(gè)狀態(tài)分別代表已經(jīng)讀入的整數(shù)字的和除以3的不同的余數(shù)的情況：,狀態(tài)與對(duì)應(yīng)的等價(jià)類,q0：余數(shù)為0的輸入串的等價(jià)類 q1：余數(shù)為1的輸入串的等價(jià)類 q2：余數(shù)為2的輸入串的等價(jià)類,例3-13構(gòu)造DFA,接收,0，1上的語(yǔ)言，該語(yǔ)言的每個(gè)字符串擋成二進(jìn)制數(shù)時(shí)， 代表的數(shù)字能整除3。,DFA的每個(gè)狀態(tài)對(duì)應(yīng)一個(gè)等價(jià)類 利用一個(gè)狀態(tài)去表示一個(gè)等價(jià)類 除以3的余數(shù)只能為0、1和2,q0：余數(shù)為0的輸入串的等價(jià)類； q1：余數(shù)為1的輸入串的等價(jià)類； q2：余數(shù)為2的輸入串的等價(jià)類；,不能接收空串，所以， 還需要一個(gè)開(kāi)始狀態(tài)qS,人們習(xí)慣使用十進(jìn)制數(shù),w=x1x2x3xn (x1x2x3xn)2=(x1*2n-1+ x2*2n-2+ xn-1*2+xn)10 當(dāng)串長(zhǎng)度增加1時(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)10 =(2*(w)10+x)10 =6*n+2*i+x 實(shí)際上 2*i+x 對(duì)3的余數(shù)就是wx對(duì)3的余數(shù),設(shè)w是當(dāng)前已經(jīng)讀入的輸入串； qS：開(kāi)始狀態(tài) 讀入0時(shí)，進(jìn)入狀態(tài)q0 讀入1時(shí)，進(jìn)入狀態(tài)q1,q0,能引導(dǎo)DFA到達(dá)此狀態(tài)的w除以3余數(shù)為0，因此 (w)10=3n+0,q0,在此狀態(tài)讀入0，引導(dǎo)DFA到達(dá)下一狀態(tài)的輸入串為w0，則 (w0)10=2(3n+0)+0=32n+0 表明w0也屬于q0對(duì)應(yīng)的等價(jià)類。所以，DFA在q0狀態(tài)讀入0，應(yīng)該繼續(xù)保持q0狀態(tài)；,q0,在此狀態(tài)讀入1，引導(dǎo)DFA到達(dá)下一狀態(tài)的輸入串為w1，則 (w1)10=2(3n+0)+1=32n+1 表明w1屬于q1對(duì)應(yīng)的等價(jià)類。所以， DFA在q0狀態(tài)讀入1，應(yīng)該到達(dá)q1狀態(tài)；,q1,能引導(dǎo)DFA到達(dá)此狀態(tài)的w除以3余數(shù)為1，因此 (w)10=3n+1,q1,在此狀態(tài)讀入0，引導(dǎo)DFA到達(dá)下一狀態(tài)的輸入串為w0，則 (w0)10=2(3n+1)+0=32n+2 表明w0屬于q2對(duì)應(yīng)的等價(jià)類。所以， DFA在q1狀態(tài)讀入0，應(yīng)該到達(dá)q2狀態(tài)；,q1,在此狀態(tài)讀入1，引導(dǎo)DFA到達(dá)下一狀態(tài)的輸入串為w1，則 (w1)10=2(3n+1)+1=32n+3 表明w1屬于q0對(duì)應(yīng)的等價(jià)類。所以， DFA在q1狀態(tài)讀入1，應(yīng)該到達(dá)q0狀態(tài)；,q2,能引導(dǎo)DFA到達(dá)此狀態(tài)的w除以3余數(shù)為2，因此， (w)10=3n+2,q2,在此狀態(tài)讀入0，引導(dǎo)DFA到達(dá)下一狀態(tài)的輸入串為w0，則 (w0)10=2(3n+2)+0=32n+4 表明w0屬于q1對(duì)應(yīng)的等價(jià)類。所以，DFA在q2狀態(tài)讀入0，應(yīng)該到達(dá)q1狀態(tài)；,q2,在此狀態(tài)讀入1，引導(dǎo)自動(dòng)機(jī)到達(dá)下一狀態(tài)的輸入串為w1，則 (w1)10=2(3n+2)+1=32n+5 表明w1屬于q2對(duì)應(yīng)的等價(jià)類。所以，自動(dòng)機(jī)在q2狀態(tài)讀入1，繼續(xù)保持q2狀態(tài)；,狀態(tài)圖,例3-14構(gòu)造DFA，接收,0，1上的語(yǔ)言，該語(yǔ)言的每個(gè)字符串為二進(jìn)制數(shù)時(shí)， 代表的數(shù)字能被5整除。,分析：,對(duì)5的余數(shù)只能為0、1、2、3和4 使用5個(gè)狀態(tài)分別代表已經(jīng)讀入的數(shù)字除以5的不同的余數(shù)的等價(jià)類： qi：已經(jīng)讀入的數(shù)除以5，余數(shù)為i的輸入串的等價(jià)類； 其中 i=0,1,2,3,4 不能接收空串，需要一個(gè)開(kāi)始狀態(tài)qS,例3-15構(gòu)造DFA，接收,1,2,3上的語(yǔ)言，該語(yǔ)言的每個(gè)字符串擋成十進(jìn)制數(shù)時(shí)， 代表的數(shù)字能被4整除。,思考：構(gòu)造DFA，接收,0，1,2，3，4，5，6，7，8，9上的語(yǔ)言，該語(yǔ)言的每個(gè)字符串擋成十進(jìn)制數(shù)時(shí)， 代表的數(shù)字能整除7 。 ,總結(jié)：構(gòu)造DFA，接收,=x1, x2,x3,xm上的語(yǔ)言 該語(yǔ)言的每個(gè)字符串擋成base進(jìn)制數(shù)時(shí) 代表的數(shù)字能整除N 或 代表的數(shù)字對(duì)N的余數(shù)為K,分析：,對(duì)N的余數(shù)只能為0、1、2、3、和N-1 使用N個(gè)狀態(tài)分別代表已經(jīng)讀入的串（當(dāng)作數(shù)）對(duì)N的不同的余數(shù)的等價(jià)類：,q0：余數(shù)為0的輸入串的等價(jià)類； 該類數(shù)十進(jìn)制為N*n+0,q1：余數(shù)為1的輸入串的等價(jià)類；該類數(shù)十進(jìn)制為N*n+1 q2：余數(shù)為2的輸入串的等價(jià)類；該類數(shù)十進(jìn)制為N*n+2, qN-1：余數(shù)為N-1的輸入串的等價(jià)類；該類數(shù)十進(jìn)制為N*n+N-1,注意,不能接收空串， 還需要一個(gè)開(kāi)始狀態(tài)qS,qS,讀入x時(shí)，進(jìn)入對(duì)應(yīng)狀態(tài)qi,本質(zhì),已知 qi(i =0，1，2，N-1) x=x1, x2,x3,xm 應(yīng)該如何確定 j？,qi,qj,x,qi,已經(jīng)讀入的數(shù)為w，對(duì)應(yīng)余數(shù)為i的輸入串的等價(jià)類； 該類數(shù)十進(jìn)制為N*n+i,當(dāng)前讀入的字符為x；則wx表示的十進(jìn)制數(shù)為 (wx)10= base* (w)10 +x =base*（N*n+i）+x =N*base*n+base*i+x,該數(shù)對(duì)于N取余數(shù)就是base*i+x對(duì)于N的余數(shù)， 若該余數(shù)為j， 則相應(yīng)的狀態(tài)就應(yīng)該從qi變換為qj,其中 i=0，1，2，N-1。 x = x1, x2,x3,xm 0, 1， ，base-1,例3-16構(gòu)造DFA，接收,0，1上的語(yǔ)言 L=0n1m2k|n,m,k=1,該語(yǔ)言的串的特點(diǎn)是，0在最前面，1在中間，2在最后，0、1和2不能交叉，順序也不能顛倒。 0、1和2的個(gè)數(shù)都至少為1個(gè)； 需要4個(gè)狀態(tài)：,q0：開(kāi)始狀態(tài),等待接收第1個(gè)0 q1：已經(jīng)接收第1個(gè)0，負(fù)責(zé)接收可能的多個(gè)0，等待接收第1個(gè)1； q2：已經(jīng)接收第1個(gè)1，負(fù)責(zé)接收可能的多個(gè)1，等待接收第1個(gè)2；,q3：已經(jīng)接收第1個(gè)2，負(fù)責(zé)接收可能的多個(gè)2。,狀態(tài)轉(zhuǎn)移圖(省略陷阱狀態(tài)),q0,0,1,0,1,2,2,q1,q2,q3,思考1,補(bǔ)充陷阱狀態(tài)及對(duì)應(yīng)的狀態(tài)函數(shù)。,思考2 DFA是否可以為(省略陷阱狀態(tài)),q0,0,1,0,1,2,2,q1,q2,q3,.4 不確定的有限狀態(tài)自動(dòng)機(jī),每個(gè)FSL都是右線性語(yǔ)言 (定理3-1),問(wèn)題,每個(gè)右線性語(yǔ)言是不是一個(gè)FSL？,例,接收語(yǔ)言aa，ab的FA,省略陷阱狀態(tài),q1,a,b,q0,q2,a,a,q3,該自動(dòng)機(jī)接收的語(yǔ)言L=aa，ab 是右線性語(yǔ)言； 但自動(dòng)機(jī)不是DFA。,(q0，a)=q1，q2 即沒(méi)有到達(dá)確定的惟一的狀態(tài)。 不確定的有限狀態(tài)自動(dòng)機(jī)-NFA,3.4.1不確定的有限狀態(tài)自動(dòng)機(jī),定義3-10 NFA是一個(gè)五元式， NFA =（Q，Q0，F(xiàn)） 其中： Q 是一個(gè)有限狀態(tài)的集合 是字母表,Q0 Q 是開(kāi)始狀態(tài)集合 F Q 是接收狀態(tài)集合,是Q2Q的狀態(tài)轉(zhuǎn)換函數(shù) 即 (q，a) 2Q NFA在狀態(tài)q，掃描字母a后到達(dá) 可能的下一狀態(tài)集合。,NFA與DFA,NFA有一個(gè)可能的開(kāi)始狀態(tài)集合和可能的下一狀態(tài)集合 其余的同DFA。,NFA與DFA的重要區(qū)別在于 轉(zhuǎn)移函數(shù)的不同。 (q，x)對(duì)應(yīng)的是狀態(tài)集合Q的一個(gè)子集,FA處于狀態(tài)q,DFA對(duì)每個(gè)字母只有惟一的狀態(tài)轉(zhuǎn)移 NFA對(duì)某個(gè)字母可以有多個(gè)狀態(tài)轉(zhuǎn)移； NFA接收該字母時(shí),從多個(gè)狀態(tài)轉(zhuǎn)移中可以 非確定地選擇任意一個(gè)。,具體地,對(duì)于NFA， (q，a) Q (q，a) 有3種可能 (q，a) = (q，a) =q1 (q，a) =q1 ，q2，qn,或,或,(q，a)仍是一個(gè)狀態(tài)轉(zhuǎn)換函數(shù)，只是其值域發(fā)生了改變。 所有(q，a)對(duì)應(yīng)的所有子集元素個(gè)數(shù)都為1時(shí)，NFA退化為DFA,NFA停機(jī),NFA在兩種情況下自動(dòng)停機(jī)： 將輸入串掃描結(jié)束 (q，a)=(即對(duì)應(yīng)沒(méi)有定義),或,在掃描一個(gè)串w時(shí)，NFA的狀態(tài)發(fā)生轉(zhuǎn)換，可能會(huì)有多種情況： 可能在接收狀態(tài)時(shí)終止； 可能在非接收狀態(tài)時(shí)終止； 也可能在中途停止（中止）。,若至少存在一條路徑可以使NFA在掃描串w后到達(dá)接收狀態(tài) 則串w能被NFA所接收。,對(duì)于字母表上的NFA，它能接收的所有串的集合，稱為NFA能接收的語(yǔ)言。 記為 L(NFA),問(wèn)題,如何形式化定義L(NFA)?,定義 NFA擴(kuò)展?fàn)顟B(tài)轉(zhuǎn)換函數(shù),給定NFA，擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù) *：2Q*2Q 為 *(p，w)= Q 即NFA在狀態(tài)集合p時(shí)，掃描串w后到達(dá)可能的的狀態(tài)集合Q,NFA擴(kuò)展?fàn)顟B(tài)轉(zhuǎn)換函數(shù),若p= q1，q2，qn *（p，）=p,a,*(p，a) = (q，a)|qp =(q1, a),(q2, a),(qn, a),對(duì)于串w,w=a *(p， w) =*(p，a) = (q，a)| q*(p，),或,w= a *(p， w ) =*(p， a ) = *(q,)| q*(p， a ),L(NFA)表示被NFA所接收的語(yǔ)言 L(NFA)=w|w*且 *(Q0， w)F,它表示所有串w的集合 在NFA的狀態(tài)圖中，至少存在一條路徑 以w為標(biāo)記，能使NFA從某個(gè)開(kāi)始狀態(tài)到達(dá)某個(gè)接收狀態(tài)。,構(gòu)造NFA，分別接收語(yǔ)言,0*、 0+ (0+1)*、(0+1)+ 0、01 (0+1)*0 0(0+1) * 1 (0+1)*00(0+1)*,3.4.2 NFA的確定化,DFA可以轉(zhuǎn)換為NFA NFA可以轉(zhuǎn)換為DFA(確定化),定理3-3,*的一個(gè)子集L是一個(gè)FSL， 充要條件為 存在NFA，使得L(NFA)=L,證明：= 必要性,若L是FSL，則有L=L(DFA） DFA=(Q ， ， ， q0 ， F) 構(gòu)造 NFA=(Q，1，q0，F(xiàn)),1(q，a)=(q，a) 即把DFA的一個(gè)狀態(tài) 當(dāng)作 NFA的一個(gè)狀態(tài)集合 則 L=L(DFA)=L(NFA),證明: = 充分性,NFA=（Q，Q0，F(xiàn)） 語(yǔ)言L=L(NFA)* 構(gòu)造 DFA=( Q,，q0，F(xiàn)) 其中 Q=2Q,q0= Q0Q F Q =p|pQ 且 pF,(p，a)= (q，a)|qp 其中, pQ，a 即(q1，q2，qn，a) =(q1,a),(q2，a),(qn，a),即把NFA的一個(gè)狀態(tài)集合當(dāng)作是DFA的一個(gè)狀態(tài)。 則L=L(NFA)=L(DFA),NFA和DFA是可以互相轉(zhuǎn)換的，是等價(jià)的； 接收的語(yǔ)言類都是FSL。,例3-18,a,a,b,S2,A,b,S1,a,b,NFADFA,S1和S2是開(kāi)始狀態(tài) A是唯一的接收狀態(tài) 該NFA共有3個(gè)狀態(tài),對(duì)于DFA，最多可能有8個(gè)狀態(tài)： ，S1，S2，A，S1，A，S2，A，S1，S2，S1，S2，A,DFA狀態(tài)轉(zhuǎn)換函數(shù),S1，S2,S2,A,S2,A,S2,A,A,A,A,A,A,DFA狀態(tài)轉(zhuǎn)換圖,a,b,a,b,a,b,S1, S2,S2, A,A,注意：,若到達(dá)空集狀態(tài) 實(shí)際上就是陷阱狀態(tài)。,例3-19構(gòu)造NFA，接收,0，1上的語(yǔ)言，該語(yǔ)言的每個(gè)字符串擋成二進(jìn)制數(shù)時(shí)， 代表的數(shù)字能被2整除。,解1:直接構(gòu)造DFA(以0結(jié)尾的串),0,q2,q1,q0,0,1,0,1,1,解2：,正則表達(dá)式為：(0+1)*0 直接構(gòu)造NFA,0,1,q1,0,q0,轉(zhuǎn)換為DFA,0,q1,0,q0,1,1,例3-20 接收,語(yǔ)言L= w|wa,b,c+, |w|1, w中最后字母與第一個(gè)字母相同,1)給出該語(yǔ)言的正則表達(dá)式； 2)構(gòu)造NFA接受該語(yǔ)言； 3)將NFA轉(zhuǎn)換為等價(jià)的DFA。,解,1) 該語(yǔ)言的正則表達(dá)式: a(a+b+c)*a + b(a+b+c)*b + c(a+b+c)*c,解,2)構(gòu)造NFA接受該語(yǔ)言,解,3) 改造為DFA接受該語(yǔ)言： 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，接收,語(yǔ)言L= w|wa,b,c+, |w|0, w中最后字母與第一個(gè)字母相同 該語(yǔ)言的正則表達(dá)式: a(R)*a+b(R)*b+c(R)*c+a+b+c,例3-21接收,語(yǔ)言L= w| wa,b+, w中倒數(shù)第二個(gè)字母肯定在前面出現(xiàn)過(guò),1)給出該語(yǔ)言的正則表達(dá)式； 2)構(gòu)造NFA接受該語(yǔ)言； 3)將NFA轉(zhuǎn)換為等價(jià)的DFA。,解,1) 該語(yǔ)言的正則表達(dá)式: (a+b)*a(a+b)*a(a+b) + (a+b)*b(a+b)*b(a+b),解,2)構(gòu)造NFA接受該語(yǔ)言,解,3)將NFA轉(zhuǎn)換為等價(jià)的DFA,例:構(gòu)造NFA，接收,0，1上的語(yǔ)言; 該語(yǔ)言的每個(gè)句子必須包含00,正則表達(dá)式為： (0+1)*00(0+1)*,NFA,0,1,q2,0,q0,0,1,q1,0,構(gòu)造NFA，接收,0，1上的語(yǔ)言， 該語(yǔ)言的每個(gè)句子必須包含001,正則表達(dá)式為：(0+1)*001(0+1)*,NFA,0,1,q2,001,q0,0,1,例3-23構(gòu)造NFA，接收,0，1上的語(yǔ)言， 該語(yǔ)言每個(gè)句子必須不包含001,NFA,0,q1,0,1,1,q2,0,q0,例3-24構(gòu)造NFA，接收,0，1上的語(yǔ)言， 該語(yǔ)言的每個(gè)句子 以0開(kāi)頭，以1結(jié)尾。,NFA,q2,0,q0,0,1,q1,1,例3-25構(gòu)造NFA，接收,0，1上的語(yǔ)言，該語(yǔ)言的句子 若以1結(jié)尾,則該字符串長(zhǎng)度為偶數(shù) 若以0結(jié)尾,則該字符串長(zhǎng)度為奇數(shù),NFA (無(wú)),q4,0,1,0,1,0,q3,q2,q1,1,思考,若還需要接收，如何構(gòu)造NFA？,一般：,NFA適于構(gòu)造（已知正則表達(dá)式）的語(yǔ)言： 滿足條件 的語(yǔ)言 包含子串 以串開(kāi)始或結(jié)束 (倒數(shù))第個(gè)字母是 ,定理3-4,每個(gè)右線性語(yǔ)言(正則語(yǔ)言)是一個(gè)FSL。,證明,L是右線性語(yǔ)言，則L=L(G) G=（，V，S，P） 首先消除G中一般的產(chǎn)生式,構(gòu)造NFA 將文法非終結(jié)符當(dāng)作NFA的狀態(tài) 增加一個(gè)接收狀態(tài)q,NFA=(Q，Q0，F(xiàn)) 其中： Q=V U q Q0=S F=q,注意,若文法G中有S,即L 則開(kāi)始狀態(tài)S也是接收狀態(tài),(A，x)=B| AxB在P中 q|Ax在P中 所以，L=L(G)=L(NFA),而NFA又和DFA是等價(jià)的， 一個(gè)右線性語(yǔ)言也是一個(gè)FSL。,總之,右線性語(yǔ)言和FSL是等價(jià)的， 右線性文法產(chǎn)生右線性語(yǔ)言； 有限狀態(tài)自動(dòng)機(jī)接收FSL； 也都是正則集。,例3-26 構(gòu)造NFA，接收,0，1上的語(yǔ)言 L=0n1m2k|n,m,k0,NFA狀態(tài)轉(zhuǎn)移圖,q0,0,1,0,1,2,2,q1,q2,q3,或,q0,0,1,0,1,2,2,q1,q2,q3,例3-27構(gòu)造NFA，接收,0，1上的語(yǔ)言 L=0n1m2k|n,m,k=0,0,1,0,1,2,2,q3,q0,q1,q2,2,1,2,或 多個(gè)開(kāi)始狀態(tài)的NFA,1,0,2,2,q3,q1,q2,1,2,3.5 帶動(dòng)作的有限狀態(tài)自動(dòng)機(jī),對(duì)于FA（DFA、NFA），有 (q，)=q *(q，)=q (q，)=q *(P，)=P,表示FA不讀入任何字母(即只掃描空串時(shí))， FA的狀態(tài)不發(fā)生改變，并且讀頭不進(jìn)行移動(dòng)，仍然指向當(dāng)前非空字符。,若允許FA在不讀入任何字符時(shí),FA的狀態(tài)可以發(fā)生改變， 則FA為帶有動(dòng)作的FA,定義3-14帶動(dòng)作的有限狀態(tài)自動(dòng)機(jī),帶有動(dòng)作的FA是一個(gè)五元式, -FA=(Q，Q0，F(xiàn)) Q，Q0，F(xiàn)的含義同NFA,: Q 2Q (q，a) 2Q (q ，) 2Q,即,具體,(q,)=q 表示自動(dòng)機(jī)在狀態(tài)q時(shí)，不讀入任何字母，自動(dòng)機(jī)狀態(tài)不變 并且讀頭不移動(dòng)；,(q，a)= 表示自動(dòng)機(jī)在讀入字母a后，自動(dòng)機(jī)停機(jī)。,(q，a)=p1，p2，p3，pm 表示自動(dòng)機(jī)在讀入字母a后，自動(dòng)機(jī)的狀態(tài)可以選擇地改變?yōu)閜1，p2，p3，或者pm 并將讀頭向右移動(dòng)一個(gè)單元；,(q,)=q1，q2，q3，qn 表示自動(dòng)機(jī)在狀態(tài)q時(shí)，不讀入任何字母，自動(dòng)機(jī)的狀態(tài)可以選擇地改變?yōu)閝1，q2，q3，或qn 并且讀頭不移動(dòng)；,注意,帶有動(dòng)作的FA一定是NFA。 一般，記為-NFA。,例3-28,使用-NFA接收語(yǔ)言 L=0*1*2* 即 L=0n1m2k|n,m,k=0,狀態(tài)圖,0*1*2*,q0,q1,q2,2,0,1,對(duì)應(yīng)的5個(gè)函數(shù)為： (q0，0)=q0 (q0，)=q1 (q1，1)=q1 (q1，)=q2 (q2，2)=q2,定義3-15,對(duì)于-NFA ，qQ 從q開(kāi)始，掃描1個(gè)或多個(gè)后能夠到達(dá)的狀態(tài)集記為 -CLOSURE(q),-CLOSURE(q) = p|掃描后能夠從q到達(dá)p,對(duì)于-NFA， qQ -CLOSURE(q)是由遞歸規(guī)則確定的狀態(tài)集：,規(guī)則,(1) q-CLOSURE(q) 即任意狀態(tài)q接收空串，至少都能保持狀態(tài)q不變；,規(guī)則,(2) 如果p-CLOSURE(q) 則(p,) -CLOSURE(q) (3) 重復(fù)(2)，直到-CLOSURE(q)中的狀態(tài)不再增加為止。,注意,-CLOSURE(q)與(q,)不同,進(jìn)一步,對(duì)于狀態(tài)集合P，定義 -CLOSURE(P) = ,qP,-CLOSURE（q）,定義3-16 擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù),-NFA 擴(kuò)展?fàn)顟B(tài)轉(zhuǎn)換函數(shù) *： 2Q *2Q為 *（P，w）= Q 即自動(dòng)機(jī)在狀態(tài)集合P時(shí)，掃描串w后到達(dá)的狀態(tài)集合Q,空串,*(q,)=-CLOSURE(q) *(P,)=-CLOSURE(P),單個(gè)字母,*(q，a) =*(q，a) =-CLOSURE( (p,a) *(P，a)= *(q，a),qP,p*(q,),對(duì)于串wa,*(P,wa)=* (*(P,w),a),或,*(P,aw)=* (*(P,a),w),對(duì)于,-CLOSURE(q0)= -CLOSURE(q1)= -CLOSURE(q2)=,q0,q1，q2,q2,q1,q2,對(duì)于,*(q0,) =-CLOSURE(q0) =q0，q1，q2,*(q0,0) = *(q0, 0) =-CLOSURE( (p,0) p*(q0,) =-CLOSURE( (q0,0) (q1,0) (q2,0) =-CLOSURE(q0) =q0，q1，q2,*（q0,01） =* (*(q0,0),1) =* (q0,q1,q2,1) =-CLOSURE( (q0,1) (q1,1) (q2,1) =q1,q2,注意,*(q，)與(q，)不同,定理3-5,如果語(yǔ)言L被-NFA接收，則 該語(yǔ)言L也能夠被一個(gè)NFA接收,證明 ：,假設(shè)語(yǔ)言L被一個(gè)-NFA接收, -NFA =(Q，Q0，F(xiàn)),1)構(gòu)造 NFA1= (Q，1，Q0，F(xiàn)1) 其中:對(duì)于a 1(q，a)= *（q，a）,F1= Fq0 若 F-CLOSURE(q0) F1= F 若 F-CLOSURE(q0) =,2）證明對(duì)于w+,有 1(q0，w)= *（q0,w） ,結(jié)論,如果語(yǔ)言L被-NFA接收，則語(yǔ)言L也能夠被一個(gè)NFA接收,例3-29,將-NFA改造為等價(jià)的NFA。,q0,q1,q2,2,0,1,q1,q0,q2,2,0,1,0,1,1,2,0,1,2,例3-30構(gòu)造-NFA,接收,0，1上的語(yǔ)言 L=0k|k=0，k能夠被2或3整除 即L=02n或03m |n,m=0,q0,q1,q3,q2,q4,q5,0,0,0,0,0,思考,L=02n+3m |n,m0,請(qǐng)驗(yàn)證,q0,q5,q1,0,q2,0,q3,0,q4,0,0,0,0,思考：,-NFA轉(zhuǎn)換為NFA能否 先將-NFA轉(zhuǎn)換為“右線性”文法，再轉(zhuǎn)換為NFA？ 引進(jìn)單產(chǎn)生式AB,3.6 有限狀態(tài)自動(dòng)機(jī)的一些變形,有限狀態(tài)自動(dòng)機(jī)存在變形。,3.6.1雙向的有限狀態(tài)自動(dòng)機(jī),在處理輸入串的過(guò)程中， 雙向的有限狀態(tài)自動(dòng)機(jī)的讀頭 可以向右移動(dòng)一個(gè)單元； 也可以向左移動(dòng)一個(gè)單元； 也可以不移動(dòng)。,定義3-18,確定的雙向的有限狀態(tài)自動(dòng)機(jī)(2DFA)是一個(gè)五元式： 2DFA =（Q，q0，F(xiàn)） 其中，Q,q0，F(xiàn)的含義同DFA,：狀態(tài)轉(zhuǎn)換函數(shù)； QQL，R，N 對(duì)于qQ，a,(q，a)=p，D,2DFA在狀態(tài)q讀入字母a 自動(dòng)機(jī)狀態(tài)將變?yōu)閜狀態(tài) D=L 讀頭向左移動(dòng)一個(gè)單元 D=R 讀頭向左移動(dòng)一個(gè)單元 D=N 讀頭位置不變；,2DFA格局描述同DFA,2DFA =（Q，q0，F(xiàn)）接收的語(yǔ)言為L(zhǎng)(2DFA) L( 2DFA)=w|q0w=*q，qF,定理3-6,2DFA與DFA等價(jià)。 證明： 略。,可以定義不確定的雙向的有限狀態(tài)自動(dòng)機(jī)。,定義3-20,不確定雙向有限狀態(tài)自動(dòng)機(jī)2NFA是一個(gè)五元式： 2NFA =(Q， Q0，F(xiàn)) 其中 Q， Q0 ，F(xiàn)的含義同NFA,：狀態(tài)轉(zhuǎn)換函數(shù)； ：Q2QL，R，N,對(duì)于qQ，a, D1，D2，DmL,R,N，,(q,a)=(p1,D1),(p2,D2),(pm,Dm) 2NFA在狀態(tài)q讀入字母a 可以將狀態(tài)變?yōu)閜i 按照Di實(shí)現(xiàn)對(duì)讀頭的移動(dòng),定理3-7,2NFA與NFA等價(jià)。 證明： 略。,3.6.2帶輸出的有限狀態(tài)自動(dòng)機(jī),FA，對(duì)于某個(gè)輸入串w 得到的結(jié)論是: 是否接收該串； 或FA輸出 “是”或“否”。,存在許多有窮狀態(tài)系統(tǒng) 對(duì)于不同的輸入信號(hào)， 除系統(tǒng)內(nèi)部的狀態(tài)變化之外， 還向系統(tǒng)外部輸出各種信號(hào)。,模型圖,有限狀態(tài)系統(tǒng),輸入序列,輸入序列,典型帶輸出的有窮自動(dòng)機(jī)-Moore機(jī)和Mealy機(jī)。 由于它們帶有輸出，從抽象的角度考慮，就沒(méi)有必要再設(shè)置接收狀態(tài)（集）。,定義3-21,Moore機(jī)是一個(gè)六元式： Moore M=(Q, q0) 其中 Q，q0，的含義同F(xiàn)A ：輸出字母表,輸出函數(shù)：Q 對(duì)于qQ，a (q)=a 表示Moore機(jī)處于狀態(tài)q時(shí)輸出a,Moore機(jī),在讀入輸入串的過(guò)程中 狀態(tài)不斷發(fā)生改變 并且在每個(gè)狀態(tài)上都有輸出,對(duì)于輸入串a(chǎn)1a2a3an-1an,設(shè)(q0,a1)= q1 (q1,a2)= q2 (qn-2,an-1)= qn-1 (qn-1,an)= qn,則,Moore機(jī)的輸出序列可以表示為： (q0)(q1)(q2)(qn),如果輸入串的長(zhǎng)度為n,則Moore機(jī)的輸出串的長(zhǎng)度為n+1。,實(shí)際上,FA只是Moore機(jī)的一個(gè)特例。,若Moore機(jī)的輸出僅只有F或T 將輸出T的狀態(tài)當(dāng)作接收狀態(tài)，Moore機(jī)就是一般的FA。,例3-31設(shè)計(jì)Moore機(jī),=0，1 若將輸入串當(dāng)作二進(jìn)制數(shù)，則在讀入串的過(guò)程中， 希望輸出已經(jīng)讀過(guò)的（數(shù)字）串模3的余數(shù)。,分析,模3的余數(shù)只能是0、1和2 輸出字母表=0，1，2 狀態(tài)q0、q1和q2對(duì)應(yīng)3種余數(shù),狀態(tài)上的標(biāo)記表示Moore機(jī)在該狀態(tài)時(shí)的輸出,q0,q1,q2,0,1,2,0,0,0,1,1,1,當(dāng)輸入為1010時(shí) 狀態(tài)變換的序列為 q0 q1 q2 q2 q1 輸出 0 1 2 2 1,即,當(dāng)輸入時(shí)，輸出余數(shù)0 當(dāng)輸入1時(shí)，輸出余數(shù)1 當(dāng)輸入10時(shí)，輸出余數(shù)2 當(dāng)輸入101時(shí)，輸出余數(shù)2 當(dāng)輸入1010時(shí)，輸出余數(shù)1,定義3-2