幾類帶空轉(zhuǎn)移的n元偽加權(quán)自動(dòng)機(jī)的關(guān)系*

趙路瑤,王海輝,李 平

(陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,陜西 西安 710119)

1 引言

自動(dòng)機(jī)理論是計(jì)算機(jī)科學(xué)理論的基礎(chǔ)。1961年,Schützenberger[1]提出了加權(quán)有窮自動(dòng)機(jī)的概念。加權(quán)有窮自動(dòng)機(jī)是經(jīng)典的非確定型有窮自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移函數(shù)、初始狀態(tài)和接受狀態(tài)都附加上權(quán)重而形成的一種有窮自動(dòng)機(jī),這些權(quán)值形成的代數(shù)結(jié)構(gòu)一般為半環(huán),得到了廣泛研究[2 - 6]。1967年,Wee[7]提出了模糊有窮自動(dòng)機(jī)的概念,開(kāi)啟了模糊自動(dòng)機(jī)理論研究的歷程。此后,又有學(xué)者相繼提出了取值于完備正交模格的自動(dòng)機(jī)[8，9]、取值于完備剩余格的有窮自動(dòng)機(jī)[10,11]和取值于格序半群的模糊有窮自動(dòng)機(jī)[12]。作為以上各種模型的擴(kuò)展,2010年,Droste等[13]提出了取值于強(qiáng)雙半群(偽半環(huán))的自動(dòng)機(jī)理論,且進(jìn)行了深入研究[14,15]。偽半環(huán)是半環(huán)去掉分配律形成的代數(shù)結(jié)構(gòu),因此偽加權(quán)有窮自動(dòng)機(jī)(取值于偽半環(huán)的加權(quán)有窮自動(dòng)機(jī))比取值于半環(huán)的加權(quán)有窮自動(dòng)機(jī)更具一般性。

近一個(gè)世紀(jì)以來(lái),自動(dòng)機(jī)理論取得了長(zhǎng)足發(fā)展,其廣泛地應(yīng)用于人工智能、文本處理、數(shù)字圖像壓縮、模型檢測(cè)和模式識(shí)別等領(lǐng)域[16 - 21]。近來(lái),我們發(fā)現(xiàn)自動(dòng)機(jī)也可以應(yīng)用于不確定性數(shù)據(jù)處理中,以解決不確定性數(shù)據(jù)世系分析中結(jié)果元組的概率計(jì)算問(wèn)題[22,23]。然而解決此問(wèn)題需要一個(gè)可以帶有有限多個(gè)輸入的自動(dòng)機(jī),以往的自動(dòng)機(jī)概念都只帶有一個(gè)輸入或帶有輸入與輸出2個(gè)信息,因此本文提出n元偽加權(quán)有窮自動(dòng)機(jī)(帶有n個(gè)有限輸入字符集的偽加權(quán)有窮自動(dòng)機(jī))、分明型n元偽加權(quán)有窮自動(dòng)機(jī)(初始狀態(tài)與狀態(tài)轉(zhuǎn)移函數(shù)均是分明的n元偽加權(quán)有窮自動(dòng)機(jī))與確定型n元偽加權(quán)有窮自動(dòng)機(jī)(初始狀態(tài)與狀態(tài)轉(zhuǎn)移函數(shù)均是確定的n元偽加權(quán)有窮自動(dòng)機(jī))的概念。

