非確定型有窮自動機的極化

非確定型有窮自動機的極化

自動機理論是指研究各種自動處理的數(shù)學機器。實際計算機相當復雜，很難直接創(chuàng)建復雜的數(shù)學模型。因此，人們使用理想的計算機進行計算機特征的研究。這一模型的應用非常廣泛。窮自動機理論提供了計算機軟件工具的開發(fā)模式。這種模型可以很常見。它是計算機軟件和硬件研究的重要基本理論。在軟件方面，它為設計師提供了一種新的解決問題的想法和方法。它有幾個內(nèi)部模式或狀態(tài)，用于存儲過去輸入的相關信息。對于當前輸入，可以設置下一個步驟的狀態(tài)和操作。對于帶有窮自動機的狀態(tài)轉換圖，可以應用于帶有窮自動機的等效轉換圖和相應的算法，然后通過編程來實現(xiàn)。有窮自動機極小化問題的研究,在程序測試、模糊系統(tǒng)、概率自動機等方面具有重要意義.在等價的前提下,自動機的狀態(tài)越少,越節(jié)省軟件和硬件資源.朱征宇和朱慶生研究了有窮自動機的矩陣模型表示方法,并且給出了狀態(tài)自動機的基本代數(shù)性質及相應的物理意義.文獻從右不變等價關系的角度研究了非確定型有窮自動機的極小化.本文避免了文獻中對左右位置的討論,直接在有窮自動機的狀態(tài)集上定義等價關系,利用等價關系對自動機進行極小化后得到自動機識別的語言不變;本文還構造了一臺非確定型有窮自動機,它由兩臺確定型有窮自動機連接而成,由這兩臺確定型有窮自動機狀態(tài)集上的等價關系,可以構造這臺非確定有窮自動機狀態(tài)集上的等價關系;對這兩臺確定型有窮自動機分別利用等價關系進行極小化,可以得到如下結論:這臺非確定型有窮自動機極小化后的狀態(tài)復雜度,不大于分別將原來的兩臺確定型有窮自動機極小化后再連接的自動機的狀態(tài)復雜度.1確定型有窮自動機的構造及相關定義定義1.1一臺確定型有窮自動機DFA是一個五元組M=(Q,Σ,δ,q0,F),其中,Q是一個有窮集合,稱為狀態(tài)集;Σ是一個有窮集合,稱為字母表;δ:Q×Σ→Q是轉移函數(shù);q0∈Q是起始狀態(tài);F?Q是接受狀態(tài)集.定義1.2設M=(Q,Σ,δ,q0,F)是一臺確定型有窮自動機,ω=ω1ω2ω3…ωn是字母表Σ上的一個符號串.如果存在Q中的狀態(tài)序列r0,r1,r2,…,rn,滿足下述條件,則M接受ω:(1)r0=q0;(2)δ(ri,ωi+1)=ri+1;(3)rn∈F.記L(Μ)={ω∈Σ|Μ接受ω},稱為有窮自動機M所接受的語言.定義1.3設M=(Q,Σ,δ,q0,F)為一臺確定型有窮自動機(DFA),由δ定義函數(shù)δ*:Q*Σ*→Q如下:δ*=(q,ε)=q,δ*(q,ax)=δ*(δ(q,a),x),其中Σ*是指Σ上有窮符號串構成的集合.稱串x將狀態(tài)q帶到狀態(tài)δ*(q,x).對于x=a1a2a3…an,稱狀態(tài)序列q0,q1,q2,…,qn為串x將q0帶到狀態(tài)δ*(q0,x)的狀態(tài)軌跡,其中δi=δ*(q0,a1a2a3…ai)(1≤i≤n),記Q(q,x)={q0,q1,q2,…,qn}.定義1.4設M=(Q,Σ,δ,q0,F)為一臺確定型有窮自動機(DFA),在Q上引入等價關系～δ:p～δq?(?x∈Σ*)(δ*(p,x)∈F?δ*(q,x)∈F).對于確定型的有窮自動機M=(Q,Σ,δ,q0,F)借助等價關系～δ,取等價類[p]∶={q∈Q:p～δq}可以構造一臺M的極小化自動機:Μmin=({[p]:p∈Q},Σ,δmin,[q0],{[p]:p∈F}),其中,δmin([p],a)∶=δ(p,a).定義1.5設M=(Q,Σ,δ,q0,F)為一臺確定型有窮自動機(DFA),如果接受B的任何自動機的狀態(tài)數(shù)不低于|Q|,則稱L(M)=B是M接受語言B的極小化自動機.定理1.1L(M)=L(Mmin).證明:設M=(Q,Σ,δ,q0,F)是給定的一臺確定型有窮自動機.按上述方法構造自動機:Μmin=({[p]:p∈Q},Σ,δmin,[q0],{[p]:p∈F}),設x=a1a2a3…an∈L(M),則δ*(q0,x)∈F.在M中,假定串x將初始狀態(tài)q0帶到接受狀態(tài)qn∈F的狀態(tài)軌跡為:q0,q1,q2,…,qn,則在Mmin中,串x將初始狀態(tài)[q0]帶到接受狀態(tài)[qn]的狀態(tài)軌跡為:[q0],[q1],[q2],…,[qn].所以Mmin接受串x,則相應有L(M)?L(Mmin).反之,如果x∈L(Mmin),則在Mmin中,串x將初始狀態(tài)[q0]帶到接受狀態(tài)[pn],且pn∈F,其狀態(tài)軌跡為[q0],[p1],[p2],…,[pn].相應地,在M中,串x將初始狀態(tài)q0帶到接受狀態(tài)pn的狀態(tài)軌跡為:q0,p1,p2,…,pn,因此M接受串x,則L(Mmin)?L(M).從而L(M)=L(Mmin).定義1.6一臺非確定型有窮自動機是一個五元組N=(Q,Σ,δ,q0,F),其中,Q是一個有窮集合,稱為狀態(tài)集;∑是一個有窮集合,稱為字母表;δ:Q×Σε→Q是轉移函數(shù)(這里Σε=Σ∪{ε});q0∈Q是起始狀態(tài);F?Q是接受狀態(tài)集.2qq兩相關系定義2.1設M1=(Q1,Σ,δ1,q0,F1),M2=(Q2,Σ,δ2,q′0,F2)是兩臺確定型有窮自動機,構造一臺連接自動機N:Ν=Μ1?Μ2=(Q1∪Q2,Σ,δ,q0,F1∪F2)為一臺非確定型有窮自動機.本文取Q1∩Q2=?進行討論.δ(p,ω)={{δ1*(p,ω)},p∈Q1/F1;{δ1*(p,ω)},p∈F1且ω≠ε;{δ1*(p,ω)}∪{q0′},p∈F1且ω=ε;{δ2*(p,ω)},p∈Q2.定義2.2連接關系是指兩個關系進行笛卡爾積再從中選擇滿足一定條件記錄的運算.設選擇條件為F(可以為一個一般的條件表達式),則連接關系可記為R∞FS={t|t=(t1,t2)∩t1∈R∩t2∈S∩F(t)}.定義2.3設M1=(Q1,Σ,δ1,q0,F1),M2=(Q2,Σ,δ2,q′0,F2)是兩臺確定型有窮自動機,R1和R2分別是Q1和Q2上的等價關系.若對于p∈Q1,q∈Q2,且?ω∈Σ*,有δ*(p,ω)∩F1≠??δ*(q,ω)∩F2≠?,則稱〈p,q〉∈R1∞FR2.定義2.4設N=(Q,Σ,δ,q0,F)是一臺非確定型有窮自動機,在Q上引入等價關系R:若p,q∈Q且?ω∈Σ*,有δ*(p,ω)∩F≠??δ*(q,ω)∩F≠?,則稱〈p,q〉∈R.定理2.1設M1=(Q1,Σ,δ1,q0,F1),M2=(Q2,Σ,δ2,q′0,F2)是兩臺確定型有窮自動機,在狀態(tài)Q1和Q2上分別引入等價關系R1和R2,令Ν=Μ1?Μ2=(Q1∪Q2,Σ,δ,q0,F1∪F2),則在Q1∪Q2上的等價關系為R=R1∪R2∪R1∞FR2∪R2∞FR1.證明:分兩步.令R′=R1∪R2∪R1∞FR2∪R2∞FR1.(1)證明R′是一個等價關系.1)自反性.?p∈Q1∪Q2,則p∈Q1或p∈Q2,有〈p,p〉∈R1或〈p,p〉∈R2,從而有〈p,p〉∈R′.2)對稱性.(i)?p,q∈Q1∪Q2,若p,q∈Q1且〈p,q〉∈R1.由R1是等價關系可知,?q,p?∈R1??q,p?∈R′;(ii)?p,q∈Q1∪Q2,若p,q∈Q2與(i)類似可得;(iii)?p,q∈Q1∪Q2,若p∈Q1,q∈Q2,且〈p,q〉∈R1∞FR2,則?ω∈Σ*,δ*(p,ω)∩F1≠??δ*(q,ω)∩F2≠?.反之,若q∈Q2,p∈Q1,則?ω∈Σ*,δ*(q,ω)∩F2≠??δ*(p,ω)∩F1≠?,即有?q,p?∈R2∞FR1??q,p?∈R′;(iv)?p,q∈Q1∪Q2,若p∈Q2,q∈Q1,類似證明.3)傳遞性.(i)?p,q,r∈Q1∪Q2,若p,q,r∈Q1或p,q,r∈Q2,分別利用R1或R2是等價關系即可得到傳遞性成立;(ii)?p,q,r∈Q1∪Q2,若p,q∈Q1,r∈Q2,且〈p,q〉∈R1,〈q,r〉∈R1∞FR2,則有?ω∈Σ*,δ1*(p,ω)∈F1?δ1*(q,ω)∈F1,δ*(q,ω)∩F1≠??δ*(r,ω)∩F2≠?;于是由定義2.3可得{δ1*(p,ω)}∩F1≠??{δ1*(q,ω)}∩F1≠??δ*(p,ω)∩F1≠??δ*(q,ω)∩F1≠??δ*(r,ω)∩F2≠???p,r?∈R1∞FR2??p,r?∈R′;(iii)p∈Q1,q,r∈Q2,與(ii)類似可以證明;(iv)若p∈Q1,q∈Q2,r∈Q1,且〈p,q〉∈R1∞FR2,〈q,r〉∈R2∞FR1,則有?ω∈Σ*,δ*(p,ω)∩F1≠??δ*(q,ω)∩F2≠?,δ*(q,ω)∩F2≠??δ*(r,ω)∩F1≠?.若p,r?F1,則有δ*(p,ω)={δ1*(p,ω)},δ*(r,ω)={δ1*(r,ω)}?δ1*(p,ω)∈F1?δ1*(r,ω)∈F1??p,r?∈R1??p,r?∈R′.若p?F1且r∈F1或p∈F1,r∈F1同理可證;(v)若p∈Q2,q∈Q1,r∈Q2,且有條件〈p,q〉∈R2∞FR1,〈q,r〉∈R1∞FR2,?ω∈Σ*,有δ*(p,ω)∩F2≠??δ*(q,ω)∩F1≠?,δ*(q,ω)∩F1≠??δ*(r,ω)∩F2≠??δ*(p,ω)∩F2≠??δ*(r,ω)∩F2≠?,由定義可知δ*(p,ω)={δ*2(p,ω)}和δ*(r,ω)={δ*2(r,ω)},于是δ2*(p,ω)∈F2?δ2*(r,ω)∈F2??p,r?∈R2??p,r?∈R′.所以R′是等價關系.(2)證明R=R′.1)證明R′?R.(i)若〈p,q〉∈R′,且〈p,q〉∈R1或〈p,q〉∈R2,即?ω∈Σ*,有δ1*(p,ω)∈F1?δ1*(q,ω)∈F1,δ2*(p,ω)∈F2?δ2*(q,ω)∈F2,則由NFA的定義有δ*(p,ω)∩F≠??δ*(q,ω)∩F≠???p,q?∈R;(ii)〈p,q〉∈R′且〈p,q〉∈R1∞FR2,即?ω∈Σ*,有δ*(p,ω)∩F1≠??δ*(q,ω)∩F2≠??δ*(p,ω)∩F≠??δ*(q,ω)∩F≠???p,q?∈R;(iii)〈p,q〉∈R2∞FR1同理可證.〈p,q〉∈R.則有R′?R.反之:(i)若p,q∈Q1/F1,則δ*(p,ω)={δ1*(p,ω)}?Q1,{δ1*(p,ω)}∩F≠??{δ1*(q,ω)}∩F≠??δ1*(p,ω)∈F1?δ1*(q,ω)∈F1??p,q?∈R1??p,q?∈R′;(ii)若p,q∈Q1/F1,q∈F1同理可得;(iii)若p∈Q1/F1,q∈Q2,則有:?ω∈Σ*,δ*(p,ω)∩F≠??δ*(q,ω)∩F≠??{δ1*(p,ω)}∩F1≠??{δ2*(q,ω)}∩F2≠???p,q?∈R1∞FR2??p,q?∈R′;(iv)若p∈F1,q∈Q2,同理可證結論〈p,q〉∈R?〈p,q〉∈R′,所以R?R′.綜上所述,可得R=R1∪R2∪R1∞FR2∪R2∞FR1=R′.定義2.5設N=(Q,Σ,δ,q0,F)是一臺非確定型有窮自動機,ω是字母表Σ上的一個符號串,如果可將ω寫成ω=y1y2…ym,這里每個yi∈Σε=Σ∪{ε}并且存在Q中的狀態(tài)序列r0,r1,r2,…,rm,滿足下述條件:(1)r0=q0;(2)ri+1∈δ(ri,ωi+1),i=0,1,2,…,m-1;(3)rm∈F.則稱非確定型有窮自動機N接受串ω.定義2.6設N=(Q,Σ,δ,q0,F)為一臺非確定型有窮自動機,由狀態(tài)集Q上的等價關系R所確定的等價類[p]∶={q∈Q:〈p,q〉∈R},則N的極小化自動機可表示為Μmin=({[p]:p∈Q},Σ,δmin,[q0],{[p]:p∈F}),其中δmin([p],a)∶=δ(p,a).定義2.6由定義2.4的等價關系定義一個等價類,從而對非確定型有窮自動機進行狀態(tài)極小化.定理2.2L(N)=L(Nmin).證明:Mmin=({[p]:p∈Q},Σ,δmin,[q0],{[p]:p∈F}),設x=a1a2a3…an∈L(N),則δ*(q0,x)∩F≠?,即在N中一定存在一個分支q0,q1,q2,…,qn,串x將初始狀態(tài)q0帶到接受狀態(tài)qn∈F,則同樣對應這個分支[q0],[q1],[q2],…,[qn],串x將初始狀態(tài)[q0]帶到接受狀態(tài)[qn],且qn∈F,于是x∈L(Nmin).反之,若x∈L(Nmin),則在Nmin中存在一個分支,串x將[q0]帶到[qn],qn∈F對應N中的軌跡q0,q1,q2,…,qn,且qn∈F,所以x∈L(N).因此L(N)=L(Nmin).證畢.定理2.2表明非確定有窮自動機最小化后識別的語言不會改變.證明與前面相似(但要修改),只需取非確定有窮自動機能夠出現(xiàn)接受狀態(tài)的分支來分析即可.推論2.1L(M1。M2)=L((M1。M2)min).定理2.3M1=(Q1,Σ,δ1,q0,F1),M2=(Q2,Σ,δ2,q′0,F2)是兩臺有窮自動機,Q1上引入等價關系R1,Q2上引入等價關系R2,分別對M1,M2進行極小化,得到Μ1′=(Q1′,Σ,δ1min,[q0],F1′),Μ2′=(Q2′,Σ,δ2min,[q0′],F2′),則Νmin=(Μ1?Μ2)min=(Q,Σ,δ,[q0],F),|Q|≤|Q1′|+|Q2′|=|Q1′∪Q2′|.證明:設|Q1|=Κ1,|Q2|=Κ2,利用R1將M1狀態(tài)極小化,滿足R1的等價關系同樣滿足R=R1∪R2∪R1∞FR2∪R2∞FR1,并且R在Q1∪Q2上也可以按照等價關系進行狀態(tài)合并.滿足R2的等價關