張麗霞

(安慶師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,安徽 安慶 246013)

加權(quán)有窮自動(dòng)機(jī)的代數(shù)性質(zhì)*

張麗霞

(安慶師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,安徽 安慶 246013)

在加權(quán)有窮自動(dòng)機(jī)理論基礎(chǔ)上，利用強(qiáng)同態(tài)的概念，證明兩個(gè)加權(quán)有窮自動(dòng)機(jī)在計(jì)算能力上是等價(jià)的，并在加權(quán)有窮自動(dòng)機(jī)的狀態(tài)集上建立一種等價(jià)關(guān)系，得到加權(quán)有窮自動(dòng)機(jī)的商自動(dòng)機(jī)，證明加權(quán)有窮自動(dòng)機(jī)與其商自動(dòng)機(jī)在計(jì)算能力上也是等價(jià)的。并通過(guò)引入加權(quán)有窮自動(dòng)機(jī)的可交換性、分離性、(強(qiáng))連通性及層的概念，討論在(強(qiáng))同態(tài)的條件下，兩個(gè)加權(quán)有限狀態(tài)機(jī)之間的可交換性、分離性、(強(qiáng))連通性及層的關(guān)系。

形式冪級(jí)數(shù)；加權(quán)有窮自動(dòng)機(jī)；同態(tài)；強(qiáng)連通

1 引言

在計(jì)算機(jī)科學(xué)中，自動(dòng)機(jī)作為計(jì)算過(guò)程的動(dòng)態(tài)數(shù)學(xué)模型，用來(lái)研究計(jì)算機(jī)的體系結(jié)構(gòu)、邏輯操作、程序設(shè)計(jì)乃至計(jì)算復(fù)雜性理論[1～5]。1961年，Schützenberger M P[6]首先提出了加權(quán)自動(dòng)機(jī)的概念，并提出了半環(huán)上的形式冪級(jí)數(shù)的概念，證明了Kleene-Schützenberger 定理，即加權(quán)有窮自動(dòng)機(jī)所識(shí)別的形式冪級(jí)數(shù)和有理冪級(jí)數(shù)是一致的。隨后，又有很多學(xué)者在這一領(lǐng)域作出了進(jìn)一步有意義的工作[7～12]。目前，加權(quán)自動(dòng)機(jī)在模式識(shí)別、模型檢測(cè)、數(shù)字圖像壓縮算法等領(lǐng)域取得了廣泛的應(yīng)用[13～15]。由于 Successor 和Source 算子是自動(dòng)機(jī)理論中的重要工具之一，Kuroki N、Tiwari S P，Srivastava A K等[16～21]利用 Successor 和 Source算子研究了模糊有窮自動(dòng)機(jī)(強(qiáng))連通性、分離性、交換等性質(zhì)，并給出了模糊自動(dòng)機(jī)一些結(jié)構(gòu)刻畫(huà)。本文將在半環(huán)的結(jié)構(gòu)上，研究加權(quán)有窮自動(dòng)機(jī)的同態(tài)和強(qiáng)同態(tài)及其性質(zhì)，并在加權(quán)有窮自動(dòng)機(jī)的狀態(tài)集上建立一種等價(jià)關(guān)系，從而得到加權(quán)有窮自動(dòng)機(jī)的商自動(dòng)機(jī)。進(jìn)一步，利用(強(qiáng))同態(tài)的概念，討論了兩個(gè)加權(quán)有限狀態(tài)機(jī)之間的可交換性、分離性、(強(qiáng))連通性及層的關(guān)系。

2 基本概念與符號(hào)

首先，我們引入一些必要的概念與記號(hào)，詳細(xì)請(qǐng)參考文獻(xiàn)[11,12,17,20]。

集合S是帶有兩個(gè)二元運(yùn)算⊕、?和兩個(gè)特殊元素0、1的集合，并且滿(mǎn)足:

(1)(S,⊕,0)是交換幺半群;

(2)(S,?,1)是幺半群;

(3) 對(duì)任意a,b,c∈S，有a?(b⊕c)=a?b⊕a?c，(b⊕c)?a=b?a⊕c?a;

(4) 對(duì)任意a∈S，有0?a=a?0=0。

稱(chēng)(S,⊕,?,0,1)為半環(huán)。為了方便討論，本文簡(jiǎn)記S。如果對(duì)任意a,b∈S，都有ab=ba，則稱(chēng)半環(huán)S為交換半環(huán)。半環(huán)理論作為具有廣泛應(yīng)用背景的代數(shù)系統(tǒng)在計(jì)算機(jī)理論科學(xué)中具有特殊性及重要性。特別在經(jīng)典的形式語(yǔ)言理論中，最重要的半環(huán)是Boolean半環(huán)S={0,1}。

