有限自动机化合和等价于(输入)存贮线性有限自动机问题

《有限自动机化合和等价于(输入)存贮线性有限自动机问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、有限自动机的化合与等价于(输入)存贮线性有限自动机问题学科专业：基础数学年级：2001级研究方向：代数及其应用研究生：文毅玲摘要自动机理论是研究离散数字系统的功能、结构及其两者关系的数学理论。五十年代，在开关网络理论和数理逻辑中图灵机理论的基础上，形成了自动机理论这一数学分支学科。目前，根据自动机的应用情况，主要集中在可逆自动机、线性自动机和循环自动机的研究上。我国学者陶仁骥于1985年首先提出了有限自动机公开钥密码体制(FAPKC)，由于这一理论在构造单钥、双钥和基于身份的密码体制等密码学重要分支中都有良

2、好的应用，并具有很大的应用潜力，进一步激发了人们的研究兴趣。在双钥和基于身份的密码体制的构造中，有限自动机的化合成为一种基本手段。就我所知，除文献[3~5]对两个有限自动机化合前后的可逆性及RaRb变换之间的关系进行了深入的研究外，还没有其它研究化合性质的文章。本人对有限自动机化合前后的严格延迟步数，弱逆，极小性和线性性等的关系作了一系列研究，获得的结果对于在密码体制构造中构造具有所需性质的自动机具有重要的指导意义。主要结论有：1．关于严格延迟步数：Mi是X上严格延迟ôi步弱可逆的，i=1，2，则M1·M2是

3、延迟ô1+ô2步弱可逆的[12]，若设其严格延迟步数为ô，则有ô1≤ô≤ô1+ô2；若ô1=0，则M1·M2与M2·M1都是严格延迟ô2步弱可逆的；对一般情形，给出M1·M2是严格延迟ô1+ô2步弱可逆的一个充要条件。2．关于弱逆：1)如果M1'是M1的延迟ô步弱逆，M2'是M2的延迟0步弱逆，则M2'·M1'是M1·M2的延迟ô步弱逆；2)如果M1'是M1的延迟ô步逆，M2'是M2的延迟ô'步弱逆，给出M2'·M1'是M1·M2的延迟ô+ô'步弱逆的一个充分条件。3．关于极小性：化合后的有限自动机极小必然要

4、求化合前的两个有限自动机均极小。例证两个极小有限自动机的化合未必极小。4．关于线性性：线性有限自动机的化合仍为线性有限自动机，并给出它们之间的结构矩阵、自由响应生成矩阵和传输函数矩阵的显式关系式。此外，自动机理论中最重要的一个问题是技术实现问题，所以对一般自动机都是研究线性实现问题，而(输入)存贮线性有限自动机是一类典型的、易于实现的且结构简单的线性有限自动机。文献[33]中给出了等价嵌入于存贮线性有限自动机的一组充要条件以及一个可等价嵌入的充分条件和一个不可等价嵌入的充分条件。"嵌入于"意味着后者的功能强于

5、前者，并可能强于前者许多，这就是说后者虽然能实现前者的功能，但可能会有一些"浪费"。什么样的线性有限自动机刚好与一个(输入)存贮线性有限自动机功能等价，或者说(输入)存贮线性有限自动机能够实现的功能最强线性有限自动机是哪一类线性有限自动机？本人运用文献［33］提出的模的思想方法研究(输入)存贮线性有限自动机的功能等价问题，回答了上述问题，从而对于将一类复杂的线性有限自动机化简为易于实现的(输入)存贮线性有限自动机具有重要的理论和现实意义。主要结论有：1．可等价嵌入于一个输入存贮线性有限自动机，则必然等价于这个

6、输入存贮线性有限自动机。并给出一组等价于输入存贮线性有限自动机的充要条件和一个充分条件。2．给出等价于存贮线性有限自动机的一个充要条件。3．两个(输入)存贮线性有限自动机的化合，必存在它的一个子线性有限自动机与一个(输入)存贮线性有限自动机等价。全文分为三章：第一章介绍自动机理论的历史背景与发展现状和本人的研究内容与主要结果，并将文中涉及到的一些基本概念和记号作了系统的介绍。第二章对有限自动机化合前后的严格延迟步数、弱逆、极小性以及线性性等的关系进行研究，给出所获得的结果。第三章运用文献［33］提出的模

7、的思想方法研究(输入)存贮线性有限自动机功能等价问题，解决了什么样的线性有限自动机刚好与一个(输入)存贮线性有限自动机功能等价的问题。关键词：有限自动机;化合;等价;输入存贮AbstractAutomatatheoryisamathematictheory,whichessentiallyresearchesthefunctions,thestructures,andtherelationshipsbetweenthemfordiscretemathematicssystems.In1950s,ontheba

8、sicofswitchnetworktheoryandtheTuringmachinetheoryofmathematicallogic,itformedtheautomatatheory,whichisabranchofmathematics.Atpresent,accordingtotheapplicationsituationoftheautomatatheory,Itfocusesonthe