有限自動機理論3章有限狀態(tài)自動機.ppt

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