第四五六講 有窮自動機(jī)

1、第4講 有窮自動機(jī)（1）1 一、DFA 一個確定的有窮自動機(jī)（DFA）M是一個五元組：M=（K，f，s，Z）其中1。K是一個非空有窮集，它的每個元素稱為一個狀態(tài)；2。是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱為輸入符號字母表；3。f是轉(zhuǎn)換函數(shù)，是在KK上的映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時，將轉(zhuǎn)換為下一個狀態(tài)kj，我們把kj稱作ki的一個后繼狀態(tài)；4。sK是唯一的一個初態(tài)；5。Z K是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。2DFA 例：DFA M=（S,U,V,Q, a,b, f, S, Q）其中 t 定義為：f（S，

2、a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q3DFA 的狀態(tài)圖表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb4DFA 的狀態(tài)轉(zhuǎn)換表f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q字母狀態(tài)00015DFA的確定性f:K X 是一個單值函數(shù)，即對任何的狀態(tài)k K,對于輸入符號a ,f(k,a)唯一地確定了下一個狀態(tài)。從狀態(tài)轉(zhuǎn)換圖來看，

3、若字母表含有n個輸入字符，那末任何一個狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個不同的輸入字符標(biāo)記。6DFA的擴(kuò)充 對于DFA=(K,f,S,Z),擴(kuò)充的映射為 f: k X *K定義為 （1）f(q, )=q （2）f(q,a )=f(f(q,a), ) 其中，q K,a , *7L(A)對于DFA=(K,f,s,Z),如果 f(s, )=qZ 則稱符號串可以被DFA所接受。DFA A所接受的符號串集，記為L(A) 8例：證明t=baab被如下的DFA所接受。DFA M=（S,U,V,Q, a,b,f, S, Q）其中 t 定義為：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）

4、=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb證明： f（S，baab）=f（f（S，b），aab）=f（V，aab）=f（f（V，a），ab）=f（U，ab）=f（f（U，a），b）=f（Q，b）=QQ屬于終態(tài)。得證。9二、NDFA定義 NDFA=K，f，S，Z，其中K為狀態(tài)的有窮非空集， 為有窮輸入字母表，f為K * 到K的子集的映像，SK是初始狀態(tài)集，Z K為終止?fàn)顟B(tài)集。10例子NDFA N=（S，P，Z，0，1，f，S，P，Z）其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=PSPZ00,1111狀

5、態(tài)圖表示11NDFA的擴(kuò)充 對于NDFA=(K,f,S,Z),擴(kuò)充的映射為 f: k X *K定義為 （1）f(q, )=q （2）f(q,a )=f(f(q,a), )=f(q1, )U f(q2, )UUf(qn, ), 其中，q K,a , *, f(q,a)=q1,q2,q3,qn12L(A)對于NDFA A=(K,f,S,Z),如果 qf(q0, ),q0S,qZ 則稱符號串可以被NDFA所接受。NDFA A所接受的符號串集，記為L(A) 13三、NDFA的確定化造表法目標(biāo)：NDFA A=（K，f，S，Z） DFA A= （K，f，S，Z）思想： q0為S所有元素構(gòu)成的一個狀態(tài)子集

6、= 以q0為出發(fā)點(diǎn)利用造表法產(chǎn)生新狀態(tài)直 至無新狀態(tài)產(chǎn)生，從而確定K和f Z為K中所有包含Z中元素的狀態(tài)子集 構(gòu)成的集合14第5講 有窮自動機(jī)（2）15 NDFA的確定化狀態(tài)集合I的-閉包-closure(I)，是一狀態(tài)集 a.任何狀態(tài)q I，則q -closure(I)；b.任何狀態(tài)q I，則q經(jīng)任意條 弧而能到達(dá)的狀態(tài)的q -closure(I) 。 例：I=1, -closure(I)=1,2； I=5, -closure(I)=5,6,2；12534687aaa16I=1,2, J = 5,3,4 ; Ia= -closure(5,3,4)=2,3,4,5,6,7,812534687a

7、aa狀態(tài)集合I的a弧轉(zhuǎn)換，Ia = -closure(J) ,其中J是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀態(tài)的全體。17對一個 NDFA 進(jìn)行確定化的算法：首先置該表的首行首列為 : -closure(Q0)對 = a1ak, 構(gòu)造一個k+1列的表。若某行的第一列的狀態(tài)已確定為I，則第i+1(i = 1,2,k)列的值為Iai，然后檢查該行上的所有狀態(tài)子集，看它是否已在第一列出現(xiàn)。若未出現(xiàn)，將其填加到后面的空行上。重復(fù)此過程，直到所有狀態(tài)子集均在第一列中出現(xiàn)。得到一個確定的有窮自動機(jī)：將每個狀態(tài)子集視為新的狀態(tài)，初態(tài)就是首行首列的狀態(tài)，終態(tài)是含有原終態(tài)的集合。18 NFA的確定化

8、例子4f35621iaaaabbbb194f35621iaaaabbbb20 等價的DFAaCDBAEFSbaaaaabbbbbabF21DFA的最小化（化簡）最小狀態(tài)DFA沒有多余狀態(tài)(死狀態(tài))沒有兩個狀態(tài)是互相等價（不可區(qū)別）兩個狀態(tài)s和t等價：滿足一致性同是終態(tài)或同是非終態(tài)蔓延性從s出發(fā)讀入某個aa和從 t出發(fā)讀入某個a到達(dá)的狀態(tài)等價。22消除多余狀態(tài)s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1s0s1s2