在經(jīng)典的有窮自動(dòng)機(jī)理論中,帶空轉(zhuǎn)移的非確定型有窮自動(dòng)機(jī)、非確定型有窮自動(dòng)機(jī)與確定型有窮自動(dòng)機(jī)是等價(jià)的[24,25]。在基于格序半群的模糊自動(dòng)機(jī)理論中,除初始狀態(tài)與接受狀態(tài)均是分明的非確定型格值自動(dòng)機(jī)以外,其他類型的非確定型格值自動(dòng)機(jī)與帶空轉(zhuǎn)移的非確定型格值自動(dòng)機(jī)均是等價(jià)的[26],而非確定型格值自動(dòng)機(jī)與確定型格值自動(dòng)機(jī)并不是等價(jià)的[12]。由格序半群和半環(huán)的代數(shù)性質(zhì)可知,這些結(jié)論推廣到取值于半環(huán)上的加權(quán)自動(dòng)機(jī)依然成立。此外,在已知確定型加權(quán)自動(dòng)機(jī)與非確定型加權(quán)自動(dòng)機(jī)并不等價(jià)的前提下,文獻(xiàn)[27]提出了狀態(tài)轉(zhuǎn)移函數(shù)是分明的加權(quán)自動(dòng)機(jī)、帶空轉(zhuǎn)移的狀態(tài)轉(zhuǎn)移函數(shù)是分明的加權(quán)自動(dòng)機(jī)的概念,并證明了以上二者是等價(jià)的,且它們與確定型加權(quán)自動(dòng)機(jī)也是等價(jià)的。

然而由于偽半環(huán)未必滿足分配律,以上結(jié)論并不能直接推廣到偽加權(quán)有窮自動(dòng)機(jī)中,并且到目前為止還沒(méi)有文獻(xiàn)直接討論偽加權(quán)有窮自動(dòng)機(jī)與帶空轉(zhuǎn)移的偽加權(quán)有窮自動(dòng)機(jī)之間的等價(jià)性關(guān)系。因此,本文以n元偽加權(quán)有窮自動(dòng)機(jī)為基礎(chǔ),根據(jù)狀態(tài)轉(zhuǎn)移函數(shù)在每個(gè)字符集上是否帶空轉(zhuǎn)移,將n元偽加權(quán)有窮自動(dòng)機(jī)與分明型n元偽加權(quán)有窮自動(dòng)機(jī)分為4類:帶r-型空轉(zhuǎn)移的n元偽加權(quán)有窮自動(dòng)機(jī)、帶空轉(zhuǎn)移的n元偽加權(quán)有窮自動(dòng)機(jī)、帶r-型空轉(zhuǎn)移的分明型n元偽加權(quán)有窮自動(dòng)機(jī)和帶空轉(zhuǎn)移的分明型n元偽加權(quán)有窮自動(dòng)機(jī),并研究了上述幾種類型的自動(dòng)機(jī)之間的關(guān)系,討論了狀態(tài)轉(zhuǎn)移函數(shù)在每個(gè)字符集上是否帶空轉(zhuǎn)移對(duì)其接受語(yǔ)言的影響,進(jìn)一步完善了偽加權(quán)有窮自動(dòng)機(jī)理論。

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

首先回顧一下偽半環(huán)的概念及其相關(guān)結(jié)論。

注1在文獻(xiàn)[15]中,偽半環(huán)又叫做強(qiáng)雙半群。

例1[15]易驗(yàn)證下面的代數(shù)結(jié)構(gòu)都是偽半環(huán):

(1)(N,+,×,0,1)、(R,+,×,0,1)與([0,1],max,×,0,1)都是偽半環(huán)。其中,(N,+,×,0,1),(R,+,×,0,1)是交換且分配的,([0,1],max,×,0,1)是交換且加冪等的。

(2)格序半群是偽半環(huán)。同時(shí),它們也是加冪等且分配的。

(3)格、完備格、完備正交模格和完備分配格都是偽半環(huán)。其中,格、完備格、完備正交模格、完備分配格均是交換、加冪等且乘冪等的。此外,完備分配格還是分配的。

3 n元偽加權(quán)有窮自動(dòng)機(jī)及其識(shí)別的語(yǔ)言

本節(jié)給出n元偽加權(quán)有窮自動(dòng)機(jī)、分明型n元偽加權(quán)有窮自動(dòng)機(jī)和確定型n元偽加權(quán)有窮自動(dòng)機(jī)的概念,并分別給出它們所識(shí)別的語(yǔ)言的定義。下面先回顧一下偽加權(quán)有窮自動(dòng)機(jī)的定義。

