1、文章编号：（）加权有限转换状态机黄飞丹（广东轻工职业技术学院，广东 广州 ）摘要：给出加权有限状态机的概念，定义了可交换的加权有限状态机和加权有限转换状态机，研究了可交换的加权状态机的性质及其等价刻画，并研究加权转换有限状态机的性质。另一方面，给出了两个加权有限状态机同态（强同态）的概念，研究了加权有限状态机的同态性质，并研究两个加权有限状态机在强同态下的可交换性。关键词：加权有限状态机；交换；转换；半环；同态中图分类号：文献标识码：引言自动机是计算机科学理论中的计算模型，用以研究计算机的结构、计算能力等性质。自动机包括很多类型，如经典有限自动机、模糊有限自动机、概率有限自动机、量子有限自动机
2、等。加权有限自动机是一类转移权重取值于半环的非确定型有限自动机，最早由 提出，其研究方法是用代数理论研究有限自动机的一般方法。加权有限自动机可根据权重结构的不同而涵盖多种类型的自动机。目前加权有限自动机的研究已经取得了较为丰富的成果，加权有限自动机的代数性质也得到了研究。文 研究了加权变换半群及其商变换半群的性质，文 研究了加权有限自动机的变换幺半群，文 用加权有限自动机的强同态研究两个加权有穷自动机在计算能力上的等价性，并讨论了加权有限自动机的可交换性、分离性、（强）连通性。交换性是代数学的一个重要概念，文 将交换性概念引入到模糊自动机中，其后模糊自动机的交换性得到了更深入的研究 ，且许多类
3、型的自动机的交换性也得到了研究，如概率有限自动机的交换性、格值有限自动机的交换性 、量子自动机的交换性 、扰动模糊有限自动机的交换性 等。文 引入了加权有限自动机的可交换性的概念。本文只研究加权有限自动机的状态转移结构，称为加权有限状态机，定义了加权有限状态机的交换性、转换性，并研究加权有限状态机的交换性、转换性的相关性质。基本概念和记号定义，设非空集合上有两种运算和，且上有两个特殊的元素和，并满足以下条件：（）（，）是交换的幺半群；第 卷第期 模糊系统与数学 ，年月 ，收稿日期：基金项目：广东轻工职业技术学院校级科研项目（）作者简介：黄飞丹（），女，副教授，研究方向：环，模，自动机理论。（）
4、（，）是幺半群；（），有（）（）（），（）（）（）；（），有，则称（，）为半环（简记为）。特别的，若对任意的，有，则称为交换半环。定义，设是一个半环，在上定义一个二元关系为：（）（），则称为伪序半环。定义，设是一个半环，加权有限自动机是五元组（，），其中为有限状态集，为有限输入字符集，：为权重状态转移函数，与分别代表权值初始状态与权值接受状态。记为上的所有长度有限的字的集合，表示空字符，表示字的长度。权值状态转移函数可以扩展为从到的函数：（，），对，（，），（，）（，）（，）由此定义可得，对任意，有（，）（，）（，）本文只讨论加权有限自动机的状态转移结构，将其称为加权有限状态机。定义设是一个半
5、环，（，）是一个加权有限自动机，称（，）为加权有限状态机。定义设是一个半环，（，）是一个加权有限状态机，若对任意，及，有（，）（，）则称是可交换的。定义设是一个半环，（，）是一个加权有限状态机，若对任意，及，有（，）（，）则称是可转换的。定义设是一个半环，（，）是一个加权有限状态机，若既是可交换的，又是可转换的，则称是加权有限转换状态机。主要结论定理设是一个半环，（，）是一个可交换的加权有限状态机，则对任意的，及，有（，）（，）证明设，及。对的长度用归纳法。当时，则（，）（，）（，）（，）（，）第期黄飞丹：加权有限转换状态机假设结论对长度为的字成立。设，其中，满足，则（，）（，）（，）（，）（
6、，）（，）（，）（，）（，）（，）（，）（，）（，）故结论成立。定理设是一个半环，（，）是一个可交换的加权有限状态机，则对任意的，及，有（，）（，）证明设，及，对，的长度和用双重数学归纳法。由定理知（，）（，）当，时成立，且（，）（，）当，时成立。假设（，）（，）对任意，（，）成立，且（，）（，）对任意，（，）成立。当，时，设，其中，则（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）综合上述，结论成立。定理设是一个交换半环，（，）是一个加权有限转换状态机，则对任意的，模糊系统与数学 年及，有（，）（，）证明设，及，对的长度用归纳法。当时，则（，）（，）（，）（，）
7、假设结论对满足的成立。设，其中，。则（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）故结论对成立，从而结论成立。推论设是一个交换半环，（，）是一个加权有限转换状态机，则对任意的，及，有（，）（，）证明由定理及定理可知结论成立。引理设是一个半环，（，）是一个加权有限状态机。在上定义关系如下：（，）（，）（，）则是上的一个同余关系。的等价类的集合（）对运算 做成一个幺半群。定义设是一个半环，（，）是一个加权有限状态机，。记（），其中（，），。（）称为状态转移矩阵。对，记（）（，）。引理设是一个半环，（，）是一个加权有限状态机，。则对任意，有（）（）（）（）。证明对用归纳法。当时，
8、结论显然成立。假设结论对成立。当时，设，则（）（）（，）（，）（，）（，）（，）（，）（，）（，）（）（）的第行第个元素为（，）（，）（，）而（）的第行第个元素为（，），因此（）（）（）。由归纳假设，有（）（）（）（），故（）（）（）（），因此结论成立。定理设是一个半环，（，）是一个加权有限状态机，则以下命题等价：第期黄飞丹：加权有限转换状态机（）是可交换的；（）对任意，及，有（，）（，）。（）对任意，有（）（）（）（）。（）（）是一个交换的幺半群。证明（）（）：由定理可知。（）（）：设对任意，及，有（，）（，），则（）（）。由引理知（）（）（），（）（）（），故（）（）（）（）。（）（）：，
9、（），由条件（）（）（）（），即（）（），故，有（，）（，），从而 ，即 。因此（）是一个交换的幺半群。（）（）：，由于（）是一个交换的幺半群，故 ，即 ，故（，）（，），因此是可交换的。定义设是一个伪序半环，（，）和（，）是两个加权有限状态机，：和：为映射，称（，）为到的同态映射，记为（，）：，如果对任意的，和，有（，）（），（），（）若对任意的，和，有（），（），（）（，），（）（）则称（，）为到的强同态映射，简称强同态。若（，）是强同态，且，都是满射，则称与同态。若且是恒等映射，则简记：，并相应地称是同态映射或强同态映射。设（，）是到的同态映射（强同态映射），则可将扩展为到的映射：（），
10、（）（）（）（）其中，。引理设是一个伪序半环，若，则。证明设，则存在，使得，从而（）（），即（）（）（）（）故。定理设是一个伪序半环，（，）和（，）是两个加权有限状态机，（，）是到的同态映射且是满射。则对任意，和，有（，）（），（），（）证明设，和。对的长度用归纳法。当时，若，则（，）（，）（），（）（），（），（）若，则（，）（，）（），（）（），（），（）假设结论对满足的一切成立，设，其中，则（，）（，）（，）（，）由归纳假设及题设可知（，）（），（），（），（，）（），（），（）由引理，有模糊系统与数学 年（，）（），（），（）（），（），（）（），（），）（，（），（）（），（）（），
11、（）（），（），（）故结论成立。定理设是一个半环，（，）和（，）是两个加权有限状态机，（，）是到的强同态映射且是满射。则对任意，和，有（），（），（）（）（）（，）证明设，对用归纳法。当时，由（，）是强同态知结论成立。假设结论对满足的成立。设，则（），（），（）（），（），（）（），（）（），（）（），（），）（，（），（）（）（，）（，（），（）（）（，）（，（），（）（）（，）（），（），（）（）（，）（）（）（，）（）（）（）（，）（，）（）（）（）（，）（，）（）（）（，）（，）（）（）（，）（）（）（，）故结论成立。定理设是一个半环，（，）和（，）是两个加权有限状态机，（，）是到的强
12、同态映射且，是满射。若是可交换的，则是可交换的。证明对任意的，和，存在，和，使得（），（），（），（）。由于是可交换的，故（，）（），（），（）（）（）（，）（）（）（，）（），（），（）（），（）（），（）（，）故是可交换的。第期黄飞丹：加权有限转换状态机参考文献：，（）：，（）：，：，（）：，：，：，：王拥兵加权有限自动机及其商变换半群系统科学与数学，（）：王拥兵，李永明加权有限自动机的幺半群陕西师范大学学报（自然科学版），（）：张丽霞加权有穷自动机的代数性质计算机工程与科学，（）：，（）：，（）：谢正卫等 两类模糊有限状态机积的交换性 计算机研究与发展，（）：，：谢正卫概率有限自动机的交换性江苏理工学院学报，（）：黄飞丹，杨京开，邓泽喜格值有限状态机的交换性模糊系统与数学，（）：黄飞丹，李雪佳，武玲玲格值有限状态机的弱交换性模糊系统与数学，（）：黄飞丹，邓泽喜量子自动机的交换性计算机工程与应用，（）：黄飞丹，谢正卫，邓泽喜，杨京开未初始化时序量子机的代数性质工程数学学报，（）：彭家寅扰动模糊有限转换状态机计算机工程与应用，（）：（，）：，（），：；模糊系统与数学 年