9、s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1s0s1s2s3s5s723DFA的化簡算法目的：合并DFA中的等價狀態(tài) 狀態(tài)等價的定義：若狀態(tài)q1與q2導(dǎo)出的符號串集合相等，則q1與q2等價，否則稱q1與q2可區(qū)分。方法： a.將狀態(tài)集合k分解為互不相交的子集，使每個子集中的狀態(tài)都是等價的，不同子集中的狀態(tài)則是可區(qū)分的 b.合并等價狀態(tài)24將下圖中的DFA M最小化1,2,3,4 5,6,71,2 3,4 5 6,71,2 3 4 5 6,71352746aaaaaaabbbbbbb13546aaaaabbbbb25正規(guī)式(regular expre

10、ssion)定義（正規(guī)式和它所表示的正規(guī)集）：設(shè)字母表為輔助字母表= ， 。1。 和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和；2。任何a ，a是上的一個正規(guī)式，它所表示的正規(guī)集為a；3。假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，那么，(e1), e1e2, e1e2, e1也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)。4。僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。26(e1), e1e2, e1e2, e1 L(e1), L(e1)L(e

11、2), L(e1)L(e2)， (L(e1)其中的“”讀為“或” ；“ ”讀為“連接”；“”讀為“閉包”（即，任意有限次的自重復(fù)連接）。在不致混淆時，括號可省去，但規(guī)定算符的優(yōu)先順序?yàn)椤啊薄ⅰ?”、“” 。連接符“ ”一般可省略不寫。27例4.2 令=a，b， 上的正規(guī)式和相應(yīng)的正規(guī)集的例子有：正規(guī)式 正規(guī)集a aaba,bab ab(ab)(ab)aa,ab,ba,bba ,a,a, 任意個a的串(ab) ,a,b,aa,ab 所有由a 和b組成的串(ab)(aabb)(ab)上所有含有兩個相繼 的a或兩個相繼的b組成 的串28例 =l，d，r=l(l d) 定義的正規(guī)集: l,ll,ld,

12、ldd,（標(biāo)識符）29兩個正規(guī)式等價若兩個正規(guī)式e1和e2所表示的正規(guī)集相同,則說e1和e2等價,寫作e1=e2。例如： e1= (ab)， e2 = ba又如： b(ab) = (ba)b30正規(guī)式的運(yùn)算律設(shè)r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：1。rs=sr “或”服從交換律2。r(st)=(rs)t“或”的可結(jié)合律3。(rs)t=r(st)“連接”的可結(jié)合律4。r(st)=rsrt (st)r=srtr分配律 5。 r=r, r=r是“連接”的恒等元素6。 rr=r r=rrr “或”的抽取律 31第6講 有窮自動機(jī)（3）32正規(guī)式和有窮自動機(jī)的等價性1. 對于上的NDFA M，可

13、以構(gòu)造一個上的正規(guī)式R,使得L(R)=L(M)。2.對于上的一個正規(guī)式R，可以構(gòu)造一個上的NDFA M，使得L(M)=L(R)。331. 對于上的NDFA M，可以構(gòu)造一個上的正規(guī)式R,使得L(R)=L(M)。第一步：在M的狀態(tài)轉(zhuǎn)換圖上加進(jìn)兩個結(jié)，一個為x結(jié)點(diǎn)，一個為y結(jié)點(diǎn)。從x結(jié)點(diǎn)用弧連接到M的所有初態(tài)結(jié)點(diǎn)，從M的所有終態(tài)結(jié)點(diǎn)用弧連接到y(tǒng)結(jié)點(diǎn)。形成一個與M等價的M,M只有一個初態(tài)x和一個終態(tài)y。第二步：逐步消去M中的所有結(jié)點(diǎn)，直至只剩下x和y。（消去規(guī)則見下頁）最后x和y結(jié)點(diǎn)間的弧上的標(biāo)記則為所求的正規(guī)式R。34123R1R213R1 R213R1R213R1| R2123R1R3R213R

14、1 R2* R335例：03124a,baaa,ba,bbb求正規(guī)式R3603124a,baaa,ba,bbbxy024a|baaa|ba|bbbxy37024a|baaa|ba|bbbxy0a|baa(a|b)*bb(a|b)*xy380a|baa(a|b)*bb(a|b)*xy0a|bxyaa(a|b)* |bb(a|b)*xy(a|b)* (aa |bb)(a|b)*(aa |bb)(a|b)*R=(a|b)* (aa |bb)(a|b)*392.對于上的一個正規(guī)式R，可以構(gòu)造一個上的NDFA M，使得L(M)=L(R)。40 xiy(a|b)*abbR=(a|b)*abbxjyabbia|bxjyabbiab繼續(xù)對abb進(jìn)行分解。2.對于上的一個正規(guī)式R，可以構(gòu)造一個上的NDFA M，使得L(M)=L(R)。41正規(guī)文法和有窮自動機(jī)間的轉(zhuǎn)換采用下面的規(guī)則從正規(guī)文法G直接構(gòu)造一個有窮自動機(jī)NDFA M，使