关于输入存贮线性有限自动机和状态机的研究

论文摘要

自动机理论是研究离散数字系统的功能、结构及其两者关系的数学理论。五十年代,在开关网络理论和数理逻辑中图灵机理论的基础上,形成了自动机理论这一数学分支学科。随着科学技术的发展,自动机理论有了深入的发展和广泛的应用,成为许多学科的重要理论和基础。自动机理论中最重要的问题之一是技术实现问题,文献[1]给出了任意的线性有限自动机在一定条件下都可以等价嵌入于一个输入存贮线性有限自动机。也就是说,在一定条件下,任意的线性有限自动机的功能都可以通过输入存贮线性有限自动机来实现。文献[2]证明了任何延迟τ步可逆线性有限自动机都存在τ阶输入存贮线性有限自动机为它的延迟τ步逆。并且,输入存贮线性有限自动机在有限自动机公钥密码体制和数字签名中也有重要的应用[3-12]。而输入存贮线性有限自动机是一类典型的、易于实现的线性有限自动机。所以,我们有必要对输入存贮线性有限自动机进行讨论,以便进一步研究任意的线性有限自动机和为密码学、网络、自动控制、模式识别等而服务。本文从输入存贮线性有限自动机本身出发对其进行研究,剖析了其自身结构,两个输入存贮线性有限自动机作积之后的结构,一个线性有限自动机M具有r阶输入存贮的等价定理。然后应用输入存贮线性有限自动机的结构矩阵讨论了输入存贮线性有限自动机的弱可逆性,得到了h阶输入存贮线性有限自动机延迟0步弱可逆的充要条件、延迟τ步弱可逆和严格延迟τ步弱可逆的充分条件,由这些条件得出了延迟τ步弱可逆和严格延迟τ步弱可逆的h阶输入存贮线性有限自动机新的构造方法、求出延迟0步弱可逆h阶输入存贮线性有限自动机的一个弱逆（这里,τ为任意正整数）。而且还应用输入存贮线性有限自动机的结构矩阵讨论了输入存贮线性有限自动机积的弱可逆性,得出两个h阶输入存贮线性有限自动机作全直积和化合之后延迟0步弱可逆的充分必要条件是这两个h阶输入存贮线性有限自动机本身都是延迟0步弱可逆的。此外,本文应用输入存贮线性有限自动机的线性系数组成的矩阵来研究输入存贮线性有限自动机的极小化问题,得到输入存贮线性有限自动机极小的等价定理,由此定理得出输入存贮线性有限自动机极小化的新方法。对状态自动机来说,与自动机的等价嵌入类似的问题是状态机的覆盖问题。本文还讨论了两个状态机积的变换半群和它们变换半群的积之间的覆盖关系、两个状态机的积之间的覆盖关系、两个变换半群的积之间的覆盖关系、两个状态机的积与覆盖它们的状态机的积之间的覆盖关系、两个变换半群的积与覆盖它们的变换半群的积之间的覆盖关系。本文共分五部分,每部分为一章。第一章:引言。本章主要介绍了输入存贮线性有限自动机在自动机理论中所起的重要作用以及国内外学者应用输入存贮线性有限自动机研究的一些成果,并给出了（输入存贮）线性有限自动机的一些概念与记号。第二章:输入存贮线性有限自动机积的讨论。本章通过讨论得出输入存贮线性有限自动机本身结构矩阵的特点、两个输入存贮线性有限自动机作积之后仍然是输入存贮线性有限自动机,还讨论了两个输入存贮线性有限自动机作积之后的结构矩阵、自由响应生成矩阵、传输函数矩阵和原来两个输入存贮线性有限自动机的结构矩阵、自由响应生成矩阵、传输函数矩阵的关系。而且还通过讨论得出一个线性有限自动机M具有r阶输入存贮的等价定理。主要结论有:定理2.2.4设M是GF （ q ）上输入、输出维数分别为l ,m的h阶输入存贮线性有限自动机,由下式定义: ,其中B′j为GF （ q ）上m×l阶矩阵。则M的结构矩阵A,B ,C ,D分别为:这里, 0l ,l表示l×l阶零阵, Ei ,l表示第i个l阶单位阵, El表示l阶单位阵, i = 1,…, h-1.定理2.2.10设M是GF （ q ）上线性有限自动机,则M具有r阶输入存贮性? M等价于M 1与Mα的后并,其中M 1是一个r阶输入存贮线性有限自动机,Mα是一个具有r阶输入存贮性的自治的线性有限自动机。定理2.2.15设M = （ X , Y , S ,δ,λ） , M′= （Y , Y′, S′,δ′,λ′）是两个h阶输入存贮线性有限自动机,则M·M′= （ X , Y′, S×S′, （δ|—）,（λ|—））是2h阶输入存贮线性有限自动机。第三章:输入存贮线性有限自动机的弱可逆性。本章应用输入存贮线性有限自动机的结构矩阵来讨论输入存贮线性有限自动机的弱可逆性,得到h阶输入存贮线性有限自动机延迟0步弱可逆的充要条件、延迟τ步弱可逆和严格延迟τ步弱可逆的充分条件,由这些条件得出延迟τ步弱可逆和严格延迟τ步弱可逆的h阶输入存贮线性有限自动机新的构造方法、求出延迟0步弱可逆输入存贮线性有限自动机的一个弱逆。而且还应用输入存贮线性有限自动机的结构矩阵讨论了输入存贮线性有限自动机积的弱可逆性,得出两个h阶输入存贮线性有限自动机作全直积和化合之后延迟0步弱可逆的充分必要条件是这两个输入存贮线性有限自动机本身都是延迟0步弱可逆的。这里,τ、h为任意的正整数。主要结论有:定理3.2.2设M是GF （ q ）上h阶输入存贮线性有限自动机,由下式定义:（1）M延迟0步弱可逆? M的结构矩阵D列线性无关。（2）当1≤τ≤h时,若Bj= 0, j = 0,1,τ- 1,则M严格延迟τ步弱可逆（?） Bτ列线性无关。推论3.2.3设M是GF （ q ）上h阶输入存贮线性有限自动机,由下式定义:（1）如果B0列线性无关,则M延迟τ步弱可逆。τ为任意非负整数。构造3.3.1由定理3.2.2的方法,我们可以构造出GF （ q ）上严格延迟τ步弱可逆的h阶输入存贮线性有限自动机M .方法如下:设M由下式定义: ,其中Bj为GF （ q ）上m×l阶矩阵。令B0 = B1 =…= Bτ-1 = 0,Bτ为GF （ q ）上列线性无关的m×l阶矩阵,Bτ+1 ,…, Bh为GF （ q）上任意的m×l阶矩阵,则这样定义的M为严格延迟τ步弱可逆的h阶输入存贮线性有限自动机。这里,1≤τ≤h.构造3.3.2由推论3.2.3（1）的方法,我们可以构造出GF （ q ）上延迟τ步弱可逆的h阶输入存贮线性有限自动机M .方法如下:设M由下式定义: ,其中Bj为GF （ q ）上m×l阶矩阵。令B0为GF （ q ）上列线性无关的m×l阶矩阵, B1 , B2 ,…, Bh为GF （ q ）上任意的m×l矩阵,则这样定义的M为延迟τ步弱可逆的h阶输入存贮线性有限自动机。这里,τ为任意非负整数。定理3.4.1设M = （ X , Y , S ,δ,λ）是GF （ q ）上h阶输入存贮线性有限自动机,由下式定义:若M延迟0步弱可逆,则存在（0,4）阶存贮线性有限自动机M′= （Y , X , S′,δ′,λ′）为M的延迟0步弱逆。M′由下式定义:这里:P为B0的左逆矩阵。定理3.5.1设M = （ X , Y , S ,δ,λ）, M′= （ X′, Y′, S′,δ′,λ′）为GF （ q ）上两个h阶输入存贮线性有限自动机,分别由以下两式定义:若M和M′都延迟0步弱可逆,则M和M′的全M×M′= （X×X′, Y×Y′, S×S′,δ×δ′,λ×λ′）延迟0步弱可逆。定理3.5.2设M = （ X , Y , S ,δ,λ） , M′= （Y , Y′, S′,δ′,λ′）是GF （ q ）上两个h阶输入存贮线性有限自动机, M的输入、输出维数分别为l、m ,M′的输入、输出维数分别为m、m′, M和M′分别由以下两式定义:若M和M′都延迟0步弱可逆,则M和M′的化合M ? M′= （ X , Y′, S×S′,δ,λ）延迟0步弱可逆。第四章:输入存贮线性有限自动机的极小化。本章用新的方法得出输入存贮线性有限自动机极小的等价定理,由此定理得出输入存贮线性有限自动机极小化的新方法。主要结论有:定理4.2.8设M = （ X , Y , S ,δ,λ）是GF （ q ）上h阶输入存贮线性有限自动机,由下式定义: ,则M极小（?） U的列在GF （ q ）上线性无关。这里,U为M的线性系数组成的矩阵,定理4.2.11设M = （ X , Y , S ,δ,λ）是GF （ q ）上h阶输入存贮线性有限自动机,由下式定义:M的结构矩阵为A , B ,C , D .设U的j1 ,…, jr列是它的GF （ q ）上极大线性无关列,这些列组成矩阵U1,且U = U1T,T是GF （ q ）上r×n矩阵。设M1是GF （ q ）上线性有限自动机,结构矩阵为A1 = TA′, B1 = TB , C1 = C′,D1 = D.其中A′,C′分别为A和C的第j1 ,…, jr列组成的矩阵。则有M～M1且M 1极小。第五章:状态机和变换半群积的覆盖关系。本章讨论了两个状态机积的变换半群和它们变换半群的积之间的覆盖关系、两个状态机的积之间的覆盖关系、两个变换半群的积之间的覆盖关系、两个状态机的积与覆盖它们的状态机的积之间的覆盖关系、两个变换半群的积与覆盖它们的变换半群的积之间的覆盖关系。主要结论有:定理5.2.4设M =（Q ,∑, F ）, M′= （Q′,∑′, F′）是两个状态机,则（1） TS （ M∧M′） = TS （ M ）∧TS（M′）,对半群满同态θ:∑+→S ,θ′:∑+→S′成立。这里θ（α） = [α],θ′（α） = [α]′.（3） TS （ M（?）M′）≤TS （ M ）（?） TS（M′）定理5.2.3设M =（Q ,∑, F ）, M′= （Q′,∑′, F′）是两个状态机,则（1） M∧M′≤M×M′（2） M×M′≤M（?） M′（3） MωM′≤M（?） M′定理5.2.6设Mi=（Qi,∑i , Fi ）, Mi′= （Qi′,∑i′, Fi′）, i=1,2是状态机.若M1≤M1′, M2≤M2′,则（1） M1×M2≤M1′×M2′（2） M1（?）M2≤M1′（?） M2′（3） M1ωM2≤M1′ωM2′

论文目录

• 中文摘要
• 英文摘要
• 第一章 引言
• 1.1 研究背景及我的研究成果
• 1.2 基本概念和记号
• 第二章 输入存贮线性有限自动机积的讨论
• 2.1 基本概念和记号
• 2.2 关于输入存贮线性有限自动机积的一些结果
• 第三章 输入存贮线性有限自动机的弱可逆性
• 3.1 基本概念和记号
• 3.2 延迟τ步弱可逆h阶输入存贮线性有限自动机的判别
• 3.3 延迟τ步弱可逆h阶输入存贮线性有限自动机的构造
• 3.4 延迟0 步弱可逆h阶输入存贮线性有限自动机的求弱逆
• 3.5 输入存贮线性有限自动机积的弱可逆性
• 第四章 输入存贮线性有限自动机的极小化
• 4.1 基本概念和记号
• 4.2 关于输入存贮线性有限自动机极小的判定和极小化的方法
• 第五章 状态机和变换半群积的覆盖关系
• 5.1 基本概念和记号
• 5.2 关于状态机和变换半群积的覆盖关系的一些结果
• 结束语
• 参考文献
• 读硕期间发表的论文目录
• 致谢