学位论文 > 优秀研究生学位论文题录展示

下推自动机的半环方法

作　者: 麻勇军
导　师: 刘耀军
学　校: 太原科技大学
专　业: 计算机软件与理论
关键词: 半环线性代数下推自动机形式语言
分类号: O153.3
类　型: 硕士论文
年　份: 2009年
下　载: 31次
引　用: 0次
阅　读: 论文下载

内容摘要

当今自动机理论及其相关的形式语言的理论得到了高度的发展,由其衍生出的知识也层出不穷。但经典自动机和语言理论也存在某方面的不足,特别是一些证明从数学的角度看仍不够完美,一个典型的例子就是在自动机的理论中,自动机状态转换的描述,仅仅是定义了状态转换,从数学运算的角度看还不够严密。本文在下推自动机概念的基础上给出了其在半环上的定义,下推转换矩阵的引入,使下推自动机的行为和半环代数理论上的等式建立了联系。从而使下推自动的讨论更加简洁。首先,介绍了课题研究的对象下推自动机的概念、下推自动机的及时描述、下推自动机所接受的语言等相关概念与半环、半模、收敛等概念。并重点讨论了偏序半环和关于偏序半环上等式的一些性质。最后说明了课题实现的具体目标和意义。接着,引入了与语言理论密切相关的形式幂级数的概念,并将半环的概念转换到形式幂级数,同时在引入矩阵概念的基础上也将半环的概念转移到矩阵,重点证明了布尔形式幂级数矩阵半环和形式幂级数布尔矩阵半环的子半环同构,进一步结合形式幂级数布尔矩阵半环和分块矩阵的相关理论给出了:与矩阵星运算求解相关的线性系统,并证明了线性系统与矩阵星运算相关的一些定理。最后,提出了语言半环的概念,证明了它和布尔形式幂级数半环是同构的。在语言半环到语言矩阵半环扩展的基础上定义了下推转移矩阵,进而定义了下推自动机和下推自动机行为。特别是下推转换矩阵的引入,通过一系列矩阵半环同构将下推自动机行为的研究转移到布尔形式幂级数矩阵半环上,最终使下推自动机的计算转变为矩阵半环上下推转换矩阵的乘法和加法运算。

全文目录

中文摘要  3-4
ABSTRACT  4-8
第一章引言  8-14
  1.1 选题背景和国内外研究现状  8-12
    1.1.1 下推自动机理论  8-11
    1.1.3 国内外研究现状  11-12
  1.2 本文的主要研究内容  12
  1.3 研究下推自动机半环方法的目的和意义  12
  1.4 本论文的组织结构如下  12-14
第二章形式幂级数和矩阵半环  14-34
  2.1 半环理论  14-18
    2.1.1 幺半群  14
    2.1.2 半环  14-18
  2.2 形式幂级数半环  18-21
    2.2.1 形式幂级数  18
    2.2.2 半环向形式幂级数半环的转换  18-20
    2.2.3 形式幂级数序列  20-21
  2.3 矩阵  21-34
    2.3.1 矩阵的概念  21-23
    2.3.2 半环向矩阵半环的转换  23-24
    2.3.3 矩阵半环的收敛  24-25
    2.3.4 矩阵半环上半模的相容性  25-26
    2.3.5 矩阵的分块  26-27
    2.3.6 布尔形式幂级数矩阵半环  27-31
    2.3.7 半环等式及定理向矩阵半环的推广  31-34
第三章下推自动机的半环方法  34-52
  3.1 语言半环  34-35
  3.2 语言半环和布尔形式幂级数半环的关系  35-36
  3.3 下推自动机的半环方法  36-52
    3.3.1 幂级数半环到幂级数矩阵半环的转换  36-42
    3.3.2 下推自动机的半环表示  42-48
    3.3.3 布尔矩阵形式幂级数自动机和线性系统的联系  48-52
第四章总结和展望  52-53
参考文献  53-56
发表文章目录  56-57
致谢  57-58

下推自动机的半环方法

内容摘要

全文目录

相似论文