论文部分内容阅读
自动机理论是研究离散数字系统的功能、结构及其两者关系的数学理论,它旨在研究自动机的分析与综合问题。分析就是分析一个给定的自动机的功能,综合就是研制一个自动机来实现预定的功能。随着现代科学技术的发展,自动机理论有了深入的发展和广泛的应用,它已经成为许多学科的重要理论和基础。( h, k )阶存贮线性有限自动机是一类典型的、易于实现的线性有限自动机,它的输出由现在时刻的输入和刚过去的h位输入以及k位输出决定[1]。任何一个延迟r步弱可逆线性有限自动机的构造问题都可以归结为延迟r步弱可逆有限阶存贮线性有限自动机的构造问题[2]。对一个给定线性有限自动机,当它满足一定的条件时,它就可以等价嵌入一个有限阶存贮线性有限自动机[27]。这些都说明( h, k )阶存贮线性有限自动机在自动机的研究中具有重要的地位。我国著名学者陶仁骥先生在[1]中提出了拟( h, k )阶存贮线性有限自动机的概念。拟( h, k )阶存贮线性有限自动机的状态变换方式与( h, k )阶存贮线性有限自动机相同,但它的输出仅仅是把当前状态的第一位上的文字输出来,因此它的输出更容易得到和控制。但是人们对这类线性有限自动机研究不多。本文对拟( h, k )阶存贮线性有限自动机这一特殊的自动机的结构进行了一些讨论,并对拟( r , r )阶存贮线性有限自动机的可逆性问题进行了一些讨论,还讨论了如何利用弱可逆拟( r , r)阶存贮线性有限自动机构造前馈可逆有限自动机和前馈逆有限自动机的问题。由此可见对拟( r , r )阶存贮线性有限自动机的研究和讨论具有重要的理论和现实意义。自动机的分解问题涉及到一个复杂自动机如何由一些简单自动机来实现的问题,这是一个自动机技术实现的问题,因此一直被人们所关注[3-11]。本文最后讨论了弱可逆拟( r , r )阶存贮线性有限自动机的分解问题。本文可以分为三个部分,每一部分为一章。第一章是引言。这部分简单介绍了国内外学者利用代数工具对自动机和有限存贮自动机进行研究的一些内容和本文的研究内容,并给出了有限自动机的一些基本概念和记号。第二章是关于拟( h, k )阶存贮线性有限自动机性质的研究。在这一章中,讨论了拟( h, k )阶存贮线性有限自动机的结构矩阵、自由响应矩阵和传输函数矩阵的特点,给出了一个判断拟( r , r )阶存贮线性有限自动机M延迟r步弱可逆的充分必要条件,给出了一个构造弱可逆拟( r , r )阶存贮线性有限自动机M的延迟r步弱逆有限自动机M ’的方法。最后还讨论了如何利用弱可逆拟( r , r )阶存贮线性有限自动机构造延迟r步前馈可逆有限自动机和延迟r步前馈逆有限自动机。主要结果有:定理2.2.1:设M是一个拟( h, k )阶存贮线性有限自动机,由(2.2)式定义,则它的结构矩阵有下面的形式:这里E1 ,E2分别表示GF ( q )上的m×m阶和l×l阶单位矩阵。定理2.3.1:设M是由(2.3)式定义的拟( r ,r)阶存贮线性有限自动机,则M延迟r步弱可逆的充分必要条件为B0的列线性无关。定理2.3.2:设M′=< Y , X , S′,δ′,λ′>是( r , r )阶存贮线性有限自动机,由下式定义:则M′是由(2.3)式定义的延迟r步弱可逆拟( r , r )阶存贮线性有限自动机M的延迟r步弱逆,其中Q是一个m×m阶可逆矩阵。第三章是关于弱可逆拟( r , r )阶存贮线性有限自动机分解问题的研究。这部分首先给出了自动机分解的一些概念,然后研究了弱可逆拟( r , r )阶存贮线性有限自动机的状态的输出权、严格延迟步数等,最后给出了拟( r , r )阶存贮线性有限自动机M弱可逆的充分必要条件是M可以分解为一个延迟0步弱可逆有限自动机M 0和一个延迟r步弱可逆拟(0, r )阶存贮线性有限自动机M 1。主要结果有:定理3.2.1:设M =< X , Y , S ,δ,λ>是拟( r , r )阶存贮线性有限自动机,由(3.1)定义,当M延迟r步弱可逆时,有:(1)对?s∈S,d elay ( s )= r; (2)? s∈S,w r , M =| WrM ,s|= 1。定理3.2.3:设有限自动机M =< X , Y , S ,δ,λ> , X = Y = n> 1。如果存在一个延迟0步弱可逆有限自动机M 0 =< X , X , S 0 ,δ0 ,λ0>和一个由(3.2)式定义的延迟r步弱可逆拟(0, r )阶存贮线性有限自动机M 1 =< X , Y , S1 ,δ1 ,λ1> ,使得M < M 0 ? M1,则:(1)?s∈S, wr , M =| WrM ,s|= 1, | Wr M +1 ,s|= n;(2) ?s∈S, delay ( s )= r。从而M延迟r步弱可逆。定理3.2.6:设M =< X , Y , S ,δ,λ>是一个延迟r步弱可逆拟( r , r )阶存贮线性有限自动机,若X = Y = n> 1,则M可分解为一个延迟0步弱可逆有限自动机M 0和一个延迟r步弱可逆的拟(0, r )阶存贮线性有限自动机M 1,即M < M 0 ? M1。定理3.2.7 :设M =< X , Y , S ,δ,λ>是拟( r , r )阶存贮线性有限自动机,| X |= | Y |= n> 1,则M延迟r步弱可逆的充分必要条件是M < M 0 - M1。其中M 0是一个延迟0步弱可逆有限自动机, M 1是一个延迟r步弱可逆拟(0, r )阶存贮线性有限自动机。