第四五六講 有窮自動機

第四五六講有窮自動機第一頁，共四十三頁，2022年，8月28日一、DFA一個確定的有窮自動機（DFA）M是一個五元組：M=（K，Σ，f，s，Z）其中1。K是一個非空有窮集，它的每個元素稱為一個狀態(tài)；2。Σ是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱Σ為輸入符號字母表；3。f是轉換函數，是在K×Σ→K上的映射，即，如f（ki，a）=kj，（ki∈K，kj∈K）就意味著，當前狀態(tài)為ki，輸入符為a時，將轉換為下一個狀態(tài)kj，我們把kj稱作ki的一個后繼狀態(tài)；4。s∈K是唯一的一個初態(tài)；5。ZK是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結束狀態(tài)。第二頁，共四十三頁，2022年，8月28日DFA例：DFAM=（{S,U,V,Q},{a,b},f,S,{Q}）其中t定義為：f（S，a）=U f（V，a）=Uf（S，b）=V f（v，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q第三頁，共四十三頁，2022年，8月28日DFA的狀態(tài)圖表示f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QbSUVQaaaba，bb第四頁，共四十三頁，2022年，8月28日DFA的狀態(tài)轉換表f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q字母狀態(tài)0001第五頁，共四十三頁，2022年，8月28日DFA的確定性f:KXΣ是一個單值函數，即對任何的狀態(tài)k∈K,對于輸入符號a∈Σ,f(k,a)唯一地確定了下一個狀態(tài)。從狀態(tài)轉換圖來看，若字母表Σ含有n個輸入字符，那末任何一個狀態(tài)結點最多有n條弧射出，而且每條弧以一個不同的輸入字符標記。第六頁，共四十三頁，2022年，8月28日DFA的擴充對于DFA=(K,Σ,f,S,Z),擴充的映射為f:kXΣ*K定義為（1）f(q,ε)=q（2）f(q,aα)=f(f(q,a),α)其中，q∈K,a∈Σ,α∈Σ*第七頁，共四十三頁，2022年，8月28日L(A)對于DFA=(K,Σ,f,s,Z),如果f(s,α)=q∈Z則稱符號串α可以被DFA所接受。DFAA所接受的符號串集，記為L(A)

第八頁，共四十三頁，2022年，8月28日例：證明t=baab被如下的DFA所接受。DFAM=（{S,U,V,Q},{a,b},f,S,{Q}）其中t定義為：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（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)。得證。第九頁，共四十三頁，2022年，8月28日二、NDFA定義NDFA=K，，f，S，Z，其中K為狀態(tài)的有窮非空集，為有窮輸入字母表，f為K*到K的子集的映像，SK是初始狀態(tài)集，ZK為終止狀態(tài)集。第十頁，共四十三頁，2022年，8月28日例子NDFAN=（{S，P，Z}，{0，1}，f，{S，P}，{Z}）其中

f（S，0）={P}f（S，1）={S，Z}f（P，1）={Z}f（Z，0）={P}f（Z，1）={P}SPZ00,1111狀態(tài)圖表示第十一頁，共四十三頁，2022年，8月28日NDFA的擴充對于NDFA=(K,Σ,f,S,Z),擴充的映射為f:kXΣ*K定義為（1）f(q,ε)=q（2）f(q,aα)=f(f(q,a),α)=f(q1,α)Uf(q2,α)U……Uf(qn,α),其中，q∈K,a∈Σ,α∈Σ*,f(q,a)={q1,q2,q3,……qn}第十二頁，共四十三頁，2022年，8月28日L(A)對于NDFAA=(K,Σ,f,S,Z),如果q∈f(q0,α),q0∈S,q∈Z則稱符號串α可以被NDFA所接受。NDFAA所接受的符號串集，記為L(A)

第十三頁，共四十三頁，2022年，8月28日三、NDFA的確定化—造表法目標：NDFAA=（K，∑，f，S，Z）DFAA’=（K’，∑’，f’，S’，Z’）思想：q0為S所有元素構成的一個狀態(tài)子集

