廣義標(biāo)準(zhǔn)自動(dòng)機(jī)及其商自動(dòng)機(jī)

徐　慧，田　徑，金英姬

(1.空軍工程大學(xué) 基礎(chǔ)部, 陜西 西安　710051;2.西安外國(guó)語(yǔ)大學(xué) 金融學(xué)院, 陜西 西安　710128；3.西藏民族大學(xué) 教育學(xué)院，陜西 咸陽(yáng)　712082)

1936年英國(guó)數(shù)學(xué)家Turing提出一種抽象的自動(dòng)機(jī)—圖靈機(jī),用來(lái)定義可計(jì)算函數(shù)類(lèi),自此開(kāi)創(chuàng)了自動(dòng)機(jī)理論的抽象研究[1]。二十世紀(jì)五六十年代,由于計(jì)算機(jī)、通信和人工智能的興起,自動(dòng)機(jī)理論得到了迅速發(fā)展。自動(dòng)機(jī)不僅成為計(jì)算機(jī)科學(xué)的理論基礎(chǔ),而且在信息科學(xué)、生命科學(xué)、管理學(xué)、控制學(xué)等眾多學(xué)科領(lǐng)域有著廣泛應(yīng)用[2-8]。

設(shè)自動(dòng)機(jī)A=(Q,Σ,δ), 任取q∈Q, 令〈q〉表示集合{δ(q,u) |u∈Σ*}。 稱(chēng)自動(dòng)機(jī)A(q)=(〈q〉,Σ,δ〈q〉×Σ)為由q生成的子自動(dòng)機(jī)[5], 其中δ〈q〉×Σ表示δ在〈q〉×Σ上的限制。 進(jìn)一步,若A=A(q), 則稱(chēng)q為A的生成元[10]。A的所有生成元構(gòu)成的集合用Gen(A) 表示,稱(chēng)之為生成元集。 若Gen(A)≠?, 則稱(chēng)A是循環(huán)自動(dòng)機(jī)[10]。

設(shè)A=(Q,Σ,δ)是循環(huán)自動(dòng)機(jī), 在Q上定義二元關(guān)系LE如下:

LE{(p,q)∈Q×Q| (?s∈Gen(A))p,q∈Os}，

其中

Os={f(s) |f∈E(A)}。

若LE是Q上的等價(jià)關(guān)系,則稱(chēng)A是標(biāo)準(zhǔn)自動(dòng)機(jī)[11]。

文獻(xiàn)[11-12] 中證明了循環(huán)交換異步自動(dòng)機(jī)和強(qiáng)連通自動(dòng)機(jī)是標(biāo)準(zhǔn)自動(dòng)機(jī)，同時(shí)將強(qiáng)連通自動(dòng)機(jī)的表示推廣到標(biāo)準(zhǔn)自動(dòng)機(jī)。在此基礎(chǔ)上,本文將介紹一類(lèi)非循環(huán)自動(dòng)機(jī),即廣義標(biāo)準(zhǔn)自動(dòng)機(jī)。我們將給出廣義標(biāo)準(zhǔn)自動(dòng)機(jī)的幾個(gè)刻畫(huà)。同時(shí),討論廣義標(biāo)準(zhǔn)自動(dòng)機(jī)的商自動(dòng)機(jī)的循環(huán)性。

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

設(shè)A=(Q,Σ,δ) 和B=(Q′,Σ,γ) 是自動(dòng)機(jī),f是從Q到Q′的映射。若對(duì)于任意的q∈Q和任意的x∈Σ有f(δ(q,x))=γ(f(q),x)成立,則稱(chēng)f是A到B的同態(tài)[10]。 若同態(tài)f是雙射,則稱(chēng)f為同構(gòu)[10]。 自動(dòng)機(jī)A到其自身的同態(tài)和同構(gòu)分別稱(chēng)為自同態(tài)和自同構(gòu)。我們用E(A)和G(A)分別表示A的自同態(tài)和自同構(gòu)的全體。 在通常意義的映射合成運(yùn)算下,E(A)和G(A)分別構(gòu)成幺半群和群,分別稱(chēng)為自同態(tài)幺半群和自同構(gòu)群[10]

