有限自动机的同态

摘要：

循环有限自动机是由单个状态生成的有限自动机，任何有限自动机都是有限个循环有限自动机的并。为了进一步探讨循环有限自动机的性质和揭示一般有限自动机和循环有限自动机的关系，本文利用代数的方法，讨论了循环有限自动机的自同态，得出了计算循环有限自动机自同态半群和自同构群的算法；并讨论了一般有限自动机的同态，证明了每一个有限自动机都是有限个循环有限自动机的直和的同态象。

关键词：循环有限自动机、同态、自同态、直和

分类号：TP301.1(计算技术、计算机技术)

资助基金：贵州省科技厅、毕节市科技局、毕节学院科技联合基金黔科合J字LKB[2012]10号；贵州省科学技术基金2012GZ10526.@@@@The Science and Technology Joint Foundation of Guizhou Province, Bijie Technology Bureau, and Bijie UniversityGuizhou Branch of J-LKB[2012]10;the Science and Technology Foundation of Guizhou Province of China2012GZ10526

在线出版日期：2014-03-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共13页

页码：44-56