基于有限格序幺半群的自动机理论的状态最小化

摘要:定义了一种新的矩阵运算并由此给出了格值有限Mealy型自动机的定义。将转移矩阵M和输出矩阵O分别扩展到M*和O*。给出了格值有限Mealy型自动机的状态等价和自动机等价的定义。定义了状态最小化自动机并且得出了结论:任意一个格值有限Mealy型自动机都存在一个与之等价的状态最小化自动机。

关键词:格序幺半群 模糊有限自动机 最小化

1、L-模糊矩阵

设L是一个格,∨和∧分别代表取上确界和下确界运算。0和1代表L上的最小元和最大元。L上有一个二元运算·,使(L,·,e)成为有单位元eL的幺半群。我们称L是一个有序幺半群,如果它满足下面的条件:

我们称L是一个格序幺半群,如果L是一个有序幺半群并且满足下面的分配律:

设是一个矩阵,我们称A是一个L-模糊矩阵,如果。

定义1.1[1].设,分别是和L-模糊矩阵。定义两个矩阵A和B的乘积为矩阵,其中,记为AB。

定义1.2.设,分别是和L-模糊矩阵。定义两个矩阵A和B的运算为矩阵,其中,记为AB。

2、格值有限Mealy型自动机

定义2.1.一个格值有限Mealy型自动机（简称为LFMA）是一个五元组A=(Q,X,Y,M,O),其中

:是一个有限状态集,:是一个有限输入字符集,:是一个有限输出字符集;

是L-模糊转移矩阵。我们将M作为Q,X和Q之间的一个定义为的模糊关系;

是L-模糊输出矩阵。实际上,O可看成Q,X和Y之间的一个定义为的模糊关系。

我们假设本文中所讨论的任何一个LFMA都满足下面的两个条件:

定义2.2.设A=(Q,X,Y,M,O)是一个LFMA,|Q|=n。我们定义L-模糊转移矩阵M*如下:

(1)M*(Λ)=U,其中U=(m(Λ))是单位矩阵,即如果i=j,则m(Λ)=e,否则m(Λ)=0;

(2)M*(ux)=M*(u)·M(x),其中u∈X*,x∈X,M*(ux)是一个n×n方阵。

定义2.3.设A=(Q,X,Y,M,O)是一个LFMA,|Q|=n。我们定义n×1L-模糊输出矩阵O*(u,v)如下:

其中(e是L中的单位元,e>0,T代表矩阵的转置),o是一个零矩阵;

(2)O*(ux,vy)=(O*(u,v))'(M*(u)O(x,y)),其中(u,v)∈X*×Y*,(x,y)∈X×Y.

定义2.4.设A=(Q,X,Y,M,O)是一个LFMA,|Q|=n。我们定义L-模糊输出矩阵O*如下:

(1)O*(Λ)=E;

(2)O*(ux)=(O*(u))'(M*(u)O(x)),其中u∈X*,x∈X.

定理2.1设A=(Q,X,Y,M,O)是一个LFMA.|Q|=n并且|X|=m。则{M*(u)|u∈X*}中至多存在(k=|L|）个不同的L-模糊矩阵。

证明:设,。设是在模糊矩阵组中出现的所有不同元素的集合。所以,{M*(u)|u∈X*}中不同的模糊矩阵至多为个。

定理2.2.设A=(Q,X,Y,M,O)是一个LFMA.|Q|=n并且|X|=m。则至多步就确定了{O*(u)|u∈X*}中的所有矩阵,其中k=|L|并且是某一个输入字符串的长度。

证明:设L是一个有限格并且k=|L|。由定理2.1知,如果输入字符串u的长度大于,M*(u)将和前步中算出的某一个矩阵相同。因此,至多步就确定了{M*(u)|u∈X*}。当|u|>时,易知O*(ux)将和步中某一个矩阵相同。因此,至多步就确定了{O*(u)|u∈X*}。

3、LFMA的状态最小化

定义3.1.设A=(Q,X,Y,M,O)和A'=(Q',X,Y,M',O')是两个LFMAs。设q∈Q,q'∈Q'。那么:

(1)如果x∈X*,在O*(x)中对应于状态q的行与O'*(x)中对应于状态q'的行相同,我们称q和q'等价(qq');

(2)如果存在某个x∈X*,使得在O*(x)中对应于状态q的行与O'*(x)中对应于状态q'的行不同,我们称q和q'是可区分的;

(3)如果q∈Q,存在q'∈Q',使得q'q并且q'∈Q',存在q∈Q,使得qq',我们称A和A'等价(AA');

定理3.1.设A=(Q,X,Y,M,O)是一个LFMA,|Q|=n。如果u∈X*,在O*(u)中第i行和第j行相同,其中i≠j,则存在一个只含n-1个状态的LFMAA',使得AA'。

证明:设,并且.由定义3.1知和等价.我们构造一个自动机A'=(Q',X,Y,M',O'),令Q'=Q\,M'={M'(x)|M'(x)=(),x∈X,∈L}并且O'={O'(x)|O'(x)=(),x∈X,∈L},其中

易知,|Q'|=n-1。并且AA'。

定义3.2.设A=(Q,X,Y,M,O)是一个LFMA。如果Q中任意两个状态都是可区分的,我们称A是一个状态最小化自动机。

推论1.设A=(Q,X,Y,M,O)是一个LFMA。则存在一个状态最小化的LFMAA'使得AA'。

定理3.2.设A=(Q,X,Y,M,O)是一个LFMA,|Q|=n。设L是一个有限格并且k=|L|。则至多步就可区分Q中的所有状态。

证明:由定理3.2知{O*(u)|u∈X*}中不同矩阵的数目是可数的。而且O*(u)中只有n行。因此,在{O*(u)|u∈X*}中不同列的数目至多个。

4、结语

文献[1]中研究的是完备格值有限自动机的最小化。我们扩大了研究的范围,通过引入一个新的矩阵运算就不再要求完备了。然后,定义了格值有限Mealy型自动机。证明了任意一个格值有限Mealy型自动机A都存在一个与之等价的状态最小化格值有限Mealy型自动机A'。

参考文献

[1]H.X. Lei, Y.M. Li, Minimization of states in automata theory based on finite lattice-ordered monoids, Information Sciences 177 (2007) 1413-1421.