王 敏，李永明

陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安 710119

1 引言

加權(quán)自動(dòng)機(jī)[1-6]是對(duì)經(jīng)典自動(dòng)機(jī)[7-8]的推廣，是轉(zhuǎn)移上附加權(quán)重的自動(dòng)機(jī)。這些權(quán)重作成的代數(shù)結(jié)構(gòu)通常是半環(huán)，Droste教授等在文獻(xiàn)[3]中已經(jīng)很好地研究了取值于半環(huán)的加權(quán)有窮自動(dòng)機(jī)的理論及其實(shí)際應(yīng)用。2011年Droste教授在文獻(xiàn)[4]中首次提出賦值幺半群的概念，將半環(huán)推廣到更一般的賦值幺半群上，并在文獻(xiàn)[5]中對(duì)取值于賦值幺半群的加權(quán)自動(dòng)機(jī)和加權(quán)單體二階邏輯進(jìn)行詳細(xì)的闡述。對(duì)一個(gè)輸入字符串，不帶輸出的有窮自動(dòng)機(jī)只判定此串是或者不是句子，這在許多時(shí)候是不夠的，原因是有時(shí)不僅希望系統(tǒng)能得出一個(gè)輸入串是否為要求串的結(jié)論，更希望系統(tǒng)在處理此串的過(guò)程中給出系統(tǒng)的輸出結(jié)果。Moore機(jī)和Mealy機(jī)就是兩種不同的帶有輸出的有窮自動(dòng)機(jī)[7]。并且由于帶輸出的加權(quán)有窮自動(dòng)機(jī)是自動(dòng)機(jī)理論的一個(gè)重要研究方向，在自然語(yǔ)言的處理方面[9-11]有著很重要的意義。文獻(xiàn)[12]和文獻(xiàn)[13]分別在格序幺半群和分配格意義下，證明了格值序列機(jī)與格值Moore機(jī)是等價(jià)的，格值序列機(jī)與格值Mealy機(jī)是不等價(jià)的（包括格序幺半群取{0,1}時(shí)的情況）。從而得到了格值Mealy機(jī)與格值Moore機(jī)是不等價(jià)的。但格值序列機(jī)與格值Moore機(jī)的等價(jià)性成立是依賴于分配律的。文獻(xiàn)[14]和文獻(xiàn)[15]在強(qiáng)雙半群-偽半環(huán)意義下研究偽加權(quán)序列機(jī)、偽加權(quán)Mealy機(jī)以及偽加權(quán)Moore機(jī)的關(guān)系，得到了類似的結(jié)論，且結(jié)論成立不依賴于分配律，但偽半環(huán)和格序幺半群都滿足結(jié)合律。

本文在賦值幺半群的基礎(chǔ)上引入了新的概念—強(qiáng)賦值幺半群，并研究了取值于新的代數(shù)結(jié)構(gòu)的強(qiáng)賦值加權(quán)序列機(jī)、強(qiáng)賦值加權(quán)Mealy機(jī)以及強(qiáng)賦值加權(quán)Moore機(jī)的關(guān)系，證明了強(qiáng)賦值加權(quán)序列機(jī)與強(qiáng)賦值加權(quán)Moore機(jī)是等價(jià)的，強(qiáng)賦值加權(quán)序列機(jī)與強(qiáng)賦值加權(quán)Mealy機(jī)是不等價(jià)的，從而得到了強(qiáng)賦值加權(quán)Mealy機(jī)與強(qiáng)賦值加權(quán)Moore機(jī)是不等價(jià)的，且上述結(jié)論成立既不依賴于分配律，強(qiáng)賦值幺半群也不需要滿足結(jié)合律。

2 預(yù)備知識(shí)

為了便于本文閱讀，現(xiàn)將與本文相關(guān)的概念介紹如下。

定義1[7]Mealy機(jī)是一個(gè)六元組：

其中，Q表示狀態(tài)的非空有窮集合；Σ表示輸入字母表；Δ表示輸出字母表；δ表示狀態(tài)轉(zhuǎn)移函數(shù)，有時(shí)又叫作狀態(tài)轉(zhuǎn)換函數(shù)或者移動(dòng)函數(shù)，δ:Q×Σ→Q。?(q,a)∈Q×Σ，δ(q,a)=p表示M在狀態(tài)q讀入字符a，將狀態(tài)變成p，并將讀頭向右移動(dòng)一個(gè)帶方格而指向輸入字符串的下一個(gè)字符；λ表示輸出函數(shù)，λ:Q×Σ→Δ。?(q,a)∈Q×Σ，λ(q,a)=d表示M在狀態(tài)q讀入字符a時(shí)輸出d；q0表示M的開(kāi)始狀態(tài)，也可叫作初始狀態(tài)或者啟動(dòng)狀態(tài)，q0∈Q。

