田徑，徐慧

（1.西安外國語大學(xué)經(jīng)濟金融學(xué)院，陜西西安710128；2.空軍工程大學(xué)理學(xué)院，陜西西安710051；3.西安理工大學(xué)理學(xué)院，陜西西安710048）

確定權(quán)重有限自動機的同余及極小自動機

田徑1，3，徐慧2

（1.西安外國語大學(xué)經(jīng)濟金融學(xué)院，陜西西安710128；2.空軍工程大學(xué)理學(xué)院，陜西西安710051；3.西安理工大學(xué)理學(xué)院，陜西西安710048）

主要研究對象是強雙幺半群上的確定權(quán)重有限自動機A.首先給出了A上的同態(tài)定理和同構(gòu)定理；接著，構(gòu)造了識別φ的一個極小自動機Aφ；最后，證明極小自動機在同構(gòu)意義下是唯一的.

確定權(quán)重自動機；同余；極小自動機

1　引言

自動機理論是計算機科學(xué)的基礎(chǔ)，自動機上的同余和極小化問題是自動機理論的經(jīng)典問題［1-3］.近幾年，很多學(xué)者對此進行了深入研究.T.Petkovi?在文獻［4］中定義并討論了fuzzy-自動機上的同余和同態(tài)，同時證明了fuzzy-自動機的同態(tài)定理.文獻［5］討論了識別分配格上正則語言的極小權(quán)重自動機.本文討論強雙幺半群上確定權(quán)重有限自動機的同余及極小自動機，將文獻［4-5］中的部分結(jié)果推廣到強雙幺半群.

2　預(yù)備知識

本節(jié)將給出本文用到的基本概念.

設(shè)（K，+，·，0，1）是一個（2，2，0，0）-型代數(shù).若（K，+，0）和（K，·，1）都是含幺半群，則稱（K，+，·，0，1）是雙幺半群［3］，簡記為K.進一步，如果（K，+，0）是交換的含幺半群并且對任意的a∈K有a·0=0·a=0，那么就稱K是強雙幺半群.

定義2.1［6］設(shè)Σ是有限字母表，（K，+，·，0，1）是強雙幺半群，稱四元組A=（Q，δ，σ，τ）是關(guān)于Σ和K上的權(quán)重有限自動機，其中：Q為非空有限集，稱為狀態(tài)集；δ：Q×Σ×Q→K稱為權(quán)重轉(zhuǎn)換函數(shù)；σ：Q→K稱為初始權(quán)重向量；τ：Q→K稱為終止權(quán)重向量.

設(shè)A=（Q，δ，σ，τ）是關(guān)于Σ和K上的權(quán)重有限自動機.若對任意x∈Σ和任意q∈Q，存在q′∈Q使得δ（q，x，q′）=1，任取p∈Q｛q′｝有δ（q，x，p）=0，則稱δ是確定的.若存在q0∈Q使得σ（q0）=1，任取q∈Q｛q0｝有σ（q）=0，則稱σ是確定的.若δ和σ都是確定的，則稱A是確定的［7］.

事實上，確定權(quán)重有限自動機等價于四元組A=（Q，δ，q0，τ），其中Q是狀態(tài)集，δ：Q×Σ-→Q是狀態(tài)轉(zhuǎn)換函數(shù)，q0∈Q是初始狀態(tài)，τ：Q→K為終止權(quán)重向量.δ可以擴張成Q×Σ到Q上的函數(shù)如下：

強雙幺半群上確定權(quán)重自動機和經(jīng)典確定自動機的不同之處在于終止狀態(tài)構(gòu)成一個強雙幺半群，從而可以識別強雙幺半群上的形式冪級數(shù).設(shè)Σ是有限字母表，（K，+，·，0，1）是強雙幺半群，稱映射φ：Σ?→K為Σ和K上的形式冪級數(shù)［4］，記作

其中（φ，w）=φ（w）.Σ和K上的形式冪級數(shù)的全體記為K〈〈Σ?〉〉.

