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

田徑，徐慧

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

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

田徑1，3，徐慧2

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

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

確定權(quán)重自動(dòng)機(jī)；同余；極小自動(dòng)機(jī)

1　引言

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

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

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

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

定義2.1［6］設(shè)Σ是有限字母表，（K，+，·，0，1）是強(qiáng)雙幺半群，稱四元組A=（Q，δ，σ，τ）是關(guān)于Σ和K上的權(quán)重有限自動(dòng)機(jī)，其中：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)重有限自動(dòng)機(jī).若對(duì)任意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］.

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

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

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

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

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

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

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

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

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

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

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

定義τρ：Qρ→K為

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

設(shè)Aρ=（Qρ，δρ，［q0］ρ，τρ）是A關(guān)于ρ的權(quán)重商自動(dòng)機(jī).引理1表明δρ可以擴(kuò)張成δρ：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)映射，此時(shí)稱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α）?的一個(gè)同態(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)重有限自動(dòng)機(jī)的極小化

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

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

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

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

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

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

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

作為文獻(xiàn)［2］中定理3.2的一個(gè)推廣，我們有

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

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

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

即

從而

故

這樣就證明了

定理4.1若φ是K-正則的，則Aφ=（Qφ，δφ，φ，τφ）是識(shí)別φ的極小自動(dòng)機(jī).

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

定理4.2設(shè)φ∈K〈〈Σ?〉〉，‖A‖=φ.若A是可達(dá)約簡的，則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ù)理論，理論計(jì)算機(jī)科學(xué).

2010 MSC:18B20