顯然，?a1a2…an∈Σ?,M的輸出串為：λ(q0,a1)λ(δ(q0,a1),a2)…λ(δ(…δ(δ(q0,a1),a2)…),an), 設(shè)δ(q0,a1)=q1,δ(q1,a2)=q2,…,δ(qn-1,an)=qn,則M的輸出可以表示成λ(q0,a1)λ(q1,a2)…λ(qn-1,an),這是一個(gè)長(zhǎng)度為n的串。

定義2[7]Moore機(jī)是一個(gè)六元組：

其中，Q,Σ,Δ,δ,q0的意義同Mealy機(jī)。λ表示輸出函數(shù)，λ:Q→Δ。?q∈Q,λ(q)=a表示M在狀態(tài)q時(shí)輸出a。

顯然，?a1a2…an∈Σ?,M的輸出串為：λ(q0)λ(δ(q0,a1))…λ(δ((…δ(δ(q0,a1),a2)…),an)),設(shè)δ(q0,a1)=q1,δ(q1,a2)=q2,…,δ(qn-1,an)=qn,則M的輸出可以表示成λ(q0)λ(q1)λ(q2)…λ(qn),這是一個(gè)長(zhǎng)度為n+1的串。

定義3[4]設(shè)D是一個(gè)非空集合，(D,+,0)是一個(gè)可交換的幺半群，定義D上的賦值函數(shù)val:D+→D,若賦值函數(shù)滿足：

（1）?d∈D,val(d)=d;

（2）若存在i∈{1,2,…,n},使得di=0,則val(d1,d2,…,dn)=0 。

則稱D為賦值幺半群，記為(D,+,val,0)。

文中出現(xiàn)的∨與max表示相同意義，N表示自然數(shù)集，R表示實(shí)數(shù)集，并且用ε表示空字符串。

3 強(qiáng)賦值幺半群

定義4設(shè)D是一個(gè)非空集合，(D,+,val,0)是一個(gè)賦值幺半群，若賦值函數(shù)val:D+→D滿足，對(duì)任意自然數(shù)k：

（1）val作用于2k個(gè)元時(shí)，

（2）val作用于2k+1個(gè)元時(shí)，

（3）存在元素e∈D，使得val(d,e)=d,?d∈D。

則稱D為強(qiáng)賦值幺半群，記為(D,+,val,0,e)。

例1以下代數(shù)結(jié)構(gòu)為強(qiáng)賦值幺半群，并且賦值函數(shù)val滿足結(jié)合律。

（1）D=(?,+,×,0,1),D=(R,+,×,0,1)。

（2）D=(R+?{∞},+,∧,0,∞)，其中R+={a∈R|a≥ 0}。

注1強(qiáng)賦值幺半群是偽半環(huán)的推廣，同時(shí)也是格序幺半群的推廣。進(jìn)而，本文的結(jié)果可以看作文獻(xiàn)[12]和文獻(xiàn)[14]的進(jìn)一步推廣。

通過(guò)下面的例子來(lái)說(shuō)明強(qiáng)賦值幺半群比偽半環(huán)與格序幺半群條件弱。

例2設(shè)D=([0,1],max,val,0,1)，賦值函數(shù)val定義如下：?x1,x2,…,xi∈[0,1],i∈N ：

可以驗(yàn)證D=([0,1],max,val,0,1)是強(qiáng)賦值幺半群，但賦值函數(shù)val不滿足結(jié)合律。

4 強(qiáng)賦值加權(quán)Mealy機(jī)與強(qiáng)賦值加權(quán)Moore機(jī)及其響應(yīng)函數(shù)

定義5一個(gè)強(qiáng)賦值加權(quán)序列機(jī)是一個(gè)五元組M=(X,U,Y,f,I)，其中，X為非空有限狀態(tài)集合；U為有限輸入字符集；Y為有限輸出字符集；I：X→D為X上的D-值子集，表示D-值初始狀態(tài)；f:X×U×X×Y→D是D-值輸入-轉(zhuǎn)移-輸出函數(shù)，且f滿足條件：

f(x,u,x′,y)表示在狀態(tài)x下，輸入u，到達(dá)狀態(tài)x′并輸出y的權(quán)重。

