论文部分内容阅读
自动机理论是研究离散数字系统的功能、结构及两者关系的数学理论.它旨在研究自动机的分析与综合问题.有限自动机是自动机理论的一个分支,随着数字计算机,数字通信和自动化等科学技术的出现和发展,自动机理论在理论和实践中发挥着越来越重要的作用.本文讨论循环有限自动机的(弱)可逆性及分解;以代数为工具,对循环有限自动机的代数性质进行研究;并讨论有限自动机的路代数的代数性质与有限自动机性质的关系.本文分为五部分,前四部分中每个部分为一章,最后部分为结束语.第一章为引言.这部分简单介绍了有限自动机的应用,阐述了本文的思路和主要内容并对有限自动机的基本概念和记号做了介绍.第二章讨论循环有限自动机的(弱)可逆性及分解.主要结果有:定理2.1.1设M =< X ,Y, S,δ,λ>是一个循环有限自动机,s∈S 0为M的生成子,则M是弱可逆的当且仅当0 s是弱可逆的.定理2.2.2设M =< X,Y, S,δ,λ>为由s∈S 0生成的延迟τ步WIFA,| X |=|Y|=n>1,则M可分解为一个延迟0步WIFA和个τ阶延迟元当且仅当第三章讨论了循环有限自动机的自同态和有限自动机同态的性质,得出了计算循环有限自动机自同态半群和自同构群的算法,并证明了每一个有限自动机都是有限个循环有限自动机直和的同态象.主要结果有:定理3.1.1设M=<X,Y,S,δ,λ>是以s0为生成子的循环有限自动机, 0π为X*关于0 s的右同余,则定理3.1.3的每一个自同态为中的元素对的左乘变换;反之,每一个中的元素对的左乘变换都是的自同态.即定理3.1.4有限自动机的自同构为中的元素对的左乘变换;反之,中的元素对的左乘变换为的自同构.定理3.2.4任意有限自动机都是有限个循环有限自动机直和的同态象.第四章讨论了有限自动机的性质与其路代数的代数性质之间的关系.主要结果有:定理4.2.1设M1 =< X , Y , S1 ,δ1 ,λ1>为M =< X , Y , S ,δ,λ>的子有限自动机,则(ⅰ) 1F (ΔM)是F (ΔM)的理想当且仅当M1是M的直和项或M1= M;(ⅱ) 1F (ΔM)是F (ΔM)的子代数当且仅当M1= M.定理4.3.1设M =< X , Y , S ,δ,λ>是一个有限自动机,则(ⅰ) M延迟τ步弱可逆当且仅当( )1MIΔτ= Jτ+;(ⅱ) M延迟τ(≥1)步弱可逆当且仅当( )MIΔτ为F (ΔM)的τ+ 1阶关系理想;(ⅲ) M严格延迟τ(≥1)步弱可逆当且仅当( )MIΔτ是F (ΔM)的τ+ 1阶关系理想,但( 1)MIΔτ(?)不是F (ΔM)的τ阶关系理想;(ⅳ) M延迟τ步弱可逆当且仅当( ) ( )MFMΔIΔτ为n (lτ+ + l+ 1)维代数,其中| S |= n, | X |= l.定理4.3.5设M =< X , Y , S ,δ,λ>为延迟τ(≥1)步弱可逆有限自动机,| X |= | Y|> 1,则M可分解为一个延迟0步弱可逆有限自动机与一个τ阶延迟元的化合当且仅当( 1)MIΔ′′τ(?) = Jτ.定理4.4.1设M i =< X i , Yi , S i ,δi ,λi>为有限自动机, i = 1,2.则全直积M1×M2的路代数1 2F (ΔM×M)和1F (ΔM)与2F (ΔM)的张量积1 2F (ΔM ) (?) F(ΔM)的一个子代数同构.定理4.4.2设M1 =< X , Y , S1 ,δ1 ,λ1>和M2 =< Y , Z , S2 ,δ2 ,λ2>为有限自动机,则M1 M2的路代数1 2F (ΔM M)与1 2F (ΔM ) (?) F(ΔM)的一个子代数同构.定理4.4.3设M1 =< X , Y , S1 ,δ-1 ,λ1>和M2 =< Y , Z , S2 ,δ2 ,λ2>为有限自动机, M1延迟τ1步弱可逆, M2延迟τ2步弱可逆,则存在1 2F (ΔM ) (?) F(ΔM)的子代数A ,使得A ( rad ( A) )τ1 +τ2 +1为1 2mn (lτ+τ+ + l+ 1)维代数,其中| S1 |= n, | S 2|= m, | X |= l.最后部分为结束语,总结了本文的主要工作并阐述了今后的工作.