基于有限狀態機最小化理論的同余關系研究
2009-01-01 00:00:00郭凱紅李文立
計算機應用研究 2009年5期
(1.大連理工大學 管理學院 遼寧 大連 116023； 2.遼寧大學 信息學院 沈陽 110036)
摘 要：對有限狀態機(FA)的最小化理論進行了研究，提出了原機器M與其最小機器M′之間還存在一種更近的關系，即同余關系。為機器M與M′構造相關的代數系統，證明了兩者之間存在同余關系。實驗表明，同余關系對簡化系統描述具有重要意義，為揭示原系統與約簡系統之間蘊涵的更為深刻的內在關系提供了必要的理論基礎。
關鍵詞：有限狀態機； 約簡； 代數系統； 同余關系
中圖分類號：TP301.1文獻標志碼：A
文章編號：1001-3695(2009)05-1746-03
Study of congruence relation based on minimization theory of FA
GUO Kaihong1，2 LI Wenli1
(1.School of Management Dalian University of Technology Dalian Liaoning 116023 China; 2. College of Information Liaoning University Shenyang 110036 China)
Abstract:Studied minimization theory of finite automata(FA) and proposed the existence of congruence relation which was much closer than equivalence relation between minimized automata M′ and original one M proposed. Proved the existence of congruence relation between M′ and M by constructing the corresponding algebraic system respectively. Experiment results show the significance of congruence relation for systemsimplified description and it provides the necessary theoretical basis for disclosing the deeply internal relationship between original system and reduction one.
Key words：finite automata; reduction; algebraic system; congruence relation
Melay機與Moore機[1]是兩種不同的帶有輸出的有限狀態機，均是一個六元組M=(Q，S，R，f，O，qI)。Melay機的輸出符號不僅與機器所處的狀態有關，而且還與輸入字母有關；而Moore機的輸出只與到達狀態有關，與從哪個狀態轉換而來無關。由于它們帶有輸出，從抽象的角度考慮，已經沒有必要再設置終止狀態集[1]。文獻[2]給出了這兩類自動機轉換的方法以及由此產生的關于自動機最小化問題必要性的討論。有限狀態機的最小化理論最初見于文獻[3，4]，在此方面，許多學者針對不同類型的自動機研究了它們的最小化問題[5~11]。文獻[2]使用狀態數目作為效率的度量，給出了帶有輸出的有限狀態機的最小化理論和最小化算法。該算法可以將任意正確但卻冗余的機器構造產生出等價的、更有效的機器；文獻[8]基于有限狀態機的矩陣模型，以矩陣理論和布爾代數為工具給出了一種有限狀態機最小化的新方法；文獻[9]從行為矩陣出發，給出了完備的同步格值自動機狀態等價和自動機等價的定義，研究了該自動機可約簡的條件，并得到了該自動機的最小化算法。這些研究成果主要集中在自動機模型本身等價約簡的問題上，極少從更高角度重新審視原模型與其簡化模型，即原系統與約簡系統之間的內在關系。這里所謂更高級的內在關系已不再是兩者間簡單的等價關系，而是比等價關系更強的一種關系，即同余關系。本文在等價約簡的基礎上，進一步研究了原機器與其最小機器的邏輯關系，提出并證明了兩者之間不僅是等價的，還是同余的，為揭示原系統與約簡系統之間蘊涵的更為深刻的內在關系（如運算或表示）提供了必要的理論基礎，以便更嚴謹地在動態環境下建立不完備或不協調信息(決策)系統[12~14]的約簡任務模型。
1 記號及預備
設S是一個有限字母表，將笛卡兒積S×S×…×Sk記為Sk。用Sk表示所有長度為k的串組成的集合，即Sk={ω‖ω｜=k}。
設S是一個有限字母表，S的正閉包S+=∪∞i=1Si={ω‖ω｜≥1}表示字母表S上所有非空串的集合；S的克林閉包S=∪∞i=0Si={ω‖ω｜≥0}表示字母表S上所有串的集合。
設S是一個有限字母表 ○ 是S上的一個二元運算，稱為串的連接運算。對于S上的任意兩個串ω＝u1u2…um和φ=v1v2…vn，記ω ○ φ＝u1u2…umv1v2…vn。
定義1[15~17] 設R為集合A上的等價關系，對任何a∈A，集合[a]R={x｜x∈A，aRx}稱為元素a形成的R等價類。
定義2[15~17] 集合A上的等價關系R，其等價類集合{[a]R｜a∈A}稱做A關于R的商集，記做A/R。
定義3[15~17]設〈A ● 〉是一個代數系統，并設R是A上的一個等價關系。如果當〈a1，a2〉，〈b1，b2〉∈R時，蘊涵著〈a1
● b1，a2 ● b2〉∈R，則稱R為A上關于●的同余關系。由這個同余關系將A劃分成的等價類就稱為同余類。
定義4[18] 設機器M1=(Q1，S1，R1，f1，O1，q′I)，M2=(Q2，S2，R2，f2，O2，q″I)，如果滿足：S1=S2，R1=R2；對于任意非空激勵ω，有O1(q′I，ω)=O2(q″I，ω)，則稱M1和M2是等價的，記做M1~M2。可以驗證，有限狀態機之間的關系 ~ 是有限狀態機集合上的等價關系。
定義5[18] 機器M=(Q，S，R，f，O，qI)的兩個狀態qa和qb是等價的，當且僅當Ma=(Q，S，R，f，O，qa)和Mb=(Q，S，R，f，O，qb)是等價的，記做qa~qb。
2 主要結論及證明
機器M與其最小機M′具有等價關系[1，2，18]。事實上，兩者之間還存在著一種更近的關系，即同余關系。同余關系是一種更強的等價關系[17]，它使得[x]R中任一元素與[y]R中任一元素運算后，結果都在同一個等價類內。應該注意，并非任何等價關系都是同余關系，這與代數系統的運算密切相關。
下面給出本文的主要結論。
對給定機器M=(Q，S，R，f，O，qI)，經最小化計算后得到一臺等價的最小機
M′=(Q′，S，R，f′，O′，q′I)
則機器M與M′具有同余關系。
證明 令｜Q｜=n，分別為機器M與M′構造相關的代數系統。
對于機器M，設集合A=Q∪S+，在A上定義二元運算●為
a)q ● ω=ω ● q=f(q，ω)=q′。其中q，q′∈Q，ω∈S+。
b)ω1 ● ω2=ω1 ○ ω2。其中ω1，ω2∈S+，即任意兩個激勵ω1，ω2的 ● 運算等價于它們的連接運算 ○ 。
c)
q1 ● q2=q2 若q1ωq2ω∈S+，q1，q2∈Qq1 否則
可用謂詞邏輯表示為
q1 ● q2=q2 iff q1q2ω(q1∈Q∧q2∈Q∧
ω∈S+f(q1，ω)=q2)
簡稱q1到q2可轉換；若q1到q2不可轉換，則定義q1●q2=q1。
代數系統〈A，●〉可用表1簡化表示。
對于機器M′，設集合B=Q′∪S+，由于Q′是機器M狀態集Q關于狀態等價關系R的等價類集合，即Q′=Q/R，則有
Q′={[q]R｜q∈Q}={Q1，Q2，…，Qr}
其中：Qi=[qj]R，qj∈Q，1≤i≤r＜n，1≤j≤n。
在B上定義二元運算*如下：
a)對于Qi，Qj∈Q′，ω∈S+，任取q1∈Qi，q2∈Qj，如果q1 ● ω=q2，則Qi*ω=ω*Qi=Qj。由于R是Q上的狀態等價關系，以上定義的Qi*ω=Qj是惟一的。
事實上，qa，qb∈Qi，因為qa~qb；對任意激勵ω∈S+，有f(qa，ω)~f(qb，ω)，即qa
●ω~qb●ω。令q′a=qa●ω，q′b=qb●ω，由狀態等價關系可知，必有[q′a]R=[q′b]R，即q′a∈Qj∧q′b∈Qj。所以，Qi*ω=Qj是惟一的。
b)ω1*ω2=ω1● ω2=ω1 ○ ω2。其中ω1，ω2∈S+，即任意兩個激勵ω1，ω2的*運算與它們的●運算相同。
c)對于Qi，Qj∈Q′，任取q1∈Qi，q2∈Qj，定義如下：
Qi*Qj=Qj 若q1● q2=q2Qi 若q1● q2=q1
顯然，Qi*Qj的結果由q1●q2的結果決定。由于Qi，Qj均是等價類，對任意的q1∈Qi，q2∈Qj，q1●q2的結果惟一，Qi*Qj的結果也是惟一的。
代數系統〈B，*〉可用表2簡化表示。
作映射g:A→B如下：
g(x)=Qi x∈Qixx∈S+
顯然，g是從A到B的滿映射。
對于q∈Q，ω∈S+，q必屬于B中Q′的某個等價類，不妨令q∈Qi；同時，q ● ω=q′，q′也必屬于Q′的某個等價類。不妨令q′∈Qj，于是有
g(q ● ω)=g(q′)=Qj=Qi*ω=g(q)*g(ω)(1)
g(ω ● q)=g(q ● ω)=g(q′)=Qj=Qi*ω=
ω*Qi=g(ω)*g(q)(2)
對于ω1，ω2∈S+，有
g(ω1●ω2)=g(ω1○ω2)=ω1○ω2=ω1*ω2=g(ω1)*g(ω2)
(3)
對于q1，q2∈Q，q1，q2必屬于B中Q′的某兩個狀態等價類，不妨令q1∈Qi，q2∈Qj；同時，必有q1 ● q2=q2或q1 ● q2=q1。不妨令q1 ● q2=q2，于是有
g(q1 ● q2)=g(q2)=Qj=Qi*Qj=g(q1)*g(q2)(4)
由式（1）~（4）可知，g是由〈A，●〉到〈B，*〉的滿同態，即〈B，*〉是〈A，●〉的同態象。
已知R是A中狀態集Q上的狀態等價關系，令〈q1，q′1〉∈R，〈q2，q′2〉∈R，即
q1∈Qi∧q′1∈Qi，q2∈Qj∧q′2∈Qj
由式(4)可得
g(q1 ● q2)=g(q1)*g(q2)=Qi*Qj=g(q′1)*g(q′2)=g(q′1 ● q′2)
由此可知q1 ● q2與q′1 ● q′2屬于同一個等價類，即
(q1● q2)∈Qk∧(q′1● q′2)∈Qk〈q1● q2，q′1● q′2〉∈R k=i或j
因此，R是A中狀態集Q上的同余關系，而B=Q′∪S+={[q]R｜q∈Q}∪S+={Q1，Q2，…，Qr，S+}
是由同余關系R所誘導的A的一個劃分。所以機器M與M′具有代數同余關系。證畢。
3 實驗分析
設給定一臺機器
M=({A，B，C，D，E，F，G，H，J}，{0，1}，{0，1}，f，O，qI)
其狀態圖和狀態表分別如圖1和表3所示。
為了簡化機器M，首先構造其等價劃分P。從表3可知
O(A，0)=O(C，0)=O(F，0)=0O(A，1)=O(C，1)=O(F，1)=0
所以A~1C~1F，又有
O(B，0)=O(D，0)=O(E，0)=O(G，0)=1O(B，1)=O(D，1)=O(E，1)=O(G，1)=1
所以B~1D~1E~1G。同理，
O(H，0)=O(J，0)=1O(H，1)=O(J，1)=0
所以H~1J。于是得
P1={{A，C，F}，{B，D，E，G}，{H，J}}。因為f(A，0)=B，f(C，0)=D，f(F，0)=G，它們都在P1的同一等價類中，而f(A，1)=f(F，1)=C，f(C，1)=E，狀態A、F的1后繼在P1的同一等價類中，而狀態C的1后繼在P1的另一等價類中，P1中的等價類{A，C，F}應加細為{A，F}和{C}。
狀態B、D、E、G的0后繼均在P1的等價類{A，C，F}中，1后繼均在P1的等價類{B，D，E，G}中，所以它們仍在P2的同一等價類中。
狀態H、J的0后繼均在P1的等價類{H，J}中，1后繼均在P1的等價類{B，D，E，G}中，所以不再需要加細。因此P2={{A，F}，{C}，{B，D，E，G}，{H，J}}。同理可得
P3={{A，F}，{C}，{B，D}，{E，G}，{H，J}}P4={{A} {F}，{C}，{B，D}，{E，G}，{H，J}}P5=P4
因此，P={{A}，{F}，{C}，{B，D}，{E，G}，{H，J}}。
下面構造與機器M等價的簡化機M′。定義M′中的新狀態名U、V、W、X、Y、Z，令U={A}，V={F}，W={C}，X={B，D}，Y={E，G}，Z={H，J}。
表4給出了新狀態與等價類之間的對應關系。機器M′的狀態圖和狀態表分別如圖2和表5所示。
顯然，簡化機M′的狀態數比機器M的狀態數少，M中的某些狀態在簡化過程中被合并了，如狀態B和D被合并成狀態X，狀態E和G被合并成狀態Y，狀態H和J被合并成狀態Z。由于這些狀態間彼此有運算關系，符合代數系統的定義，從數學的角度看它們是可以被合并的。M中的某些狀態在最初的設計過程中出現了冗余，雖然冗余機同樣可以正常工作，但畢竟它不是最有效的[19]。如果某幾個有運算關系的狀態能夠被一個具有更強等價關系的狀態替代，同時又絲毫不影響原系統的功能，就實現了這個復雜系統的簡化問題，從而用一個簡單的新系統替代原系統。這種更強的等價關系就是同余關系，它使得原系統的狀態完全可以用同余類之間的相互關系來重新描述。不僅如此，可根據具體問題和實際需求進一步研究原系統的某些狀態與其同余類之間的關系，進而揭示出原系統與新系統整體或局部間隱含的本質聯系，更嚴謹地建立基于FA描述的新系統任務模型，使新系統更加有意義。
4 結束語
最小化問題是有限狀態機應用及實現的重要問題之一。一些基本文獻如[1~4，18，20]指出，對一臺給定的機器M，經最小化計算后得到M的最小化機器M′，則M與M′是等價的。本文基于代數系統證明了機器M與M′之間不僅是等價的，還是同余的。這使得原系統(機器M)的狀態完全可以用同余類之間的相互關系(機器M′)重新描述，不僅實現了系統簡化的目的，還可深刻揭示新舊系統間內在的、本質的聯系。實驗表明，同余關系對系統描述具有重要意義。對于某些不適合用FA描述的信息(決策)系統任務模型，一定程度上限制了同余關系的應用范圍，可尋求其他（如基于粗糙集理論）系統等價約簡方法[21~23]。
參考文獻：
［1］蔣宗禮，姜守旭.形式語言與自動機理論[M].北京:清華大學出版社，2003:123-125.
[2]左孝凌，李為監，劉永才.離散數學[M].上海:上海科技文獻出版社，1982:371-385.
[3]HUFFMAN D A. The synthesis of sequential switching circuits[J]. Journal of the Franklin Institute 1954，257（3）:3-4，161-190 275-303.
[4]MOOR E F. Automata studies[M]. Princeton: Princeton University Press 1956:129-153.
[5]PEEVA K. Behavior reduction and minimization of finite Lautomata[J]. Fuzzy Sets and Systems 1998，28(2):171-181.
[6]MALIK S MORDESON J N. Minimization of fuzzy finite automata[J]. Information Science 1999，113（3-4）:323-330.
[7]孫玉強，李玉萍，王海燕.確定有限自動機最小化算法的并行處理[J].計算機科學，2008，35(1):298-300.
[8]朱征宇，王術，趙銀春.基于矩陣模型表示的有限自動機極小化方法[J].計算機工程與應用，2004，40(35):47-49.
[9]雷紅軒，李永明.同步格值自動機的約簡和最小化算法[J].計算機工程與應用，2006，42(16):57-60.
[10]韓光輝，段國麗.有限自動機最小化算法的實現[J].湖北工業大學學報，2006，21(2):69-71.
[11]蔣龍龍，陳文宇.利用等價類構造有限狀態自動機[J].計算機科學，2006，33(11):272-277.
[12]陳鑫影，邱占芝.不協調決策信息系統的約簡[J].計算機工程與應用，2008，44(7):193-195.
[13]楊習貝，於東軍，吳陳.不完備信息系統中基于相似關系的知識約簡[J].計算機科學，2008，35(2):163-165.
[14]韓江洪，張亞瓊，魏振春.基于規則的離散事件系統模型與規則匹配研究[J].系統仿真學報，2008，20(6):1394-1396.
[15]FEIL T KRONE J. Essential discrete mathematics for computer science[M]. Hertfordshire: Cunberland House 2005:205-206.
[16]JOSEPH J R. A first course in abstract algebra[M]. 2nd ed. Chicago: Wiley 2004:142-144.
[17]邵秀麗，王孝喜.離散數學[M].北京:科學出版社，2005:211-212.
[18]霍普克羅夫特.自動機理論、語言和計算導引[M].北京:科學出版社，1986:79-93.
[19]韓江洪，鄭淑麗.離散事件控制系統規則化描述方法的研究[J].合肥工業大學學報:自然科學版，2005，28(9):1081-1084.
[20]上下文無關語言的數學理論[M]. 陳力行，譯. 濟南:山東大學出版社，1986:52-63.
[21]陳娟，王國胤，胡軍.優勢關系下不協調信息系統的正域約簡[J].計算機科學，2008，35(3):216-218.
[22]丁軍，高學東.一種信息系統的快速屬性約簡算法[J].計算機工程與應用，2007，43(14):173-176.
[23]張騰飛，王錫淮，肖健梅.不完備信息系統的一種屬性相對約簡算法[J].計算機工程，2007，33(9):184-185.