下面定義M的響應(yīng)函數(shù)（也稱為輸入輸出函數(shù)）為φM:U*×Y*→D,?θ∈U*,w∈Y*,若|θ|=|w|時(shí)，設(shè)θ=u1u2…uk,w=y1y2…yk,

特別地，若θ=w=ε時(shí)，則若時(shí)，則φM(θ,w)=0 。

定義6一個(gè)強(qiáng)賦值加權(quán)Mealy機(jī)是一個(gè)六元組M=(X,U,Y,δ,h,I)，其中X、U、Y、I的定義同定義5；δ:X×U×X→D是D-值狀態(tài)轉(zhuǎn)移函數(shù)；h:X×U×Y→D是D-值轉(zhuǎn)移輸出函數(shù)，且滿足條件：

定義M的響應(yīng)函數(shù)為φM:U*×Y*→D，?θ∈U*，w∈Y*，θ=u1u2…uk,w=y1y2…yk，

定義7一個(gè)強(qiáng)賦值加權(quán)Moore機(jī)是一個(gè)六元組M=(X,U,Y,δ,h,I)，其中X、U、Y、I的定義同定義5；δ:X×U×X→D是D-值 狀 態(tài) 轉(zhuǎn) 移 函 數(shù) ；h:X×Y→D是D-值狀態(tài)輸出函數(shù)，且滿足如下條件：

定義M的響應(yīng)函數(shù)為φM:U*×Y*→D,?θ∈U*,w∈Y*,

其中，當(dāng) |w|=|θ|+1 時(shí)，設(shè)θ=u1u2…uk,w=y0y1…yk,則

特別地，若θ=ε,w=y0時(shí)，φM(θ,w)=φM(ε,y0)=

接下來(lái)研究強(qiáng)賦值加權(quán)序列機(jī)與強(qiáng)賦值加權(quán)Mealy機(jī)的關(guān)系。

若強(qiáng)賦值加權(quán)序列機(jī)M1與強(qiáng)賦值加權(quán)Mealy機(jī)M2的響應(yīng)函數(shù)相等，即φM1=φM2,則稱二者等價(jià)，也即?θ∈U*,w∈Y*,φM1(θ,w)=φM2(θ,w)。

定理1對(duì)任意的強(qiáng)賦值加權(quán)Mealy機(jī)M1，總存在與之等價(jià)的強(qiáng)賦值加權(quán)序列機(jī)M2。

證明任給一個(gè)強(qiáng)賦值加權(quán)Mealy機(jī)M1=(X,U,Y,δ,h,I)，構(gòu)造M2=(X,U,Y,f,I)如下：

即?x∈X,u∈U,上述定義的f滿足強(qiáng)賦值加權(quán)序列機(jī)中的條件。

因此，M2=(X,U,Y,f,I)是強(qiáng)賦值加權(quán)序列機(jī)。

?(θ,w)∈U*×Y*，當(dāng) |θ|=|w|時(shí)，設(shè)θ=u1u2…uk,w=y1y2…yk,

本研究考察了不同檢測(cè)波長(zhǎng)、不同柱溫、不同流速以及不同流動(dòng)相的樣品色譜圖，根據(jù)譜圖分離情況確定色譜條件，具體條件見(jiàn)“2.1”項(xiàng)下。

當(dāng) |θ|≠ |w|時(shí)，φM2(θ,w)=φM1(θ,w)=0 。

因此，?(θ,w)∈U*×Y*，都有φM2(θ,w)=φM1(θ,w)。□

注2反之，任意的強(qiáng)賦值加權(quán)序列機(jī)，未必存在與之等價(jià)的強(qiáng)賦值加權(quán)Mealy機(jī)。特別地，當(dāng)D={0,1}時(shí)，任給一個(gè)強(qiáng)賦值序列機(jī)，也未必存在與之等價(jià)的強(qiáng)賦值加權(quán)Mealy機(jī)，文獻(xiàn)[12]中引理2.1及例2.2對(duì)此進(jìn)行了詳細(xì)的證明。

推論1強(qiáng)賦值加權(quán)Mealy機(jī)與強(qiáng)賦值加權(quán)序列機(jī)是不等價(jià)的。

5 強(qiáng)賦值加權(quán)Mealy機(jī)與強(qiáng)賦值加權(quán)Moore機(jī)的關(guān)系

下面研究強(qiáng)賦值加權(quán)序列機(jī)與強(qiáng)賦值加權(quán)Moore機(jī)的關(guān)系。

