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

第四五六講有窮自動(dòng)機(jī)第一頁(yè)，共四十三頁(yè)，2022年，8月28日一、DFA一個(gè)確定的有窮自動(dòng)機(jī)（DFA）M是一個(gè)五元組：M=（K，Σ，f，s，Z）其中1。K是一個(gè)非空有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2。Σ是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱Σ為輸入符號(hào)字母表；3。f是轉(zhuǎn)換函數(shù)，是在K×Σ→K上的映射，即，如f（ki，a）=kj，（ki∈K，kj∈K）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把kj稱作ki的一個(gè)后繼狀態(tài)；4。s∈K是唯一的一個(gè)初態(tài)；5。ZK是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。第二頁(yè)，共四十三頁(yè)，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第三頁(yè)，共四十三頁(yè)，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第四頁(yè)，共四十三頁(yè)，2022年，8月28日DFA的狀態(tài)轉(zhuǎn)換表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第五頁(yè)，共四十三頁(yè)，2022年，8月28日DFA的確定性f:KXΣ是一個(gè)單值函數(shù)，即對(duì)任何的狀態(tài)k∈K,對(duì)于輸入符號(hào)a∈Σ,f(k,a)唯一地確定了下一個(gè)狀態(tài)。從狀態(tài)轉(zhuǎn)換圖來(lái)看，若字母表Σ含有n個(gè)輸入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個(gè)不同的輸入字符標(biāo)記。第六頁(yè)，共四十三頁(yè)，2022年，8月28日DFA的擴(kuò)充對(duì)于DFA=(K,Σ,f,S,Z),擴(kuò)充的映射為f:kXΣ*K定義為（1）f(q,ε)=q（2）f(q,aα)=f(f(q,a),α)其中，q∈K,a∈Σ,α∈Σ*第七頁(yè)，共四十三頁(yè)，2022年，8月28日L(A)對(duì)于DFA=(K,Σ,f,s,Z),如果f(s,α)=q∈Z則稱符號(hào)串α可以被DFA所接受。DFAA所接受的符號(hào)串集，記為L(zhǎng)(A)

第八頁(yè)，共四十三頁(yè)，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)。得證。第九頁(yè)，共四十三頁(yè)，2022年，8月28日二、NDFA定義NDFA=K，，f，S，Z，其中K為狀態(tài)的有窮非空集，為有窮輸入字母表，f為K*到K的子集的映像，SK是初始狀態(tài)集，ZK為終止?fàn)顟B(tài)集。第十頁(yè)，共四十三頁(yè)，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)圖表示第十一頁(yè)，共四十三頁(yè)，2022年，8月28日NDFA的擴(kuò)充對(duì)于NDFA=(K,Σ,f,S,Z),擴(kuò)充的映射為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}第十二頁(yè)，共四十三頁(yè)，2022年，8月28日L(A)對(duì)于NDFAA=(K,Σ,f,S,Z),如果q∈f(q0,α),q0∈S,q∈Z則稱符號(hào)串α可以被NDFA所接受。NDFAA所接受的符號(hào)串集，記為L(zhǎng)(A)

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

∑’=∑

以q0為出發(fā)點(diǎn)利用造表法產(chǎn)生新?tīng)顟B(tài)直

至無(wú)新?tīng)顟B(tài)產(chǎn)生，從而確定K’和f’Z’為K’中所有包含Z中元素的狀態(tài)子集構(gòu)成的集合第十四頁(yè)，共四十三頁(yè)，2022年，8月28日第5講有窮自動(dòng)機(jī)（2）第十五頁(yè)，共四十三頁(yè)，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經(jīng)任意條ε弧而能到達(dá)的狀態(tài)的q’∈ε-closure(I)。例：I={1},-closure(I)={1,2}；I={5},-closure(I)={5,6,2}；12534687aaa第十六頁(yè)，共四十三頁(yè)，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弧轉(zhuǎn)換，Ia=ε-closure(J),其中J是所有那些可從I中的某一狀態(tài)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)的全體。第十七頁(yè)，共四十三頁(yè)，2022年，8月28日對(duì)一個(gè)NDFA進(jìn)行確定化的算法：首先置該表的首行首列為:-closure(Q0)對(duì)={a1…ak},構(gòu)造一個(gè)k+1列的表。若某行的第一列的狀態(tài)已確定為I，則第i+1(i=1,2,…,k)列的值為Iai，然后檢查該行上的所有狀態(tài)子集，看它是否已在第一列出現(xiàn)。若未出現(xiàn)，將其填加到后面的空行上。重復(fù)此過(guò)程，直到所有狀態(tài)子集均在第一列中出現(xiàn)。得到一個(gè)確定的有窮自動(dòng)機(jī)：將每個(gè)狀態(tài)子集視為新的狀態(tài)，初態(tài)就是首行首列的狀態(tài)，終態(tài)是含有原終態(tài)的集合。第十八頁(yè)，共四十三頁(yè)，2022年，8月28日