定義2[15]偽加權(quán)有窮自動(dòng)機(jī)PA(Pseudo weighted Automata)是一個(gè)五元組A=(Q,Σ,δ,I,F),其中,

(1)Q為有限狀態(tài)集,Σ為有限輸入字符集;

令Σ*表示Σ關(guān)于連接運(yùn)算生成的自由幺半群,ε是其單位元。對(duì)任意θ∈Σ*,|θ|表示θ的長(zhǎng)度,即字符的個(gè)數(shù),特別地,|ε|=0。

定義4n元偽加權(quán)有窮自動(dòng)機(jī)(n-PA)是一個(gè)n+4元組M=(Q,Σ1,…,Σn,δ,I,F),其中,

(1)Q,I,F的意義同定義1;

(2)Σi為有限字符集,i=1,…,n;

若存在i,j,使得|θi|≠|(zhì)θj|,則fM(θ1,…,θn) =0;

顯然,當(dāng)n=1時(shí),n元偽加權(quán)有窮自動(dòng)機(jī)即為偽加權(quán)有窮自動(dòng)機(jī)。

定義5設(shè)M=(Q,Σ1,…,Σn,δ,I,F)是一個(gè)n-PA,若I={q0},δ:Q×Σ1×…×Σn→2Q,則稱M為分明型n元偽加權(quán)有窮自動(dòng)機(jī)n-CPA(n-ary Crisp Pseudo weighted Automata)。

若|θ1|=…=|θn|=0,即θ1=…=θn=ε,則δ*(q,θ1,…,θn)={q};

否則,δ*(q,θ1,…,θn)無(wú)定義。

定義6設(shè)M=(Q,Σ1,…,Σn,δ,I,F)是一個(gè)n-PA,若I={q0},δ:Q×Σ1×…×Σn→Q,則稱M是一個(gè)確定型n元偽加權(quán)有窮自動(dòng)機(jī)n-DPA(n-ary Deterministic PA)。

若|θ1|=…=|θn|=0,即θ1=…=θn=ε,則δ*(q,θ1,…,θn)=q;

若|θ1|=…=|θn|>0,不妨設(shè)θ1=θ′1u1,…,θn=θ′nun,則δ*(q,θ1,…,θn) =δ(δ*(q,θ′1,…,θ′n),u1,…,un);

否則,δ*(q,θ1,…,θn)無(wú)定義。

fM(θ1,…,θn)=

為方便起見(jiàn),若I={q0},那么記M=(Q,Σ1,…,Σn,δ,q0,F)。

注3設(shè)Σ1,…,Σn是非空有限字符集,則由文獻(xiàn)[27]中的定理4.1與文獻(xiàn)[12]中的定理3.3可推出L(n-DPA,Σ1,…,Σn)=L(n-CPA,Σ1,…,Σn)L(n-PA,Σ1,…,Σn)。即n-DPAs與n-CPAs是等價(jià)的,但與n-PAs并不是等價(jià)的。稱2個(gè)自動(dòng)機(jī)是等價(jià)的是指它們所接受的語(yǔ)言類型是相同的。

4 帶r-型空轉(zhuǎn)移的n元偽加權(quán)有窮自動(dòng)機(jī)及其識(shí)別的語(yǔ)言

本節(jié)將根據(jù)狀態(tài)轉(zhuǎn)移函數(shù)在每個(gè)字符集上是否帶空轉(zhuǎn)移,將n元偽加權(quán)有窮自動(dòng)機(jī)進(jìn)一步分類,給出它們分別接受語(yǔ)言的定義并討論它們之間的關(guān)系。

定義7帶r-型空轉(zhuǎn)移的n元偽加權(quán)有窮自動(dòng)機(jī)(n-rEPA)是一個(gè)n+4元組：

其中,

(1)Q,I,F的意義同定義2;