設(shè)S是一個(gè)半環(huán)，稱(chēng)Σ*到S的映射A為形式冪級(jí)數(shù)。對(duì)任意x∈Σ*，A在x處的值記為(A,x)，并記A為:

稱(chēng)A為變量在Σ中的形式冪級(jí)數(shù)，其中(A,x)為此形式冪級(jí)數(shù)的系數(shù)。所有形式冪級(jí)數(shù)組成的集合記為S?Σ*。

設(shè)A,B∈S?Σ*，若對(duì)任意x∈Σ*，有A(x)=B(x)，則稱(chēng)A等于B，記作A=B。

定義1[11]設(shè)S是半環(huán)，加權(quán)有窮自動(dòng)機(jī)(簡(jiǎn)記為WFA)(WeightedFiniteAutomata)是五元組W=(Q,Σ,δ,I,F)，其中，Q為有限狀態(tài)集合，Σ為有限輸入字符集，I:Q→S與F:Q→S分別代表權(quán)值初始狀態(tài)與權(quán)值接受狀態(tài)，而δ:Q×Σ×Q→S為權(quán)值轉(zhuǎn)移函數(shù)。

更進(jìn)一步，若對(duì)q∈Q,x∈∑，存在唯一的p∈Q使得δ(q,x,p)=1，而對(duì)其余的r∈Q，都有δ(q,x,r)=0，并且存在唯一的q′∈Q使得I(q′)=1，則得到通常的確定型加權(quán)有窮自動(dòng)機(jī)的概念。

轉(zhuǎn)移函數(shù)δ可以擴(kuò)張到Q×∑*×Q上，即δ*:Q×∑*×Q→S滿(mǎn)足如下條件:

(2) 對(duì)輸入序列x=x1x2…xk∈∑*,k≥1,則:

根據(jù)上述定義，易驗(yàn)證下列等式成立:

另外，對(duì)任意A∈S?Σ*，若存在一個(gè)WFAW使A恰為W接受的形式冪級(jí)數(shù)，則稱(chēng)A為Σ上的正則冪級(jí)數(shù)。

為了對(duì)不同的加權(quán)有窮自動(dòng)機(jī)進(jìn)行比較，下面引入加權(quán)有窮自動(dòng)機(jī)之間同態(tài)和強(qiáng)同態(tài)的概念。

定義3[11]設(shè)S是半環(huán)，W=(Q,Σ,δ,I,F)和W1=(Q1,Σ,δ1,I1,F1)是兩個(gè)WFA。設(shè)映射φ:Q→Q1，對(duì)任意q,q′∈Q，x∈Σ，若滿(mǎn)足下列條件：

I(q)≤I1(φ(q))，F(xiàn)(q)≤F1(φ(q))，δ(q,x,q′)≤δ1(φ(q),x,φ(q′))

則稱(chēng)φ為同態(tài)映射。

進(jìn)一步，若φ滿(mǎn)足:

F1(φ(q))=F(q)。

則稱(chēng)φ為強(qiáng)同態(tài)。若φ是強(qiáng)同態(tài)且同時(shí)是雙射，則稱(chēng)φ為同構(gòu)。

Successor算子是自動(dòng)機(jī)理論中的重要工具之一。在文獻(xiàn)[22]中，Zamir B首先提出了Successor算子的概念，并利用Successor算子研究了有窮自動(dòng)機(jī)一些特有的性質(zhì)。近年來(lái)，Tiwar S P等[19～21]在模糊集合的理論基礎(chǔ)上，利用Successor算子給出了模糊有窮自動(dòng)機(jī)一些結(jié)構(gòu)刻畫(huà)。本文將利用Successor算子來(lái)定義加權(quán)有窮自動(dòng)機(jī)的交換性、強(qiáng)連通性、分離性等概念，利用這些概念來(lái)討論加權(quán)有窮自動(dòng)機(jī)的一些特性。

定義5設(shè)S是半環(huán)，W=(Q,Σ,δ,I,F)是一個(gè)WFA，則:

(1) 對(duì)任意p,q∈Q，若q∈S(p)當(dāng)且僅當(dāng)p∈S(q)，則稱(chēng)W滿(mǎn)足交換性。

(2) 對(duì)任意p,q∈Q，都有p∈S(q)，則稱(chēng)W是強(qiáng)連通的。

(3)T?Q，δ是T×Σ×T的一個(gè)加權(quán)子集。若滿(mǎn)足以下兩個(gè)條件:

