文章编号：１００１－７４０２（２０２３）０３－００３８－０７加权有限转换状态机＊黄飞丹（广东轻工职业技术学院，广东广州５１０３００）摘要：给出加权有限状态机的概念，定义了可交换的加权有限状态机和加权有限转换状态机，研究了可交换的加权状态机的性质及其等价刻画，并研究加权转换有限状态机的性质。另一方面，给出了两个加权有限状态机同态（强同态）的概念，研究了加权有限状态机的同态性质，并研究两个加权有限状态机在强同态下的可交换性。关键词：加权有限状态机；交换；转换；半环；同态中图分类号：ＴＰ３０１文献标识码：Ａ１引言自动机是计算机科学理论中的计算模型，用以研究计算机的结构、计算能力等性质。自动机包括很多类型，如经典有限自动机、模糊有限自动机、概率有限自动机、量子有限自动机等。加权有限自动机是一类转移权重取值于半环的非确定型有限自动机，最早由Ｓｃｈｉｉｔｚｅｎｂｅｒｇｅ［１］提出，其研究方法是用代数理论研究有限自动机的一般方法。加权有限自动机可根据权重结构的不同而涵盖多种类型的自动机。目前加权有限自动机的研究已经取得了较为丰富的成果［２－１１］，加权有限自动机的代数性质也得到了研究［９－１１］。文［９］研究了加权变换半群及其商变换半群的性质，文［１０］研究了加权有限自动机的变换幺半群，文［１１］用加权有限自动机的强同态研究两个加权有穷自动机在计算能力上的等价性，并讨论了加权有限自动机的可交换性、分离性、（强）连通性。交换性是代数学的一个重要概念，文［１２］将交换性概念引入到模糊自动机中，其后模糊自动机的交换性得到了更深入的研究［１３－１５］，且许多类型的自动机的交换性也得到了研究，如概率有限自动机的交换性［１６］、格值有限自动机的交换性［１７－１８］、量子自动机的交换性［１９－２０］、扰动模糊有限自动机的交换性［２１］等。文［１１］引入了加权有限自动机的可交换性的概念。本文只研究加权有限自动机的状态转移结构，称为加权有限状态机，定义了加权有限状态机的交换性、转换性，并研究加权有限状态机的交换性、转换性的相关性质。２基本概念和记号定义２．１［２，９］设非空集合Ｓ上有两种运算⊕和⊗，且Ｓ上有两个特殊的元素０和１，并满足以下条件：（１）（Ｓ，⊕，０）是交换的幺半群；第３７卷第３期模糊系统与数学Ｖｏｌ．３７，Ｎｏ．３２０２３年６月ＦｕｚｚｙＳｙｓｔｅｍｓａｎｄＭａｔｈｅｍａｔｉｃｓ...
