有限自动机的同态  

Homomorphisms of Finite Automata

作　　者：黄飞丹[1] 邓培民[2] 易忠[2] 

机构地区：[1]毕节学院数学系,贵州毕节551700 [2]广西师范大学数学科学学院,桂林541004

出　　处：《工程数学学报》2014年第1期44-56,共13页Chinese Journal of Engineering Mathematics

基　　金：贵州省科技厅;毕节市科技局;毕节学院科技联合基金(黔科合J字LKB[2012]10号);贵州省科学技术基金(2012GZ10526)~~

摘　　要：循环有限自动机是由单个状态生成的有限自动机,任何有限自动机都是有限个循环有限自动机的并.为了进一步探讨循环有限自动机的性质和揭示一般有限自动机和循环有限自动机的关系,本文利用代数的方法,讨论了循环有限自动机的自同态,得出了计算循环有限自动机自同态半群和自同构群的算法;并讨论了一般有限自动机的同态,证明了每一个有限自动机都是有限个循环有限自动机的直和的同态象.A cyclic finite automaton is a finite automaton which is generated by one single state, and each finite automata is the union of some cyclic finite automata. In this paper, in order to further investigate more insightful properties underlying cyclic finite automata and reveal the relationship between general finite automata and cyclic finite automata, by using the algebraic fashion we analyze the endomorphisms of cyclic finite automata, and propose an algorithm for finding the endomorphism semigroup and the automorphism group of a cyclic finite automaton. Moreover, the homomorphisms of general finite automata are discussed, and it is proved that every finite automaton is a homomorphism image of a direct sum of cyclic finite automata.

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

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构]