论文摘要
自动机理论是研究离散数字系统的功能、结构及其两者关系的数学理论.它旨在研究自动机的分析与综合问题.有限自动机是自动机理论的一个分支,它在计算机、自动控制等领域都有良好的应用.有限自动机分解是与有限自动机公开钥密码体制（FAPKC）中的有限自动机合成相对应的一个概念.讨论有限自动机分解可以实现有限自动机的简化,可以更好地了解有限自动机的结构、性质、功能,并能够促进FAPKC密码体制的不断完善.本文从输出权的角度讨论弱可逆有限自动机的一种分解形式,并且得到这种分解在线性情形下的具体形式和判别方法;以及讨论了一般的弱可逆有限自动机可以分解出有限阶延迟元的情况.本文分为五部分,前面四部分中每个部分为一章,最后部分为结束语.第一章为引言.这部分简单介绍了有限自动机和有限自动机公开钥密码体制的概况,列举了关于弱可逆有限自动机分解的当前主要结果,阐述了本文的思路和主要结论,另外对本文的基本概念和记号也做了介绍.第二章讨论了一般的弱可逆有限自动机（不一定是n元有限自动机）可以分解出有限阶延迟元的一个充要条件.主要结果有:定理2.1对于WIFA M = <X , Y , S ,δ,λ>, X≥2,且存在正整数k 0满足: （?）s∈S.记delayM （ s ）= ms, （?）s∈S.则存在弱可逆有限自动机M1 = <X , Y , S ,δ1,λ1>满足: delayM1 （ s ）= ms - k0, （?）s∈S.定理2.4设延迟τ步WIFA M = <X , Y , S ,δ,λ>和正整数k 0,其中X≥2,则M可以分解成延迟τ- k0步WIFA M1和k0阶延迟元Mk0,d的充要条件是:对于M的任意状态s有第三章讨论一般的弱可逆有限自动机的一种分解形式.主要结果有:定理3.1对于延迟τ步WIFA M = <Ul , Um , Un, （δ|—） ,（λ|—）> ,U是有限集,|U| = q,若对（?）s∈Un其中r∈N+:0< r < m,则（1）当l = m - r时, （M|—）延迟0步弱可逆;（2）当l > m - r时, （M|—）严格延迟τ步弱可逆,且每一状态的延迟步数为τ.定理3.3对于延迟τ（τ>0）步WIFA （M|—） = <Um , Um , Un, （δ|—） ,（λ|—）>,U是有限集, |U| = q,r∈N+:0< r < m,则（M|—）可以分解成延迟0步弱可逆有限自动机M 0和Dτ,r的充要条件是:对（?）s∈Un有定理3.4设有限自动机（M|—） = <Ul , Um , Un, （δ|—） ,（λ|—）>延迟τ步弱可逆,其中U为有限集且U = q, r∈N+:0< r < m, k0∈N+.则（M|—）可以分解成延迟τ步弱可逆有限自动机M和k0个Dr的充要条件是:对（?）s∈Un有第四章讨论了在线性情形下上述分解具体是什么样的形式以及相关的一个判别方法.主要结果有:定理4.1.1设有限自动机M = < X , Y , S ,δ,λ>与有限自动机（M|—） = < X , Y , S,δ,λ>弱同构,有限自动机M1 = < X , Y1 , S1,δ1,λ1>与M2 = <Y1 , Y2 , S2,δ2,λ2>满足: M （?） C （ M1 , M2）,则存在有限自动机（M1|—）与（M2|—）使得: （M1|—）与M1弱同构, （M2|—）与M2弱同构,且（M|—） （?） C （ （M1|—） , （M2|—））.定理4.2.2对于有限域F = GF （ q）上的LFA M = < X , Y , S ,δ,λ>,线性空间X、Y、S的维数分别为l、m、n, r∈N+:0< r < m,则下面两个命题等价:（1）存在Y的一组基{（β1|—） , （β2|—）,…, （βm|—）}中的m - r个元素生成的子空间V满足: （?）s∈S,①②（?）y1y2…yτ, y1’ y2’…yτ’∈WM,sτ, yi - yi’∈V, i = 1,2, ,τ;（2）存在X的一组基{α1,α2,…,αl}, Y的一组基{β1,β2,…,βm}, S的一组基{γ1,γ2,…,γn}, M在这三组基下的结构矩阵为A , B , C , D ,定义FA M = ? F l , F m , F n,δ,λ? : （?）z∈Fn, （?）x∈Fl, （δ|—）（ z , x ）= Az + Bx, （λ|—） （ z , x ）= Cz + Dx.使得M满足:对于?z∈Fn有定理4.2.4设有限域F = GF （ q）上的延迟τ（τ> 0）步WILFA M = < X , Y , S,δ,λ> ,线性空间X、Y、S的维数分别为l、m、n,l = m, r∈N+:0< r < m,则M可以分解成延迟0步WILFA M0与LFA MD的充要条件是:存在Y的一个m - r维子空间V满足:①②（?）y1y2yτ, y1’ y2’ yτ’∈WM,sτ, yi - yi ’∈V, i = 1,2,…,τ,对（?）s∈S.定理4.2.5设LFA M = <X , Y , S ,δ,λ>,线性空间X、Y、S的维数分别为l、m、n, r∈N+:0< r < m,则Y存在一个m - r维子空间V满足: （?）s∈S, （?）y1y2…yτ, y1’ y2’ yτ’∈Wτ,sM , yi - yi’∈V（i = 1,2,…,τ）,当且仅当M存在一组结构矩阵为A,B ,C ,D满足:秩r ([CAτ- 2 B , CAτ-3B ,…, CAB , CB , D])≤m - r.最后部分为结束语,总结了本文的主要工作,阐述了这些工作的意义以及今后的工作.