∑’=∑

以q0為出發(fā)點利用造表法產生新狀態(tài)直

至無新狀態(tài)產生，從而確定K’和f’Z’為K’中所有包含Z中元素的狀態(tài)子集構成的集合第十四頁，共四十三頁，2022年，8月28日第5講有窮自動機（2）第十五頁，共四十三頁，2022年，8月28日

NDFA的確定化狀態(tài)集合I的ε-閉包ε-closure(I)，是一狀態(tài)集a.任何狀態(tài)q∈I，則q∈ε-closure(I)；b.任何狀態(tài)q∈I，則q經任意條ε弧而能到達的狀態(tài)的q’∈ε-closure(I)。例：I={1},-closure(I)={1,2}；I={5},-closure(I)={5,6,2}；12534687aaa第十六頁，共四十三頁，2022年，8月28日I={1,2},J={5,3,4};Ia=-closure({5,3,4})={2,3,4,5,6,7,8}12534687aaa狀態(tài)集合I的a弧轉換，Ia=ε-closure(J),其中J是所有那些可從I中的某一狀態(tài)經過一條a弧而到達的狀態(tài)的全體。第十七頁，共四十三頁，2022年，8月28日對一個NDFA進行確定化的算法：首先置該表的首行首列為:-closure(Q0)對={a1…ak},構造一個k+1列的表。若某行的第一列的狀態(tài)已確定為I，則第i+1(i=1,2,…,k)列的值為Iai，然后檢查該行上的所有狀態(tài)子集，看它是否已在第一列出現。若未出現，將其填加到后面的空行上。重復此過程，直到所有狀態(tài)子集均在第一列中出現。得到一個確定的有窮自動機：將每個狀態(tài)子集視為新的狀態(tài)，初態(tài)就是首行首列的狀態(tài)，終態(tài)是含有原終態(tài)的集合。第十八頁，共四十三頁，2022年，8月28日

εNFA的確定化例子4f35621iaaaabbbb第十九頁，共四十三頁，2022年，8月28日4f35621iaaaabbbb第二十頁，共四十三頁，2022年，8月28日等價的DFAaCDBAEFSbaaaaabbbbbabF第二十一頁，共四十三頁，2022年，8月28日DFA的最小化（化簡）最小狀態(tài)DFA沒有多余狀態(tài)(死狀態(tài))沒有兩個狀態(tài)是互相等價（不可區(qū)別）兩個狀態(tài)s和t等價：滿足一致性——同是終態(tài)或同是非終態(tài)蔓延性——從s出發(fā)讀入某個aa和從 t出發(fā)讀入某個a到達的狀態(tài)等價。第二十二頁，共四十三頁，2022年，8月28日消除多余狀態(tài)s1s5

s2s7

s2s5

s5s7

s5s6

s3s1

s8s0

s0s1

s3s601s0

s1

s2

s3

s4

s5

s6

s7

s8s1s5

s2s7

s2s5

s5s7

s5s6

s3s1

s8s0

s0s1

s3s601s0

s1

s2

s3

s4

s5

s6

s7

s8s1s5

s2s7

s2s5

s5s7

s3s1

s0s101s0

s1

s2

s3

s5

s7第二十三頁，共四十三頁，2022年，8月28日DFA的化簡算法目的：合并DFA中的等價狀態(tài)

狀態(tài)等價的定義：若狀態(tài)q1與q2導出的符號串集合相等，則q1與q2等價，否則稱q1與q2可區(qū)分。方法：a.將狀態(tài)集合k分解為互不相交的子集，使每個子集中的狀態(tài)都是等價的，不同子集中的狀態(tài)則是可區(qū)分的b.合并等價狀態(tài)第二十四頁，共四十三頁，2022年，8月28日將下圖中的DFAM最小化{1,2,3,4}{5,6,7}{1,2}{3,4}{5}{6,7}{1,2}{3}{4}{5}{6,7}1352746aaaaaaabbbbbbb13546aaaaabbbbb第二十五頁，共四十三頁，2022年，8月28日正規(guī)式(regularexpression)定義（正規(guī)式和它所表示的正規(guī)集）：設字母表為輔助字母表‘={，，，，，，}。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。僅由有限次使用上述三步驟而定義的表達式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。第二十六頁，共四十三頁，2022年，8月28日(e1),