首先定義機(jī)器等價(jià)的概念?？紤]強(qiáng)賦值加權(quán)序列機(jī)M1與強(qiáng)賦值加權(quán)Moore機(jī)M2，假設(shè)其具有相同的輸入集合U和輸出集合Y，且響應(yīng)函數(shù)滿足如下的關(guān)系式：則稱強(qiáng)賦值加權(quán)序列機(jī)M1與強(qiáng)賦值加權(quán)Moore機(jī)M2等價(jià)。即可通過(guò)驗(yàn)證是否滿足上述定義中的關(guān)系式來(lái)判斷強(qiáng)賦值加權(quán)序列機(jī)與強(qiáng)賦值加權(quán)Moore機(jī)是否等價(jià)。

定理2對(duì)任意的強(qiáng)賦值加權(quán)序列機(jī)M1，總存在與之等價(jià)的強(qiáng)賦值加權(quán)Moore機(jī)M2。

證明任給一個(gè)強(qiáng)賦值加權(quán)序列機(jī)M1=(X,U,Y,f,I),構(gòu)造M2=(X′,U,Y,δ,h,I′)如下：

因此，M2=(X′,U,Y,δ,h,I′)是強(qiáng)賦值加權(quán)Moore機(jī)。

這時(shí)，M2的響應(yīng)函數(shù)計(jì)算如下：

設(shè)X′=X×Y={(x0,y′0),(x1,y′1),…,(xk,yk′)}={x0′,x1′,…,xk′}，其中：x0′=(x0,y0′),x1′=(x1,y1′),…,xk′=(xk,yk′)。

下面的例子說(shuō)明了定理2中轉(zhuǎn)換函數(shù)的構(gòu)造。

例3設(shè)D=([0,1],max,val,0,1)是例2中定義的強(qiáng)賦值幺半群，X={x1,x2},U=Y={0,1}，f由如下矩陣描述：

這時(shí)M與M′等價(jià)。

以θ=01,w=10為例，可得：

因此，φ′(01,110)∨φ′(01,010)=φ(01,10)。

定理3對(duì)任意的強(qiáng)賦值加權(quán)Moore機(jī)M1，總存在與之等價(jià)的強(qiáng)賦值加權(quán)序列機(jī)M2。

證明任給一個(gè)強(qiáng)賦值加權(quán)Moore機(jī)M1=(X,U,Y,δ,h,I),構(gòu)造M2=(X′,U,Y,f,I′)如下：

即?(x,y)∈X′,u∈U，上述定義的f滿足強(qiáng)賦值加權(quán)序列機(jī)中的條件。

因此，M2=(X′,U,Y,f,I′)是強(qiáng)賦值加權(quán)序列機(jī)。

這時(shí)，M2的響應(yīng)函數(shù)計(jì)算如下：

設(shè)X′=X×Y={(x0,y0′),(x1,y1′),…,(xk,yk′)}={x0′,x1′,…,xk′}，其中x0′=(x0,y0′),x1′=(x1,y1′),…,xk′=(xk,yk′)。

下面的例子說(shuō)明了定理3中轉(zhuǎn)換函數(shù)的構(gòu)造。

例4設(shè)D=([0,1],max,val,0,1)是例2中定義的強(qiáng)賦值幺半群，X={x1,x2},U=Y={0,1},δ與h由如下矩陣描述：

這時(shí)M與M′等價(jià)。

以θ=01,w=10為例，可得：

定理4強(qiáng)賦值加權(quán)序列機(jī)和強(qiáng)賦值加權(quán)Moore機(jī)是等價(jià)的。

由定理4和推論1可得推論2。

推論2強(qiáng)賦值加權(quán)Mealy機(jī)和強(qiáng)賦值加權(quán)Moore機(jī)是不等價(jià)的。

6 總結(jié)

本文在權(quán)重取值于強(qiáng)賦值幺半群下定義了強(qiáng)賦值加權(quán)序列機(jī)、強(qiáng)賦值加權(quán)Mealy機(jī)和強(qiáng)賦值加權(quán)Moore機(jī)，得到了強(qiáng)賦值加權(quán)序列機(jī)與強(qiáng)賦值加權(quán)Mealy機(jī)是不等價(jià)的，證明了強(qiáng)賦值加權(quán)序列機(jī)與強(qiáng)賦值加權(quán)Moore機(jī)是等價(jià)的，并以強(qiáng)賦值加權(quán)序列機(jī)為中介，得到了強(qiáng)賦值加權(quán)Mealy機(jī)和強(qiáng)賦值加權(quán)Moore機(jī)是不等價(jià)的。進(jìn)一步將考慮權(quán)重取值于一般的賦值幺半群，以上結(jié)論是否也成立。