有限自动机的同步序列和UIO序列

作     者：谢正卫 

作者单位：广西师范大学 

学位级别：硕士

导师姓名：邓培民;易忠

授予年度：2006年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：(线性)有限自动机 同步序列 UIO序列 积运算 算法 

摘      要：自动机理论是研究离散数字系统的功能、结构及其两者关系的数学理论.随着科学技术的发展,自动机理论有了深入的发展和广泛的应用,成为许多学科的重要理论和基础. 目前,根据自动机应用的情况,主要集中在线性有限自动机和自动机建模上.本文简单介绍了国内外学者利用代数工具对(线性)有限自动机理论进行研究得到的一些结果,对线性有限自动机的同步序列进行了研究,对线性有限自动机的UIO序列进行了研究,同时还对有限自动机积的同步序列和UIO序列进行了讨论. 本文分为四个部分,每部分为一章. 第一章是引言.这部分简单介绍了国内外学者利用代数工具对(线性)有限自动机理论进行研究的一些内容,并给出了(线性)有限自动机的基本概念与记号. 第二章讨论了线性有限自动机的同步序列,给出了线性有限自动机有同步序列的充要条件,还讨论了一类输入存贮线性有限自动机及可等价嵌入输入存贮线性有限自动机的极小线性有限自动机的同步序列.最后给出了判断线性有限自动机有无同步序列以及有求线性有限自动机(最短)同步序列的一些算法.主要结果有: 定理2.2. 7设M =是GF ( q )上线性有限自动机,向量空间S的维数为n,则下列条件等价. (1) M有同步序列 (2) S = {0 s} (3) (?)s∈S(i= 1,2, , n)有δ( s ,0 x n) = 0s,其中s , s, , s为向量空间S的基. 定理2.2.11设M =是GF ( q )上线性有限自动机.若M有同步序列,则M的最短同步序列的长度不超过n,其中n为向量空间S的维数. 定理2.2.12设M =是GF ( q )上线性有限自动机,若S k = {0 s}, { }S k ?1≠0s则X ?上任何长度大于等于k的输入序列都是M的同步序列,任何长度小k的输入序列都不是M的同步序列,从而M的最短同步序列为X?上所有长度