e1e2,

e1e2,

e1L(e1),

L(e1)∪L(e2),

L(e1)L(e2)，

(L(e1))

其中的“”讀為“或”；“”讀為“連接”；“”讀為“閉包”（即，任意有限次的自重復連接）。在不致混淆時，括號可省去，但規(guī)定算符的優(yōu)先順序為“”、“”、“”。連接符“”一般可省略不寫。第二十七頁，共四十三頁，2022年，8月28日例4.2令={a，b}，上的正規(guī)式和相應的正規(guī)集的例子有：正規(guī)式 正規(guī)集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,a,……任意個a的串}(ab) {,a,b,aa,ab……所有由a 和b組成的串}(ab)(aabb)(ab) {上所有含有兩個相繼 的a或兩個相繼的b組成 的串}第二十八頁，共四十三頁，2022年，8月28日例={l，d}，r=l(ld)定義的正規(guī)集:{l,ll,ld,ldd,……}（標識符）第二十九頁，共四十三頁，2022年，8月28日兩個正規(guī)式等價若兩個正規(guī)式e1和e2所表示的正規(guī)集相同,則說e1和e2等價,寫作e1=e2。例如：e1=(ab)，e2=ba又如：b(ab)=(ba)b

第三十頁，共四十三頁，2022年，8月28日正規(guī)式的運算律設r,s,t為正規(guī)式，正規(guī)式服從的代數規(guī)律有：1。rs=sr “或”服從交換律2。r(st)=(rs)t “或”的可結合律3。(rs)t=r(st) “連接”的可結合律4。r(st)=rsrt (st)r=srtr 分配律5。r=r,r=r 是“連接”的恒等元素6。rr=r r=rrr… “或”的抽取律第三十一頁，共四十三頁，2022年，8月28日第6講有窮自動機（3）第三十二頁，共四十三頁，2022年，8月28日正規(guī)式和有窮自動機的等價性1.對于∑上的NDFAM，可以構造一個∑上的正規(guī)式R,使得L(R)=L(M)。2.對于∑上的一個正規(guī)式R，可以構造一個∑上的NDFAM，使得L(M)=L(R)。第三十三頁，共四十三頁，2022年，8月28日1.對于∑上的NDFAM，可以構造一個∑上的正規(guī)式R,使得L(R)=L(M)。第一步：在M的狀態(tài)轉換圖上加進兩個結，一個為x結點，一個為y結點。從x結點用ε弧連接到M的所有初態(tài)結點，從M的所有終態(tài)結點用ε弧連接到y結點。形成一個與M等價的M’,M’只有一個初態(tài)x和一個終態(tài)y。第二步：逐步消去M’中的所有結點，直至只剩下x和y。（消去規(guī)則見下頁）最后x和y結點間的弧上的標記則為所求的正規(guī)式R。第三十四頁，共四十三頁，2022年，8月28日123R1R213R1R213R1R213R1|

R2123R1R3R213R1R2*

R3第三十五頁，共四十三頁，2022年，8月28日例：03124a,baaa,ba,bbb求正規(guī)式R第三十六頁，共四十三頁，2022年，8月28日03124a,baaa,ba,bbbxyεεε024a|baaa|ba|bbbxyεεε第三十七頁，共四十三頁，2022年，8月28日024a|baaa|ba|bbbxyεεε0a|baa(a|b)*bb(a|b)*xyε第三十八頁，共四十三頁，2022年，8月28日0a|baa(a|b)*bb(a|b)*xyε0