①δ|T×Σ×T=η;

②SQ(T)?T。

則稱(chēng)N=(T,Σ,η,I|T,F|T)是W的子加權(quán)有窮自動(dòng)機(jī)。若T≠Q(mào)且T≠?，則稱(chēng)N是W的真子加權(quán)有窮自動(dòng)機(jī)。

定義7設(shè)S是半環(huán)，W=(Q,Σ,δ,I,F)是一個(gè)WFA。如果W是沒(méi)有可分離的真子加權(quán)有窮自動(dòng)機(jī)，則稱(chēng)W是連通的。

3 主要結(jié)果

∑p′∈Q1{∑s∈Q{δ*(q,y,s)|φ(s) =p′} ?∑p∈Q1{δ*(s,u,r)|φ(r)=p}}=

∑p′∈Q1{∑r,s∈Q{δ*(q,y,s)|φ(s) =p′} ?{δ*(s,u,r)|φ(r)=p}}=

∑r∈Q{δ*(q,yu,r)|φ(r)=p}

充分性。因?yàn)棣帐菃紊?，故?duì)任意q,r∈Q，且x∈Σ*，有：

因此，φ是強(qiáng)同態(tài)。

□

證明對(duì)任意x∈Σ*，有:

□

證明對(duì)任意x∈Σ*，有：

□

定理3說(shuō)明了加權(quán)有窮自動(dòng)機(jī)與其商自動(dòng)機(jī)在計(jì)算能力上是等價(jià)的，從而實(shí)現(xiàn)了加權(quán)有窮自動(dòng)機(jī)的狀態(tài)極小化。

引理1[19]設(shè)S是半環(huán)，W=(Q,Σ,δ,I,F)是一個(gè)WFA，則W是強(qiáng)連通的充分條件是W沒(méi)有真子加權(quán)有窮自動(dòng)機(jī)。

定理5設(shè)S是半環(huán)，W=(Q,Σ,δ,I,F)是一個(gè)WFA，則：

(1) 若W是強(qiáng)連通的當(dāng)且僅當(dāng)W是連通的且滿(mǎn)足交換性;

(2) 若W是強(qiáng)連通的，則Q自身為W的一個(gè)層。

(2) 顯然，若W=(Q,Σ,δ,I,F)是強(qiáng)連通的當(dāng)且僅當(dāng)S(q)=Q，q∈Q，根據(jù)可分離的定義，Q為W的一個(gè)層。

□

定理6設(shè)S是半環(huán)，W=(Q,Σ,δ,I,F)是一個(gè)WFA，則W必有一個(gè)強(qiáng)連通的子加權(quán)有窮自動(dòng)機(jī)。

□

(2) 若p∈Q，Lp為W的一個(gè)層，則φ(Lp1)為W1的一個(gè)層。

證明(1) 根據(jù)加權(quán)有窮自動(dòng)機(jī)同態(tài)的定義可得。

□

根據(jù)引理2，我們有如下結(jié)論。

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

本文在半環(huán)的結(jié)構(gòu)上，利用強(qiáng)同態(tài)的概念，證明了兩個(gè)加權(quán)有窮自動(dòng)機(jī)在計(jì)算能力上是等價(jià)的，并在加權(quán)有窮自動(dòng)機(jī)的狀態(tài)集上建立了一種等價(jià)關(guān)系，得到了加權(quán)有窮自動(dòng)機(jī)的商自動(dòng)機(jī)，證明了加權(quán)有窮自動(dòng)機(jī)與其商自動(dòng)機(jī)在計(jì)算能力上也是等價(jià)的，從而實(shí)現(xiàn)了加權(quán)有窮自動(dòng)機(jī)的狀態(tài)極小化。此外，我們給出了加權(quán)有窮自動(dòng)機(jī)的可交換性、分離性、(強(qiáng))連通性及層的概念，討論了在(強(qiáng))同態(tài)的條件下，兩個(gè)加權(quán)有限狀態(tài)機(jī)之間的可交換性、分離性、(強(qiáng))連通性及層的關(guān)系。這些研究結(jié)果進(jìn)一步豐富了加權(quán)自動(dòng)機(jī)的理論。

[1] Shannon C E, MeCary J. Automata studies[M]. Prineeton:Prineeton University Press, 1956.

[2] Hopcroft J E, Ullman J D. Introduction to automata theory, languages and computation[M]. New York:Addison-Wesley, 1979.

