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

上传人:f****u 文档编号:115129264 上传时间:2019-11-12 格式:PDF 页数:62 大小:602.12KB
返回 下载 相关 举报
关于输入存贮线性有限自动机和状态机的研究_第1页
第1页 / 共62页
关于输入存贮线性有限自动机和状态机的研究_第2页
第2页 / 共62页
关于输入存贮线性有限自动机和状态机的研究_第3页
第3页 / 共62页
关于输入存贮线性有限自动机和状态机的研究_第4页
第4页 / 共62页
关于输入存贮线性有限自动机和状态机的研究_第5页
第5页 / 共62页
点击查看更多>>
资源描述

《关于输入存贮线性有限自动机和状态机的研究》由会员分享,可在线阅读,更多相关《关于输入存贮线性有限自动机和状态机的研究(62页珍藏版)》请在金锄头文库上搜索。

1、广西师范大学 硕士学位论文 关于输入存贮线性有限自动机和状态机的研究 姓名:冯文俊 申请学位级别:硕士 专业:基础数学 指导教师:邓培民 20070401 - - I 关于输入存贮线性有限自动机和状态机的研究 关于输入存贮线性有限自动机和状态机的研究 研究生:冯文俊 导师:邓培民教授 学科专业:基础数学 研究方向:代数及其应用 年级:2004 级 摘 要 摘 要 自动机理论是研究离散数字系统的功能、结构及其两者关系的数学理论。五十年代, 在开关网络理论和数理逻辑中图灵机理论的基础上,形成了自动机理论这一数学分支学 科。随着科学技术的发展,自动机理论有了深入的发展和广泛的应用,成为许多学科的重

2、要理论和基础。 自动机理论中最重要的问题之一是技术实现问题,文献1给出了任意的线性有限自 动机在一定条件下都可以等价嵌入于一个输入存贮线性有限自动机。也就是说,在一定条 件下, 任意的线性有限自动机的功能都可以通过输入存贮线性有限自动机来实现。 文献2 证明了任何延迟步可逆线性有限自动机都存在阶输入存贮线性有限自动机为它的延迟 步逆。并且,输入存贮线性有限自动机在有限自动机公钥密码体制和数字签名中也有重 要的应用 3-12。而输入存贮线性有限自动机是一类典型的、易于实现的线性有限自动机。 所以,我们有必要对输入存贮线性有限自动机进行讨论,以便进一步研究任意的线性有限 自动机和为密码学、网络、自

3、动控制、模式识别等而服务。 本文从输入存贮线性有限自动机本身出发对其进行研究,剖析了其自身结构,两个输 入存贮线性有限自动机作积之后的结构,一个线性有限自动机M具有r阶输入存贮的等价 定理。然后应用输入存贮线性有限自动机的结构矩阵讨论了输入存贮线性有限自动机的弱 可逆性,得到了h阶输入存贮线性有限自动机延迟 0 步弱可逆的充要条件、延迟步弱可 逆和严格延迟步弱可逆的充分条件,由这些条件得出了延迟步弱可逆和严格延迟步 弱可逆的h阶输入存贮线性有限自动机新的构造方法、求出延迟 0 步弱可逆h阶输入存贮 线性有限自动机的一个弱逆(这里,为任意正整数) 。而且还应用输入存贮线性有限自动 机的结构矩阵讨

4、论了输入存贮线性有限自动机积的弱可逆性,得出两个h阶输入存贮线性 有限自动机作全直积和化合之后延迟 0 步弱可逆的充分必要条件是这两个h阶输入存贮线 性有限自动机本身都是延迟 0 步弱可逆的。此外,本文应用输入存贮线性有限自动机的线 性系数组成的矩阵来研究输入存贮线性有限自动机的极小化问题,得到输入存贮线性有限 自动机极小的等价定理,由此定理得出输入存贮线性有限自动机极小化的新方法。对状态 自动机来说,与自动机的等价嵌入类似的问题是状态机的覆盖问题。本文还讨论了两个状 态机积的变换半群和它们变换半群的积之间的覆盖关系、两个状态机的积之间的覆盖关 系、两个变换半群的积之间的覆盖关系、两个状态机的

