確定權重有限自動機的同余及極小自動機

田徑，徐慧

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

確定權重有限自動機的同余及極小自動機

田徑1，3，徐慧2

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

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

確定權重自動機；同余；極小自動機

1　引言

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

2　預備知識

本節將給出本文用到的基本概念.

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

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

設A=（Q，δ，σ，τ）是關于Σ和K上的權重有限自動機.若對任意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］.

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

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

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

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

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

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

3　確定權重有限自動機上的同余和同態

設A=（Q，δ，q0，τ），ρ是Q上的等價關系.設p，q∈Q，x∈Σ，若

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

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

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

定義τρ：Qρ→K為

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

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

定義3.1［4］設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′的同態.若同態φ是滿（單）的，則稱之為滿（單）同態.若同態φ既是滿的也是單的，則稱之為同構映射，此時稱A和A′是同構的，記作A?A′.

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

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

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

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

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

定理3.2（同構定理）設A=（Q，δ，q0，τ），A′=（Q′，δ′，q′0，τ′）.若α：Q→Q′是A到A′的同態，則

證明顯然α：Q→α（Q）是A到α（A）的滿同態.根據定理1知存在單同態

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

4　確定權重有限自動機的極小化

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

設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］.

設A=（Q，δ，q0，τ），定義Q上的等價關系π如下：

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

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

設φ∈Σ?，定義Σ?上的等價關系ρφ如下：

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

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

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

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

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

即

從而

故

這樣就證明了

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

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

定理4.2設φ∈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.

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

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

2010 MSC:18B20