[3] Zadeh L A. Outline of a new approach to the analysis of complex systems and decision processes[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1973(1):28-44.

[4] Mordeson J N, Malik D S. Fuzzy and languages:Theory and applications[M]. Boca Paton:Chapman &Hall/CRC, 2002.

[5] Malik D S, Mordeson J N, Sen M K. On subsystems of a fuzzy finite state machines[J]. Fuzzy Sets and Systems,1994,68(2):83-92.

[6] Schützenberger M P. On the definition of a family of automata[J]. Information and Control,1961(4):245-270.

[7] Salomaa A, Soittola M. Automata theoretic aspects formal power series[M]. Berlin:Springer, 1978.

[8] Droste M,Kuich W,Vogler H.A Kleene theorem for weighted tree automata[J]. Theory of Computing Systems, 2005,38(1):1-38.

[9] Droste M, Gastin P. Weighted automata and weighted logics[J]. Theoretical Computer Science,2007,380(1-2):69-86.

[10] Berstel J, Reutenauer C. Noncommutative rational series with applications, encyclopedia of mathematics and its applications[M]. Cambridge:Cambridge University Press, 2010.

[11] Li Y M,Wang Q.The universal fuzzy automation[J].Fuzzy Sets and Systems,2014,249:27-48.

[12] Li Y M. Analysis of fuzzy systems[M].Beijing:Science Press,2005.(in Chinese)

[13] Ong G H, Kai Y. A binary partitioning approach to image compression using weighted finite automata for large images[J]. Computers & Mathematics with Applications, 2006, 51(11):1705-1714.

[14] Albert J, Kari J. Digital image compression[M]∥Handbook of Weighted Automata[M]. Berlin:Springer -Verlag,2009(Chapter11).

[15] Bouyer P. Weighted timed automata:Model-checking and games[J]. Electronic Notes in Theoretical Computer Science, 2006, 158(5):3-17.

[16] Kuroki N, Mordeson J N. Successor and source functions[J]. J Fuzzy Math, 1997(5):173-182.

[17] Srivastava, A K, Tiwari S P. A topology for fuzzy automata [C]∥Proc of AFSS’02, 2002:485-490.

[18] Srivastava A K , Tiwari S P. On another decomposition of fuzzy automata [J]. Journal of Uncertain Systems, 2011,5(1):33-37.

[19] Tiwari S P, Singh A K, Sharan S. Fuzzy automata based on lattice-order monoid and associated topology[J]. Journal of Uncertain Systems, 2012,6(1):51-55.

[20] Tiwari S P, Sharan S. Fuzzy automata based on lattice-ordered monoid with algebraic and topological aspects[J]. International Journal of Fuzzy and Information Engineering, 2012, 4(2):155-164.

[21] Tiwari S P,Yadav V K,Anupam K S.On algebraic study of fuzzy automata [J]. International Journal of Machine Learning and Cybernetics,doi:10.1007/s13042-014-0233-5.

[22] Zamir B. Introduction to the theory of automata[M]. Virginia:Reston Publishing Company, 1983.

附中文參考文獻(xiàn):

[12] 李永明. 模糊系統(tǒng)分析[M].北京:科學(xué)出版社,2005.

ZHANGLi-xia,born in 1984,MS,lecturer,her research interests include representation theory of algebras, and algebraic theory of automata.

Algebraicpropertiesofweightedfinitestateautomata

ZHANG Li-xia

(School of Mathematics and Computation,Anqing Normal University,Anqing 246013,China)

On the basis of the theory of weighted finite automata,we prove the computing equivalence between two weighted finite automatas under the strong homomorphism of weighted finite automatas, and obtain the quotient weighted automata by establishing the equivalence relation on the states of weighted finite automata.Based on the equivalence relation,the equivalence between weighted finite automata and its quotient automata is also proved.Specifically,the concepts such as commutability,separateness,(strong) connectedness properties and layers of weighted finite automata are introduced,and their relations in two different weighted finite automata are discussed under the homomorphism or strong homomorphism.

formal power series;weighted finite automata;homomorphism;strong connectedness

1007-130X(2014)11-2186-05

2014-07-10;

：2014-09-16

安慶師范學(xué)院青年科研基金項(xiàng)目(KJ201214)；安徽省優(yōu)秀青年人才基金項(xiàng)目(2011SQRL097)

TP301

：A

10.3969/j.issn.1007-130X.2014.11.022

張麗霞(1984),女,安徽安慶人，碩士，講師，研究方向?yàn)榇鷶?shù)表示論和自動(dòng)機(jī)代數(shù)理論。E-mail:zhanglix84@163.com

通信地址：246013 安徽省安慶市安慶師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院

Address:School of Mathematics and Computation,Anqing Normal University,Anqing 246013,Anhui,P.R.China