确定权重有限自动机的同余及极小自动机

田径，徐慧

（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