設(shè)A=(Q,Σ,δ)，ρ是狀態(tài)集Q上的等價(jià)關(guān)系。 若對(duì)任意的p,q∈Q和任意的x∈Σ，有

(p,q)∈ρ?(δ(p,x),δ(q,x))∈ρ,

則稱(chēng)ρ是自動(dòng)機(jī)A上的同余[10]。按照泛代數(shù)中的記號(hào),我們將q所在的ρ類(lèi)記為ρq,即

ρq={p∈Q| (p,q)∈ρ}。

設(shè)A=(Q,Σ,δ),ρ是A上的同余。 記Q/ρ={ρq|q∈Q}, 對(duì)任意的ρq∈Q/ρ和任意的x∈Σ定義δρ(ρq,x)=ρδ(q,x)。 稱(chēng)自動(dòng)機(jī)A/ρ=(Q/ρ,Σ,δρ) 為A關(guān)于ρ的商自動(dòng)機(jī)。

若A=(Q,Σ,δ)是非循環(huán)自動(dòng)機(jī),則Gen(A)=?。 若存在S?Q, 使得Q=∪s∈S〈s〉, 即對(duì)任意的q∈Q, 存在s∈S和u∈Σ*，使得q=δ(s,u), 則稱(chēng)S是A的生成元集[13]。 進(jìn)一步, 如果對(duì)于任意的s,t∈S有 〈s〉≠〈t〉, 那么稱(chēng)S是A的極小生成元集[13]

設(shè)A=(Q,Σ,δ),S={s1,s2,…,sn}是A的極小生成元集。如果對(duì)任意的f∈E(A)和任意的i∈{1,2,…,n}有f(si)∈〈si〉, 那么我們就稱(chēng)A是廣義正規(guī)自動(dòng)機(jī)。

文中未定義的概念和符號(hào)請(qǐng)參考文獻(xiàn)[10,14]。

2　廣義標(biāo)準(zhǔn)自動(dòng)機(jī)的刻畫(huà)

設(shè)A=(Q,Σ,δ)是廣義正規(guī)自動(dòng)機(jī), 在Q上定義二元關(guān)系L如下:

其中Oi={f(si) |f∈E(A)}, [n]={1,2,…,n}。

容易驗(yàn)證，當(dāng)A是循環(huán)自動(dòng)機(jī)時(shí), L=LE。

設(shè)A=(Q,Σ,δ)是廣義正規(guī)自動(dòng)機(jī), 若L是Q上的等價(jià)關(guān)系, 則稱(chēng)A是廣義標(biāo)準(zhǔn)自動(dòng)機(jī)。

文獻(xiàn) [15]給出了L是等價(jià)關(guān)系的一個(gè)充分必要條件，結(jié)論如下。

引理1[15]設(shè)A=(Q,Σ,δ) 是廣義正規(guī)自動(dòng)機(jī),S={s1,s2,…,sn} 是A的極小生成元集, 則A是廣義標(biāo)準(zhǔn)自動(dòng)機(jī)當(dāng)且僅當(dāng)如下條件成立:

1)任意q∈Q存在i∈[n],f∈E(A)，使得q=f(si);

2)若f(si)=f(sj), 則i=j。

設(shè)A=(Q,Σ,δ)是廣義標(biāo)準(zhǔn)自動(dòng)機(jī), 任取i∈[n], 記Li={q∈Q| (q,si)∈L}。 根據(jù)L的定義可知,Li?Oi。 反之, 設(shè)q∈Oi, 則 (q,si)∈L。 這是因?yàn)閟i=I(si), 其中I是Q上的恒等映射,從而q∈Li。 這樣, 我們得到了如下結(jié)論。

命題1設(shè)A=(Q,Σ,δ)是廣義標(biāo)準(zhǔn)自動(dòng)機(jī), 則對(duì)任意的i∈[n]有Li=Oi。

在命題1的基礎(chǔ)上,立即可以得出廣義標(biāo)準(zhǔn)自動(dòng)機(jī)的一個(gè)刻畫(huà)。

定理1設(shè)A=(Q,Σ,δ) 是廣義正規(guī)自動(dòng)機(jī), 則A是廣義標(biāo)準(zhǔn)自動(dòng)機(jī)當(dāng)且僅當(dāng)對(duì)任意的q∈Q存在唯一的i∈[n] ，使得q∈Oi。