εNFA的確定化例子4f35621iaaaabbbb第十九頁(yè)，共四十三頁(yè)，2022年，8月28日4f35621iaaaabbbb第二十頁(yè)，共四十三頁(yè)，2022年，8月28日等價(jià)的DFAaCDBAEFSbaaaaabbbbbabF第二十一頁(yè)，共四十三頁(yè)，2022年，8月28日DFA的最小化（化簡(jiǎn)）最小狀態(tài)DFA沒(méi)有多余狀態(tài)(死狀態(tài))沒(méi)有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）兩個(gè)狀態(tài)s和t等價(jià)：滿足一致性——同是終態(tài)或同是非終態(tài)蔓延性——從s出發(fā)讀入某個(gè)aa和從 t出發(fā)讀入某個(gè)a到達(dá)的狀態(tài)等價(jià)。第二十二頁(yè)，共四十三頁(yè)，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第二十三頁(yè)，共四十三頁(yè)，2022年，8月28日DFA的化簡(jiǎn)算法目的：合并DFA中的等價(jià)狀態(tài)

狀態(tài)等價(jià)的定義：若狀態(tài)q1與q2導(dǎo)出的符號(hào)串集合相等，則q1與q2等價(jià)，否則稱q1與q2可區(qū)分。方法：a.將狀態(tài)集合k分解為互不相交的子集，使每個(gè)子集中的狀態(tài)都是等價(jià)的，不同子集中的狀態(tài)則是可區(qū)分的b.合并等價(jià)狀態(tài)第二十四頁(yè)，共四十三頁(yè)，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第二十五頁(yè)，共四十三頁(yè)，2022年，8月28日正規(guī)式(regularexpression)定義（正規(guī)式和它所表示的正規(guī)集）：設(shè)字母表為輔助字母表‘={，，，，，，}。1。和都是上的正規(guī)式，它們所表示的正規(guī)集分別為{}和；2。任何a，a是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a}；3。假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正規(guī)式,它們所表示的正規(guī)集分別為L(zhǎng)(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))。4。僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。第二十六頁(yè)，共四十三頁(yè)，2022年，8月28日(e1),

e1e2,

e1e2,

e1L(e1),

L(e1)∪L(e2),

L(e1)L(e2)，

(L(e1))

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

第三十頁(yè)，共四十三頁(yè)，2022年，8月28日正規(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… “或”的抽取律第三十一頁(yè)，共四十三頁(yè)，2022年，8月28日第6講有窮自動(dòng)機(jī)（3）第三十二頁(yè)，共四十三頁(yè)，2022年，8月28日正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性1.對(duì)于∑上的NDFAM，可以構(gòu)造一個(gè)∑上的正規(guī)式R,使得L(R)=L(M)。2.對(duì)于∑上的一個(gè)正規(guī)式R，可以構(gòu)造一個(gè)∑上的NDFAM，使得L(M)=L(R)。第三十三頁(yè)，共四十三頁(yè)，2022年，8月28日1.對(duì)于∑上的NDFAM，可以構(gòu)造一個(gè)∑上的正規(guī)式R,使得L(R)=L(M)。第一步：在M的狀態(tài)轉(zhuǎn)換圖上加進(jìn)兩個(gè)結(jié)，一個(gè)為x結(jié)點(diǎn)，一個(gè)為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)。形成一個(gè)與M等價(jià)的M’,M’只有一個(gè)初態(tài)x和一個(gè)終態(tài)y。第二步：逐步消去M’中的所有結(jié)點(diǎn)，直至只剩下x和y。（消去規(guī)則見(jiàn)下頁(yè)）最后x和y結(jié)點(diǎn)間的弧上的標(biāo)記則為所求的正規(guī)式R。第三十四頁(yè)，共四十三頁(yè)，2022年，8月28日123R1R213R1R213R1R213R1|

R2123R1R3R213R1R2*

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