設(shè)A=（Q，δ，q0，τ）是確定權(quán)重自動機，A的行為‖A‖∈K〈〈Σ?〉〉定義如下：

設(shè)φ∈K〈〈Σ?〉〉，若存在確定權(quán)重有限自動機A使得φ=‖A‖，則稱φ是K-正則的.

下文中，Σ表示非空有限集，K=（K，+，·，0，1）為強雙幺半群，A=（Q，δ，q0，τ）是關(guān)于Σ和K上的確定權(quán)重有限自動機.

3　確定權(quán)重有限自動機上的同余和同態(tài)

設(shè)A=（Q，δ，q0，τ），ρ是Q上的等價關(guān)系.設(shè)p，q∈Q，x∈Σ，若

則稱ρ是A上的同余［4］.進一步，利用數(shù)學(xué)歸納法可以證明

引理3.1設(shè)ρ是A上的同余，p，q∈Q，若（p，q）∈ρ，則對于任意的u∈Σ?，有（δ（p，u），δ（q，u））∈ρ.

設(shè)ρ是A上的同余，令Qρ=Q/ρ.定義δρ：Qρ×Σ→Qρ為

定義τρ：Qρ→K為

稱Aρ=（Qρ，δρ，［q0］ρ，τρ）為A的權(quán)重商自動機［4］.

設(shè)Aρ=（Qρ，δρ，［q0］ρ，τρ）是A關(guān)于ρ的權(quán)重商自動機.引理1表明δρ可以擴張成δρ：Qρ×Σ?→Qρ：

定義3.1［4］設(shè)A=（Q，δ，q0，τ），A′=（Q′，δ′，q′0，τ′），若映射φ：Q→Q′滿足：

（1）φ（q0）=q′0；

（2）（?q∈Q，x∈Σ）φ（δ（q，x））=δ′（φ（q），x）；

（3）（?q∈Q）τ（q）=τ′（φ（q））.

則稱φ是A到A′的同態(tài).若同態(tài)φ是滿（單）的，則稱之為滿（單）同態(tài).若同態(tài)φ既是滿的也是單的，則稱之為同構(gòu)映射，此時稱A和A′是同構(gòu)的，記作A?A′.

引理3.2設(shè)A=（Q，δ，q0，τ），A′=（Q′，δ′，q′0，τ′），若φ：Q→Q′是A到A′的同態(tài)，則kerφ=｛（p，q）∈Q×Q|φ（p）=φ（q）｝是A上的同余.

定理3.1（同態(tài)定理）設(shè)A=（Q，δ，q0，τ），A′=（Q′，δ′，q′0，τ′）.若α是A到A′的同態(tài)，則存在Akerα到A′的唯一單同態(tài)β使得α=β?（kerα）?.

證明設(shè)同態(tài)α：Q→Q′，定義β：Q/kerα→Q′如下：顯然α=β?（kerα）?.設(shè)p，q∈Q，若［p］kerα=［q］kerα，則（p，q）∈kerα，從而α（p）=α（q）.即β定義是合理的且是單射.任取x∈Σ，則

假設(shè)γ：Q/kerα→Q′是滿足α=γ?（kerα）?的一個同態(tài)，則任意p∈Q，有

綜上可知，如上定義的β是滿足α=β?（kerα）?的唯一單同態(tài).

定理3.2（同構(gòu)定理）設(shè)A=（Q，δ，q0，τ），A′=（Q′，δ′，q′0，τ′）.若α：Q→Q′是A到A′的同態(tài)，則

證明顯然α：Q→α（Q）是A到α（A）的滿同態(tài).根據(jù)定理1知存在單同態(tài)

使得α=β?（kerα）?，所以

4　確定權(quán)重有限自動機的極小化

本節(jié)將討論識別K-正則語言的極小自動機，為此，我們先給出可達自動機和約簡自動機的概念.