5、积与覆盖它们的状态机的积之间的 覆盖关系、两个变换半群的积与覆盖它们的变换半群的积之间的覆盖关系。 本文共分五部分,每部分为一章。 第一章:引言。本章主要介绍了输入存贮线性有限自动机在自动机理论中所起的重要 - - II 作用以及国内外学者应用输入存贮线性有限自动机研究的一些成果, 并给出了 (输入存贮) 线性有限自动机的一些概念与记号。 第二章:输入存贮线性有限自动机积的讨论。本章通过讨论得出输入存贮线性有限自 动机本身结构矩阵的特点、两个输入存贮线性有限自动机作积之后仍然是输入存贮线性有 限自动机,还讨论了两个输入存贮线性有限自动机作积之后的结构矩阵、自由响应生成矩 阵、传输函数矩阵和原来

6、两个输入存贮线性有限自动机的结构矩阵、自由响应生成矩阵、 传输函数矩阵的关系。 而且还通过讨论得出一个线性有限自动机M具有r阶输入存贮的等 价定理。 主要结论有: 定理 2.2.4 定理 2.2.4 设M是( )GF q上输入、输出维数分别为, l m的h阶输入存贮线性有限自动 机,由下式定义: 0 ( )(),0,1, h j j y iB x ij i = = ?,其中 j B 为( )GF q上m l阶矩阵。 则M的结构矩阵A,B,C,D分别为: ,1, ,2, , ,1, , 0000 0000 0000 00 00 l lll ll ll l l ll lll ll l l ll l

7、l ll l l ll lhl l ll l hl hl E E A E = ? ? ? ? ? ? , , 0 0 l l l l l hl l B E = ? 11 , hh CB BB =? 0 D B = 这里, , 0l l表示ll阶零阵, ,i l E 表示第i个l阶单位阵, l E 表示l阶单位阵,1,1ih=?. 定理 2.2.10 定理 2.2.10 设M 是( )GF q 上线性有限自动机,则M 具有r 阶输入存贮性M 等价 于 1 M 与M的后并,其中 1 M 是一个r 阶输入存贮线性有限自动机,M是一个具有r 阶输 入存贮性的自治的线性有限自动机。 定理 2.2.15

8、定理 2.2.15 设(, , , , ) MX Y S =, ( ,)MY Y S =是两个h阶输入存贮线性有 限自动机, 则(, ,)MMX Y SS =是2h阶输入存贮线性有限自动机。 第三章:输入存贮线性有限自动机的弱可逆性。本章应用输入存贮线性有限自动机的 结构矩阵来讨论输入存贮线性有限自动机的弱可逆性,得到h阶输入存贮线性有限自动机 延迟 0 步弱可逆的充要条件、延迟步弱可逆和严格延迟步弱可逆的充分条件,由这些 条件得出延迟步弱可逆和严格延迟步弱可逆的h阶输入存贮线性有限自动机新的构造 方法、求出延迟 0 步弱可逆输入存贮线性有限自动机的一个弱逆。而且还应用输入存贮线 性有限自动机

9、的结构矩阵讨论了输入存贮线性有限自动机积的弱可逆性,得出两个h阶输 入存贮线性有限自动机作全直积和化合之后延迟 0 步弱可逆的充分必要条件是这两个输入 存贮线性有限自动机本身都是延迟 0 步弱可逆的。这里,、h为任意的正整数。 主要结论有: - - III 定理 3.2.2 定理 3.2.2 设M 是( )GF q 上h阶输入存贮线性有限自动机,由下式定义: 0 ( )(),0,1, h j j y iB x ij i = = ?.则: (1)M 延迟 0 步弱可逆M 的结构矩阵D列线性无关。 (2)当1h时,若0,0,1,1 j Bj=?,则M 严格延迟步弱可逆 B列线性 无关。 推论 3.

