摘要
循环有限自动机是由单个状态生成的有限自动机,任何有限自动机都是有限个循环有限自动机的并.为了进一步探讨循环有限自动机的性质和揭示一般有限自动机和循环有限自动机的关系,本文利用代数的方法,讨论了循环有限自动机的自同态,得出了计算循环有限自动机自同态半群和自同构群的算法;并讨论了一般有限自动机的同态,证明了每一个有限自动机都是有限个循环有限自动机的直和的同态象.
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.
出处
《工程数学学报》
CSCD
北大核心
2014年第1期44-56,共13页
Chinese Journal of Engineering Mathematics
基金
贵州省科技厅
毕节市科技局
毕节学院科技联合基金(黔科合J字LKB[2012]10号)
贵州省科学技术基金(2012GZ10526)~~
关键词
循环有限自动机
同态
自同态
直和
cyclic finite automata
homomorphism
endomorphism
direct sum
