矩阵模型在有限自动机上的应用

论文摘要

自动机理论[1 ]是研究离散数字系统的功能、结构及两者关系的数学理论,随着数字计算机、数字通信及自动化等新技术的出现和发展,自动机理论已成为许多学科的重要理论和应用基础.有限自动机理论是自动机理论的一个重要分支,它在控制理论、对象程序测试、神经网络、保密学等众多学科中有着重要的作用,因此探索有限自动机研究的新方法对有限自动的发展有着重要意义.文献[4]在文献[9],[10],[11]的基础上讨论建立一般有限自动机的矩阵模型,对有限自动机M ? I , O , S ,δ,λ,直接从状态流程表出发,而不是依赖线路的结构函数,通过引入I （M的输入集）、O（M的输出集）和S （M的状态集）的布尔量表示X ,Z和Q,将δ（M的状态转移函数）和λ（M的输出函数）换用矩阵形式的映射方程Q = B （ x ）×Q和Z = A（ x ）×Q描述,从而得到M的矩阵模型表示: x∈X.其中B （ x ）和A（ x ）分别称为M的状态映射矩阵和输出映射矩阵.文献[5],[6]在这个矩阵模型表示方法的基础上,继续采用矩阵理论和布尔代数为工具进行研究,不仅给出了无输出情形的特殊有限自动机（状态自动机）基本代数性质及相应的物理意义,还给出了一种有限自动机极小化的新方法。这些方法有利于算法设计和计算机自动处理,也促进了有限自动机的研究和发展.本文在文献[4],[5],[6]的基础上,继续采用矩阵理论和布尔代数为工具,对有限自动机的另外一些性质做了进一步的讨论,所得的结果不仅有利于有限自动机的理论在计算机中的应用,也表明了矩阵模型方法在有限自动机应用研究中有着重要的作用.主要结论有:1在有限自动机的矩阵模型方法表示的基础上,对有限自动机的弱可逆性进行讨论,然后给出了判断有限自动机和线性有限自动机是否具有弱可逆性的算法.2在运用矩阵模型方法研究试验序列的基础上,构造出了求一个极小线性有限自动机的最短初态试验序列的算法,一个输入序列是（线性）有限自动机的同步序列的充要条件，并且构造出了判断一个线性有限自动机是否有同步序列的算法.3利用矩阵模型方法对两个有限自动机的限制直积进行讨论，在此基础上构造了限制直积的状态映射矩阵和输出映射矩阵，并进行了研究，得出了它们的一些性质:关于状态转移函数运算的两个结果和输出函数的两个结果.4利用矩阵模型对两个有限自动机的级联积进行了讨论，在此基础上构造了级联积的状态映射矩阵和输出映射矩阵，并进行了研究，得出了它们的一些性质:级联积的映射矩阵的一些性质,级联积的状态转移函数运算的两个结果,级联积的输出函数的一些性质及其运算的两个结果.全文共分为五章:第一章介绍了自动机理论的背景以及用矩阵模型方法研究自动机的现状,同时给出了有限自动机以及矩阵模型的一些基本概念和记号.第二章应用矩阵模型方法在有限自动机弱可逆上,所得的结果可以判断有限自动机和线性有限自动机是否具有弱可逆性,若具有弱可逆性,延迟几步弱可逆.主要结果有：定理2.2.4:设M? I,O,S,δ,λ是线性有限自动机，矩阵模型为：，x∈X，则M延迟τ步弱可逆的充分必要条件是：对任意1 0 x（≠x），若存在2x , ,x Xτ??∈，使得1 1 （ ） （ ） （ ） h h A x B x B x ?××??×（1≤h≤τ）的第一列的第一个元素为1，若此时1 B（x） B（x）τ×??×的第一列的不为零的元素为第k行，则1 （ ） 0 k a x = .第三章应用矩阵模型方法在试验序列上,所得的结果可以求一个极小线性有限自动机的最短初态试验序列，并且判断一个输入序列是否是（线性）有限自动机的同步序列，若一个线性有限自动机有同步序列,利用所得的结果可以求出最短同步序列.主要结果有：定理3.2.1：设M? I,O,S,δ,λ是有限自动机，I，O和S的布尔量表示为X , Z和Q，矩阵模型为：，x∈X，则1 kα=x ??x∈X?是M的同步序列的充分必要条件为1 （ ） （ ） k Bx×??×Bx的行秩为1.是线性有限自动机,矩阵模型为:则长为k的输入序列是M的同步序列的充分必要条件（其余行的元素均为零）.第四章应用矩阵模型方法在限制直积上，构造出了限制直积的状态映射矩阵和输出映射矩阵，并对它们的一些性质进行了研究，给出所获得结果.主要结果有:.的第（i一l）m+j列为（*）.其中（*）为:（其余元素均为（0,0））第五章应用矩阵模型方法在有限自动机的级联积上,构造出了级联积的状态映射矩阵和输出映射矩阵，并对它们进行了研究,给出所获得结果.主要结果有：定理5.2.2其余的元素为（1, 0）或（0,0）).定理5.4.2 ?的最后一位输出为h Z的充分必要条件为的第（i?1）m+j列为为第h行，其余的素为（1, 0）或（0,0）).

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 研究背景
• 1.2 预备知识
• 第二章 矩阵模型在有限自动机弱可逆上的应用
• 2.1 预备知识
• 2.2 有限自动机弱可逆性的判定
• 第三章 矩阵模型在试验序列上的应用
• 3.1 矩阵模型在初态试验序列上的应用
• 3.2 矩阵模型在同步序列上的应用
• 3.3 关于极小线性有限自动机的初态试验序列的一个结果
• 第四章 矩阵模型在有限自动机的限制直积上的应用
• 4.1 矩阵模型在限制直积上的应用
• 4.2 关于限制直积的状态转移函数运算的两个结果
• 4.3 关于限制直积的输出函数的两个结果
• 第五章 矩阵模型在有限自动机的级联积上的应用
• 5.1 级联积的映射矩阵的一些性质
• 5.2 关于级联积的状态转移函数运算的两个结果
• 5.3 关于级联积的输出函数的一些性质
• 5.4 关于级联积的输出函数运算的两个结果
• 后记
• 参考文献
• 致谢