為給出M接受語(yǔ)言的定義,給出以下符號(hào)和概念。

又令PM=EM∪{π|π=e1e2…em(m≥2),ei∈EM,i=1,…,m,且π滿足n(ei)=c(ei+1),i=1,…,m-1}。那么對(duì)任意π∈PM,稱π是M的一條路徑。例如,π1=(q1,ε,σ2,…,σn,q2)與π2=(q0,ε,σ2,…,σn,q1)(q1,σ1,…,σn-1,ε,q2)是M的2條路徑,而π3=(q0,ε,σ2,…,σn,q1)(q2,σ1,…,σn-1,ε,q3)并不是M的路徑。

當(dāng)θ1,…,θn不全為ε時(shí),

此外,注意到,對(duì)于一個(gè)n-PAN=(Q,Σ1,…,Σn,δ,I,F),其接受的語(yǔ)言具有等價(jià)形式:

當(dāng)θ1,…,θn不全為ε時(shí),

由此可見(jiàn),n-PA是一個(gè)特殊的n-rEPA。

定義8帶空轉(zhuǎn)移的n元偽加權(quán)有窮自動(dòng)機(jī)(n-EPA)是一個(gè)n+4元組:

其中,

(1)Q,I,F的意義同定義1;

定理1設(shè)Σ1,…,Σn是非空有限字符集,則L(n-PA,Σ1×…×Σn)L(n-rEPA,Σ1×…××…××…×Σn),其中,{i1,…,ir}是{1,…,n}的任意一個(gè)子序列。

δ1(q,u1,…,un,p)=

構(gòu)造過(guò)程如圖1所示。

Figure 1 n-rEPA M圖1 n-rEPA M

□

□

由定理1和定理2可得以下推論。

推論1設(shè)Σ1,…,Σn是非空有限字符集,則L(n-PA,Σ1×…×Σn)L(n-rEPA,其中,{i1,…,ir}是{1,…,n}的任意一個(gè)真子序列。

由以上定理與推論可知,n-PAs、n-rEPAs與n-EPAs三者均不是等價(jià)的。

下面介紹帶r-型空轉(zhuǎn)移的分明型n元偽加權(quán)有窮自動(dòng)機(jī)的定義。

類似于定義7,首先給出以下概念。

又令PM=EM∪{π|π=e1e2…em(m≥2),ei∈EM,i=1,…,m,且π滿足c(ei+1)∈δ(ei),i=1,…,m-1}。那么對(duì)任意π∈PM,稱π是M的一條路徑。例如,若δ(q1,σ1,…,σn)={q2},δ(q2,σ1,…,σn)={q3},則π1=(q1,σ1,…,σn)與π2=(q1,σ1,…,σn)(q2,σ1,…,σn)是M的2條路徑,而π3=(q2,σ1,…,σn)(q1,σ1,…,σn)并不是M的路徑。

對(duì)任意π=e1…em(m≥2)∈P(M),記o(π)=c(e1)為π的開(kāi)始狀態(tài),a(π)=δ(em)為π的終止?fàn)顟B(tài)。又假設(shè)e1=(q1,σ11,…,σn1),e2=(q2,σ12,…,σn2),…,em=(qm,σ1m,…,σnm),則定義str(π)=(σ11σ12…σ1m,…,σn1σn2…σnm)。

當(dāng)θ1,…,θn不全為ε時(shí),

當(dāng)θ1=…=θn=ε時(shí),fM(θ1,…,θn)=F(q0)。

定理3的證明類似于定理1的,此處不再具體給出。

證明由n-rECPA和n-ECPA的定義可知定理顯然成立。

□

由定理3與定理4可得如下推論：

由以上定理與推論可知,n-CPAs、n-rEPAs和n-EPAs三者是不等價(jià)的。然而,下面將證明存在一類特殊的n-EPAs,其與n-CPAs是等價(jià)的。

(i)q02=q01;

