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

摘要

自动机理论是研究离散数字系统的功能、结构及其两者关系的数学理论。五十年代，在开关网络理论和数理逻辑中图灵机理论的基础上，形成了自动机理论这一数学分支学科。随着科学技术的发展，自动机理论有了深入的发展和广泛的应用，成为许多学科的重要理论和基础。自动机理论中最重要的问题之一是技术实现问题，文献[1]给出了任意的线性有限自动机在一定条件下都可以等价嵌入于一个输入存贮线性有限自动机。也就是说，在一定条件下，任意的线性有限自动机的功能都可以通过输入存贮线性有限自动机来实现。文献[2]证明了任何延迟步可逆线性有限自动机都存在阶输入存贮线性有限自动机为它的延迟步逆。并且，输入存贮线性有限自动机在有限自动机公钥密码体制和数字签名中也有重要的应用[3-12]。而输入存贮线性有限自动机是一类典型的、易于实现的线性有限自动机。所以，我们有必要对输入存贮线性有限自动机进行讨论，以便进一步研究任意的线性有限自动机和为密码学、网络、自动控制、模式识别等而服务。 本文从输入存贮线性有限自动机本身出发对其进行研究，剖析了其自身结构，两个输入存贮线性有限自动机作积之后的结构，一个线性有限自动机具有阶输入存贮的等价定理。然后应用输入存贮线性有限自动机的结构矩阵讨论了输入存贮线性有限自动机的弱可逆性，得到了阶输入存贮线性有限自动机延迟0步弱可逆的充要条件、延迟步弱可逆和严格延迟步弱可逆的充分条件，由这些条件得出了延迟步弱可逆和严格延迟步弱可逆的阶输入存贮线性有限自动机新的构造方法、求出延迟0步弱可逆阶输入存贮线性有限自动机的一个弱逆（这里，为任意正整数）。而且还应用输入存贮线性有限自动机的结构矩阵讨论了输入存贮线性有限自动机积的弱可逆性，得出两个阶输入存贮线性有限自动机作全直积和化合之后延迟0步弱可逆的充分必要条件是这两个阶输入存贮线性有限自动机本身都是延迟0步弱可逆的。此外，本文应用输入存贮线性有限自动机的线性系数组成的矩阵来研究输入存贮线性有限自动机的极小化问题，得到输入存贮线性有限自动机极小的等价定理，由此定理得出输入存贮线性有限自动机极小化的新方法。对状态自动机来说，与自动机的等价嵌入类似的问题是状态机的覆盖问题。本文还讨论了两个状态机积的变换半群和它们变换半群的积之间的覆盖关系、两个状态机的积之间的覆盖关系、两个变换半群的积之间的覆盖关系、两个状态机的积与覆盖它们的状态机的积之间的覆盖关系、两个变换半群的积与覆盖它们的变换半群的积之间的覆盖关系。本文共分五部分。 第一章：引言。本章主要介绍了输入存贮线性有限自动机在自动机理论中所起的重要作用以及国内外学者应用输入存贮线性有限自动机研究的一些成果，并给出了（输入存贮）线性有限自动机的一些概念与记号。 第二章：输入存贮线性有限自动机积的讨论。本章通过讨论得出输入存贮线性有限自动机本身结构矩阵的特点、两个输入存贮线性有限自动机作积之后仍然是输入存贮线性有限自动机，还讨论了两个输入存贮线性有限自动机作积之后的结构矩阵、自由响应生成矩阵、传输函数矩阵和原来两个输入存贮线性有限自动机的结构矩阵、自由响应生成矩阵、传输函数矩阵的关系。而且还通过讨论得出一个线性有限自动机具有阶输入存贮的等价定理。 第三章：输入存贮线性有限自动机的弱可逆性。本章应用输入存贮线性有限自动机的结构矩阵来讨论输入存贮线性有限自动机的弱可逆性，得到阶输入存贮线性有限自动机延迟0步弱可逆的充要条件、延迟步弱可逆和严格延迟步弱可逆的充分条件，由这些条件得出延迟步弱可逆和严格延迟步弱可逆的阶输入存贮线性有限自动机新的构造方法、求出延迟0步弱可逆输入存贮线性有限自动机的一个弱逆。而且还应用输入存贮线性有限自动机的结构矩阵讨论了输入存贮线性有限自动机积的弱可逆性，得出两个阶输入存贮线性有限自动机作全直积和化合之后延迟0步弱可逆的充分必要条件是这两个输入存贮线性有限自动机本身都是延迟0步弱可逆的。这里，、为任意的正整数。 第四章：输入存贮线性有限自动机的极小化。本章用新的方法得出输入存贮线性有限自动机极小的等价定理，由此定理得出输入存贮线性有限自动机极小化的新方法。 第五章：状态机和变换半群积的覆盖关系。本章讨论了两个状态机积的变换半群和它们变换半群的积之间的覆盖关系、两个状态机的积之间的覆盖关系、两个变换半群的积之间的覆盖关系、两个状态机的积与覆盖它们的状态机的积之间的覆盖关系、两个变换半群的积与覆盖它们的变换半群的积之间的覆盖关系。