强赋值幺半群上的加权Mealy机与加权Moore机的关系

来源：计算机科学与探索杂志2018年第8期北京时间：

作者：王敏，李永明

单位：陕西师范大学 计算机科学学院，西安 710119

摘要：赋值幺半群是一类包含半环在内的代数结构，在赋值幺半群的基础上定义强赋值幺半群。由于带输出的加权有穷自动机在自然语言的处理方面有很重要的意义，是自动机理论的一个重要研究方向。在权重取值于强赋值幺半群下定义了3种带输出的加权自动机，即强赋值加权序列机、强赋值加权Mealy机以及强赋值加权Moore机，并且给出了它们的响应函数，进而探讨了强赋值加权Mealy机和强赋值加权Moore机的关系，即强赋值加权序列机与强赋值加权Mealy机是不等价的，强赋值加权序列机与强赋值加权Moore机是等价的；并以强赋值加权序列机为中介，强赋值加权Mealy机与强赋值加权Moore机的关系是不等价的。

关键词：强赋值幺半群,强赋值加权序列机,强赋值加权Mealy机,强赋值加权Moore机,等价性