循环有限自动机和有限自动机的路代数

摘要

自动机理论是研究离散数字系统的功能、结构及两者关系的数学理论．它旨在研究自动机的分析与综合问题．有限自动机是自动机理论的一个分支，随着数字计算机，数字通信和自动化等科学技术的出现和发展，自动机理论在理论和实践中发挥着越来越重要的作用． 本文讨论循环有限自动机的（弱）可逆性及分解；以代数为工具，对循环有限自动机的代数性质进行研究；并讨论有限自动机的路代数的代数性质与有限自动机性质的关系． 本文分为五部分，前四部分中每个部分为一章，最后部分为结束语. 第一章为引言．这部分简单介绍了有限自动机的应用，阐述了本文的思路和主要内容并对有限自动机的基本概念和记号做了介绍． 第二章讨论循环有限自动机的（弱）可逆性及分解．主要结果有： 定理2.1.1 设M=是一个循环有限自动机，S0 ∈S为M的生成子，则M 是弱可逆的当且仅当S0是弱可逆的． 定理2.2.2 设M=为由S0 ∈S生成的延迟τ步WIFA,WIFA|X|=|Y|=n=>1，则M 可分解为一个延迟0 步WIFA和个τ阶延迟元当且仅当|WMτ,S0|=1． 第三章讨论了循环有限自动机的自同态和有限自动机同态的性质，得出了计算循环有限自动机自同态半群和自同构群的算法,并证明了每一个有限自动机都是有限个循环有限自动机直和的同态象．主要结果有： 定理3.1.1 设M=是以S0为生成子的循环有限自动机，π0为X关于S0的右同余,则M=M(X/π0)． 定理3.1.3M=M(X/π0)的每一个自同态为φ(a0)中的元素对X/π0的左乘变换；反之,每一个φ(a0)中的元素对X/π0的左乘变换都是X/π0的自同态.