下面,我們證明L是廣義標(biāo)準(zhǔn)自動(dòng)機(jī)上的同余關(guān)系。

命題2若A=(Q,Σ,δ) 是廣義標(biāo)準(zhǔn)自動(dòng)機(jī), 則L是A上的同余關(guān)系。

證明設(shè)A=(Q,Σ,δ), 任取q,p∈Q。 若(q,p)∈L, 則存在i∈[n],f,h∈E(A) 使得q=f(si),p=h(si)。 任取u∈Σ*,根據(jù)引理1可知,存在j∈[n],g∈E(A) 使得δ(si,u)=g(sj)。 因此

δ(q,u)=δ(f(si),u)=f(δ(si,u))=(fg)(sj),

δ(p,u)=δ(h(si),u)=h(δ(si,u))=(hg)(sj),

從而(δ(q,u),δ(p,u))∈L。根據(jù)u的任意性可知,L是A上的同余。

3　商自動(dòng)機(jī)的循環(huán)性

設(shè)S={s1,s2,…,sn} 是A的極小生成元集。 顯然, 當(dāng)n=1時(shí)，A是循環(huán)自動(dòng)機(jī)。 此時(shí)，A/L也是循環(huán)的。 若n>1, 則A/L未必是循環(huán)自動(dòng)機(jī)。下面我們給出n=2 時(shí)A/L是循環(huán)自動(dòng)機(jī)的一個(gè)充分必要條件。

引理2設(shè)A=(Q,Σ,δ),S={s1,s2}是A的極小生成元集。 若A是廣義正規(guī)自動(dòng)機(jī),則〈s1〉∩〈s2〉≠?。

證明采用反證法。 假設(shè)〈s1〉∩〈s2〉=?,則對(duì)任意q∈Q,v∈Σ*有,q∈〈si〉 與δ(q,v)∈〈si〉是等價(jià)的。定義映射f:Q→Q如下:

f(s1)=s2,f(s2)=s2,

(?u∈Σ*)f(δ(s1,u))=δ(s2,u),

(?u∈Σ*)f(δ(s2,u))=δ(s2,u)。

可以證明f∈E(A)。由于f(s1)∈〈s2〉, 這與A是廣義正規(guī)自動(dòng)機(jī)矛盾。 因此假設(shè)錯(cuò)誤, 所以〈s1〉∩〈s2〉≠?。

引理3設(shè)A=(Q,Σ,δ) 是廣義標(biāo)準(zhǔn)自動(dòng)機(jī),S={s1,s2} 是A的極小生成元集, 則A/L是循環(huán)自動(dòng)機(jī)當(dāng)且僅當(dāng)〈s1〉∩〈s2〉≠?。

證明(必要性)由于A是廣義正規(guī)自動(dòng)機(jī), 且|S|=2, 所以 |Q/L|=2。 若A/L是循環(huán)自動(dòng)機(jī), 則Gen(A/L)≠?。 不妨設(shè)L1∈Gen(A/L), 則存在u∈Σ*使得δL(L1,u)=L2, 即Lδ(s1,u)=L2。 從而δ(s1,u)∈L2。 由于A是廣義正規(guī)自動(dòng)機(jī),L2?〈s2〉, 因此,δ(s1,u)∈〈s2〉。 故〈s1〉∩〈s2〉≠?。

(充分性)若〈s1〉∩〈s2〉≠?, 則存在s∈〈s1〉∩〈s2〉。 由于A是廣義標(biāo)準(zhǔn)自動(dòng)機(jī), 根據(jù)引理1可知,存在i∈{1,2}使得s∈Oi。 不妨假設(shè)s∈O1, 那么存在f∈E(A) 使得s=f(s1)。 另一方面, 由于s∈〈s2〉, 存在u∈Σ*使得s=δ(s2,u)。 因此s=f(s1)=δ(s2,u)。 從而L1=Ls=Lδ(s2,u)=δL(Ls2,u)。 故L2∈Gen(A/L), 所以A/L是循環(huán)自動(dòng)機(jī)。

注意到廣義標(biāo)準(zhǔn)自動(dòng)機(jī)是廣義正規(guī)自動(dòng)機(jī), 根據(jù)上述兩個(gè)引理可得