(iii)δ2:Q×Σ1×…×Σn→2Q,?q∈Q,σ1∈Σ1,…,σn∈Σn,δ2(q,σ1,…,σn)={p|p∈a(π),π∈PM1,o(π)=q,str(π)=(σ1,…,σn)}。

(1)若存在π2∈PM2,滿足str(π2)=(θ1,…,θn),則一定有|θ1|=…=|θn|,那么：

①當(dāng)|θ1|=…=|θn|>0時(shí),有:

fM2(θ1,…,θn)=

(1)

由(iii)可知,對(duì)任意的π∈PM2,且o(π)=q,str(π)=(θ1,…,θn),都存在一個(gè)π′∈PM1使得o(π′)=q,str(π′)=(θ1,…,θn),且a(π′)=a(π)。反之亦然。從而式(1)轉(zhuǎn)變?yōu)槭?2)所示：

(2)

又當(dāng)π′2,π1∈PM1,o(π1)=q,q∈a(π′2)時(shí),有π′2π1∈PM1,所以,式(2)轉(zhuǎn)變?yōu)槭?3)所示：

(3)

(2)否則,fM2(θ1,…,θn)=0=fM1(θ1,…,θn)。

□

以上定理說(shuō)明,即使n-ECPAs與n-CPAs并不是等價(jià)的,但卻有n-PECPAs與n-CPAs是等價(jià)的。

此外,由文獻(xiàn)[27]中的定理4.2可以推出,當(dāng)n=1時(shí),n-ECPAs與n-CPAs是等價(jià)的。由此也可以看出,狀態(tài)轉(zhuǎn)移函數(shù)在每個(gè)字符集上是否帶空轉(zhuǎn)移對(duì)n元偽加權(quán)有窮自動(dòng)機(jī)接受語(yǔ)言的影響不同于其對(duì)偽加權(quán)有窮自動(dòng)機(jī)的影響。

5 結(jié)束語(yǔ)

本文以不確定性數(shù)據(jù)世系分析中結(jié)果元組的概率計(jì)算為應(yīng)用背景,引入了n元偽加權(quán)有窮自動(dòng)機(jī)(n-PA)、帶r-型空轉(zhuǎn)移的n元偽加權(quán)有窮自動(dòng)機(jī)(n-rEPA)、帶空轉(zhuǎn)移的n元偽加權(quán)有窮自動(dòng)機(jī)(n-ECPA)、分明型n元偽加權(quán)有窮自動(dòng)機(jī)(n-CPA)、帶r-型空轉(zhuǎn)移的分明型n元偽加權(quán)有窮自動(dòng)機(jī)(n-rECPA)、帶空轉(zhuǎn)移的分明型n元偽加權(quán)有窮自動(dòng)機(jī)(n-ECPA)、確定型n元偽加權(quán)有窮自動(dòng)機(jī)(n-DPA)與一個(gè)特殊的帶空轉(zhuǎn)移的分明型n元偽加權(quán)有窮自動(dòng)機(jī)(n-PECPA)及其對(duì)應(yīng)語(yǔ)言的概念,探究了以上自動(dòng)機(jī)之間的等價(jià)性關(guān)系,并得到以下結(jié)論:

以上結(jié)論說(shuō)明,狀態(tài)轉(zhuǎn)移函數(shù)在每個(gè)字符集上是否帶空轉(zhuǎn)移對(duì)n元偽加權(quán)有窮自動(dòng)機(jī)接受的語(yǔ)言有著重要的影響,且不同于其對(duì)偽加權(quán)有窮自動(dòng)機(jī)的影響。本文完善了偽加權(quán)有窮自動(dòng)機(jī)理論,并為n元偽加權(quán)有窮自動(dòng)機(jī)在不確定性數(shù)據(jù)處理中的應(yīng)用奠定了理論基礎(chǔ)。下一步的工作將以本文研究為基礎(chǔ)探究n元偽加權(quán)有窮自動(dòng)機(jī)在不確定性數(shù)據(jù)處理方面的具體應(yīng)用。