10、2.3 推论 3.2.3 设M 是( )GF q 上h阶输入存贮线性有限自动机,由下式定义: 0 ( )(),0,1, h j j y iB x ij i = = ?.则: (1) 如果 0 B 列线性无关,则M 延迟步弱可逆。为任意非负整数。 构造 3.3.1 构造 3.3.1 由定理 3.2.2 的方法,我们可以构造出( )GF q 上严格延迟步弱可逆的h 阶输入存贮线性有限自动机M .方法如下:设M 由下式定义: 0 ( )(),0,1, h j j y iB x ij i = = ?,其中 j B 为( )GF q 上m l阶矩阵。 令 011 0BBB=?, B为( )GF q 上列

11、线性无关的m l阶矩阵, 1, , h BB + ?为( )GF q 上任意的m l阶矩阵,则这样定义的M 为严格延迟步弱可逆的h阶输入存贮线性有限自 动机。这里,1h. 构造 3.3.2 构造 3.3.2 由推论 3.2.3(1)的方法,我们可以构造出( )GF q 上延迟步弱可逆的h 阶输入存贮线性有限自动机M .方法如下:设M 由下式定义: 0 ( )(),0,1, h j j y iB x ij i = = ?,其中 j B 为( )GF q 上m l阶矩阵。 令 0 B 为( )GF q 上列线性无关的m l阶矩阵, 12 , h B BB?为( )GF q 上任意的m l矩阵, 则

12、这样定义的M 为延迟步弱可逆的h阶输入存贮线性有限自动机。这里,为任意非负 整数。 定理 3.4.1定理 3.4.1 设(, , , , ) MX Y S =是( )GF q 上h阶输入存贮线性有限自动机,由下式定 义: 0 ( )(),0,1, h j j y iB x ij i = = ?, 0 0B. 若M 延迟 0 步弱可逆, 则存在 (0,4)阶存贮线性有限自动机( ,) MY X S =为M 的延 迟 0 步弱逆。M由下式定义: 1 ( )()( ),0,1 h j j x iPB x ijPy i i = = += ? 这里:P 为 0 B 的左逆矩阵。 定理 3.5.1 定理

13、3.5.1 设(, , , , ),(,)MX Y SMX Y S =为( )GF q 上两个h阶输入存贮 线性有限自动机,分别由以下两式定义: M : 0 ( )(),0,1, h j j y iB x ij i = = ? - - IV M: 0 ( )(),0,1, h j j y iB x ij i = = ? 若M 和M都延迟 0 步弱可逆, 则M 和M的全(, , , )MMXX YYSS= 延迟 0 步弱可逆。 定理 3.5.2 定理 3.5.2 设(, , , , ) MX Y S =, ( ,)MY Y S =是( )GF q 上两个h阶输入存 贮线性有限自动机, M 的输入

14、、输出维数分别为l、m,M的输入、输出维数分别为m、 m,M 和M分别由以下两式定义: M : 0 ( )(),0,1, h j j y iB x ij i = = ? M: 0 ( )(),0,1, h j j y iB y ij i = = ? 若M 和M都延迟 0 步弱可逆,则M 和M的化合(, ,)MMX Y SS =延迟 0 步弱 可逆。 第四章:输入存贮线性有限自动机的极小化。本章用新的方法得出输入存贮线性有限 自动机极小的等价定理,由此定理得出输入存贮线性有限自动机极小化的新方法。 主要结论有: 定理 4.2.8 定理 4.2.8 设(, , , , ) MX Y S =是( )

15、GF q 上h阶输入存贮线性有限自动机, 由下式定 义: 0 ( )(),0,1, h j j y iB x ij i = = ?,则 M 极小U的列在( )GF q 上线性无关。这里,U为M 的线性系数组成的矩阵, 11 2 hh h h mh n BBB BB U B = ? ? ? 定理 4.2.11 定理 4.2.11 设(, , , , ) MX Y S =是( )GF q 上h阶输入存贮线性有限自动机,由下式 定义: 0 ( )(),0,1, h j j y iB x ij i = = ?. M 的结构矩阵为 A,B ,C,D.设U的 1, , r jj?列是它的( )GF q 上极大线性无关列, 这些列组成矩阵 1 U ,且 1 UU T=,T 是( )GF q 上rn矩阵。设 1 M 是( )GF q 上线性有限自动 机,结构矩阵为 1111 ,ATA BTB CC DD=.其中 A, C 分别为 A和C的第 1, ,

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 办公文档 > 其它办公文档

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号