設(shè)A=（Q，δ，q0，τ），p∈Q，若存在u∈Σ?，使得p=δ（q0，u），則稱q是可達的.我們記Qa=｛δ（q0，u）|u∈Σ?｝.令δa=δ|Qa×Σ，τa=τ|Qa，稱Aa=（Qa，δa，q0，τa）是A的可達部分.若Aa=A，則稱A是可達的［4］.

設(shè)A=（Q，δ，q0，τ），定義Q上的等價關(guān)系π如下：

如果π是恒等關(guān)系，那么就稱A是約簡自動機.

設(shè)φ∈K〈〈Σ?〉〉.若φ是K-正則的，則存在確定權(quán)重有限自動機A=（Q，δ，q0，τ）使得‖A‖=φ.如果A是可達和約簡的，那么稱A是識別φ的極小自動機.

設(shè)φ∈Σ?，定義Σ?上的等價關(guān)系ρφ如下：

其中，u-1φ∈K〈〈Σ?〉〉，且任取w∈Σ?有（u-1φ，w）=（φ，uw）.

作為文獻［2］中定理3.2的一個推廣，我們有

引理4.1設(shè)φ∈K〈〈Σ?〉〉，則φ是K-正則的?Σ?/ρφ是有限集.

設(shè)φ是K-正則的，則Σ?/ρφ是有限集.令A(yù)φ=（Qφ，δφ，φ，τφ），其中

顯然Aφ是可達的且‖A‖φ=φ，進一步可以驗證Aφ是約簡的.事實上，設(shè)（u-1φ，v-1φ）∈π，則任取w∈Σ?，有

即

從而

故

這樣就證明了

定理4.1若φ是K-正則的，則Aφ=（Qφ，δφ，φ，τφ）是識別φ的極小自動機.

下面的定理4表明識別φ的極小自動機在同構(gòu)意義下是唯一的.

定理4.2設(shè)φ∈K〈〈Σ?〉〉，‖A‖=φ.若A是可達約簡的，則A?Aφ.

［1］Rabin M O，Scott D.Finite automata and their decision problems［J］.IBM Journal of Research and Development，1959，3（2）：114-125.

［2］Fleck A C.Isomorphism groups of automata［J］.Journal of the Association for Computing Machinery，1962，9（4）：469-476.

［3］Droste M，Kuich W，Vogler H.Handbook of Weighted Automata［M］.Heidelberg：Springer，2009.

［4］Petkovi? T.Congruence and homomorphisms of fuzzy automata［J］.Fuzzy Sets and Systems，2006，157（3）：444-458.

［5］Li Y M，Pedrycz W.Minimization of lattice finite automata and its application to the decomposition of lattice languages［J］.Fuzzy Sets and Systems，2007，158：1423-1436.

［6］Droste M，Stüber T，Vogler H.Weighted finite automata over strong bimonoids［J］.Information Sciences，2010，180：156-166.

［7］?iri? M，Droste M，Ignjatovi? J，et al.Determinization of weighted finite automata over strong bimonoids［J］.Information Sciences，2010，180：3497-3520.

Congruence and minimization of deterministic weighted finite automata

Tian Jing1，3，Xu Hui2
（1.Economy and Finance School，Xi′an International Studies University，Xi′an710128，China 2.School of Science，Air Force Engineering University，Xi′an710051，China 3.School of science，Xi′an University of Technology，Xi′an710148，China）

The deterministic weighted finite automata over strong bimonoids is studied in the paper.Firstly，the Homomorphism Theorem and the Isomorphism Theorem are given.Secondly，we construct a minimal automaton Aφ.Any recognizor of φ is proved to be isomorphic to Aφfinally.

deterministic weighted automaton，congruence，minimal automaton

O153.3

A

1008-5513（2015）05-0468-06

10.3969/j.issn.1008-5513.2015.05.005

2015-04-12.

國家自然科學(xué)基金（61402364）；陜西省自然科學(xué)基金（2014JQ1014）.

田徑（1979-），博士，講師，研究方向：半群代數(shù)理論，理論計算機科學(xué).

2010 MSC:18B20