命題3設(shè)A=(Q,Σ,δ)是廣義標(biāo)準(zhǔn)自動(dòng)機(jī)。若S={s1,s2} 是A的極小生成元集 (即極小生成元集中有兩個(gè)元素),則A/L是循環(huán)自動(dòng)機(jī)。

命題4設(shè)A=(Q,Σ,δ) 是廣義標(biāo)準(zhǔn)自動(dòng)機(jī),S={s1,s2,…,sn} 是A的極小生成元集 (n≥3), 若A/L是循環(huán)的, 則存在i∈[n], 使得對(duì)任意的j∈[n](j≠i) 有〈s1〉∩〈s2〉≠?, 并且Li∈Gen(A/L)。

證明若A/L是循環(huán)自動(dòng)機(jī), 則存在i∈[n] 使得Li∈Gen(A/L)。 從而對(duì)任意的j∈[n]存在uj∈Σ*使得δL(Li,uj)=Lj。 即Lδ(si,uj)=Lj。 故δ(si,uj)∈Lj?〈sj〉。 因此〈s1〉∩〈s2〉≠?。

命題5設(shè)A=(Q,Σ,δ)是廣義標(biāo)準(zhǔn)自動(dòng)機(jī),S={s1,s2,…,sn}是A的極小生成元集。 若對(duì)任意i,j∈[n] (i≠j) 有〈s1〉∩〈s2〉≠?, 則A/L是循環(huán)自動(dòng)機(jī)。

證明任取i,j∈[n], 若〈s1〉∩〈s2〉≠?, 則存在s∈〈s1〉∩〈s2〉。 不妨設(shè)s∈Oi, 那么存在f∈E(A) 使得s=f(si)。 另一方面,由于s∈〈sj〉, 存在u∈Σ*使得δ(sj,u)=s。 因此,Li=Ls=Lδ(sj,u)=δL(Lsj,u)。 即Lj可以到達(dá)Li。 根據(jù)i,j的任意性可知,A/L是循環(huán)自動(dòng)機(jī)。

參考文獻(xiàn)：

[1]TURING A M. On computable number, with an application to the Entscheidungs problem[J].Proceedings of the London Mathematical Society, 1936,2(42):230-265.

[2]RABIN M O, SCOTT D. Finite automata and their decision problems [J]. IBM Journal of Research and Development, 1959, 3 (2): 114-125.

[3]SCHüTZENBERGER M P. On the definition of a family of automata [J]. Information and Control, 1961, 4(2): 245-270.

[4]MOHRI M. Finite-state transducers in language and speech processing [J].Computational linguistics, 1997, 23(2): 269-311.

[5]RAMASUBRAMANIAN S V, KRITHIVASAN K. Finite automata digital images [J].International Journal of Pattern Recognition and Artificial Intelligence, 2000, 14:501-524.

[6]ANDERSON J A. Automata Theory with Modern Applications [M].Cambridge：Cambridge University Press, 2006.

[7]GOPALAKRISHNAN G. Computation Engineering: Applied Automata Theory and Logic[M]. New York: Springer, 2006.

[8]KOHAVI Z, JHA N K. Switching and Finite Automata Theory [M].Cambridge：Cambridge University Press, 2010.

[9]FLECK A C. Isomorphism groups of automata [J]. Journal of the Association for Computing Machinery, 1962, 9(4): 469-476.

[10] HOWIE J M. Automata and Languages[M]. Oxford: Clarendon Press, 1991.

[11] TIAN J, ZHAO X Z. Representations of commutative asynchronous automata [J].Journal of Computer and System Sciences, 2012, 78: 504-516.

[12] 田徑. 關(guān)于自動(dòng)機(jī)代數(shù)理論的研究 [D]. 西安: 西北大學(xué), 2012.

[13] BAVEL Z. Structure and transition-preserving functions of finite automata [J].Journal of the Association for Computing Machinery, 1968, 15 (1): 135-158.

[14] ITO M. Algebraic Theory of Automata and Languages [M].Oxford：World Scientific Publishing Co.Pte.Ltd., 2004.

[15] 徐慧, 田徑, 馮軍慶. 有關(guān)本原自動(dòng)機(jī)的研究 [J]. 空軍工程大學(xué)學(xué)報(bào), 2016,17(2):88-90.