非确定型有穷自动机的极化

非确定型有穷自动机的极化

自动机理论是指研究各种自动处理的数学机器。实际计算机相当复杂，很难直接创建复杂的数学模型。因此，人们使用理想的计算机进行计算机特征的研究。这一模型的应用非常广泛。穷自动机理论提供了计算机软件工具的开发模式。这种模型可以很常见。它是计算机软件和硬件研究的重要基本理论。在软件方面，它为设计师提供了一种新的解决问题的想法和方法。它有几个内部模式或状态，用于存储过去输入的相关信息。对于当前输入，可以设置下一个步骤的状态和操作。对于带有穷自动机的状态转换图，可以应用于带有穷自动机的等效转换图和相应的算法，然后通过编程来实现。有穷自动机极小化问题的研究,在程序测试、模糊系统、概率自动机等方面具有重要意义.在等价的前提下,自动机的状态越少,越节省软件和硬件资源.朱征宇和朱庆生研究了有穷自动机的矩阵模型表示方法,并且给出了状态自动机的基本代数性质及相应的物理意义.文献从右不变等价关系的角度研究了非确定型有穷自动机的极小化.本文避免了文献中对左右位置的讨论,直接在有穷自动机的状态集上定义等价关系,利用等价关系对自动机进行极小化后得到自动机识别的语言不变;本文还构造了一台非确定型有穷自动机,它由两台确定型有穷自动机连接而成,由这两台确定型有穷自动机状态集上的等价关系,可以构造这台非确定有穷自动机状态集上的等价关系;对这两台确定型有穷自动机分别利用等价关系进行极小化,可以得到如下结论:这台非确定型有穷自动机极小化后的状态复杂度,不大于分别将原来的两台确定型有穷自动机极小化后再连接的自动机的状态复杂度.1确定型有穷自动机的构造及相关定义定义1.1一台确定型有穷自动机DFA是一个五元组M=(Q,Σ,δ,q0,F),其中,Q是一个有穷集合,称为状态集;Σ是一个有穷集合,称为字母表;δ:Q×Σ→Q是转移函数;q0∈Q是起始状态;F⊆Q是接受状态集.定义1.2设M=(Q,Σ,δ,q0,F)是一台确定型有穷自动机,ω=ω1ω2ω3…ωn是字母表Σ上的一个符号串.如果存在Q中的状态序列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),由δ定义函数δ*:Q*Σ*→Q如下:δ*=(q,ε)=q,δ*(q,ax)=δ*(δ(q,a),x),其中Σ*是指Σ上有穷符号串构成的集合.称串x将状态q带到状态δ*(q,x).对于x=a1a2a3…an,称状态序列q0,q1,q2,…,qn为串x将q0带到状态δ*(q0,x)的状态轨迹,其中δ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的任何自动机的状态数不低于|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将初始状态q0带到接受状态qn∈F的状态轨迹为:q0,q1,q2,…,qn,则在Mmin中,串x将初始状态[q0]带到接受状态[qn]的状态轨迹为:[q0],[q1],[q2],…,[qn].所以Mmin接受串x,则相应有L(M)⊆L(Mmin).反之,如果x∈L(Mmin),则在Mmin中,串x将初始状态[q0]带到接受状态[pn],且pn∈F,其状态轨迹为[q0],[p1],[p2],…,[pn].相应地,在M中,串x将初始状态q0带到接受状态pn的状态轨迹为:q0,p1,p2,…,pn,因此M接受串x,则L(Mmin)⊆L(M).从而L(M)=L(Mmin).定义1.6一台非确定型有穷自动机是一个五元组N=(Q,Σ,δ,q0,F),其中,Q是一个有穷集合,称为状态集;∑是一个有穷集合,称为字母表;δ:Q×Σε→Q是转移函数(这里Σε=Σ∪{ε});q0∈Q是起始状态;F⊆Q是接受状态集.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)是两台确定型有穷自动机,在状态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中的状态序列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)为一台非确定型有穷自动机,由状态集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的等价关系定义一个等价类,从而对非确定型有穷自动机进行状态极小化.定理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将初始状态q0带到接受状态qn∈F,则同样对应这个分支[q0],[q1],[q2],…,[qn],串x将初始状态[q0]带到接受状态[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表明非确定有穷自动机最小化后识别的语言不会改变.证明与前面相似(但要修改),只需取非确定有穷自动机能够出现接受状态的分支来分析即可.推论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状态极小化,满足R1的等价关系同样满足R=R1∪R2∪R1∞FR2∪R2∞FR1,并且R在Q1∪Q2上也可以按照等价关系进行状态合并.满足R2的等价关