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

模糊剩余有穷自动机

作　者: 张福刚
导　师: 李永明
学　校: 陕西师范大学
专　业: 基础数学
关键词: 模糊剩余语言模糊剩余自动机饱和运算消去运算标准L
分类号: TP301.1
类　型: 硕士论文
年　份: 2013年
下　载: 20次
引　用: 0次
阅　读: 论文下载

内容摘要

自动机是计算的简单数学模型,在计算机科学中有着重要的作用.最小化问题一直是自动机领域的重要问题之一.确定型有穷自动机(DFA)的最小化已经得到了有效的算法,但对于非确定型有穷自动机(NFA)却一直没有得到理想的结果.剩余有穷自动机(RFA)是基于Myhill_Nerode定理定义的一类特殊的NFA,在研究NFA的最小化过程中起到了十分重要的作用,为自动机最小化研究探索出了一条新的途径.1965年,L. A. Zadeh提出了模糊集理论,1967年,W. G. Wee将模糊集的概念引入到了自动机理论中.随后,模糊自动机便得到了广泛的研究.模糊有穷自动机可以看做是经典自动机的一个扩充,其中包含了像“大约”“高”“矮”这类模糊的、不准确的概念,即就是在自然语言中经常用到的一些模糊语言.正如经典的自动机那样,最小化问题依然是模糊自动机的核心问题之一,虽然确定型模糊自动机的最小化已经有了很好的结果,但是非确定型模糊自动机的最小化问题还有待研究.由于RFA在研究经典自动机的最小化问题中起到了重要作用,我们考虑利用类似的方法进行模糊自动机的最小化研究.本文在完备剩余格上定义了一种重要的模糊自动机(LFA)类型-模糊剩余有穷自动机(LRFA). LRFA是一类特殊的LFA,确定型模糊有穷自动机(DLFA)是特殊的(LRFA)通过定义标准LRFA来实现LRFA的最小化.本文的主要工作如下：1.给出了模糊剩余语言(LRL)的概念,讨论了LRL的基本运算和基本性质,利用LRL给出构造最小DLFA的方法.结合LRL给出LRFA的定义,讨论了LRFA的一些重要的性质.在以上定义的基础上,利用截集对LRFA进行了讨论,有效的将LRFA与RFA联系起来,即LRFA的λ一截集是RFA.2.讨论了LRFA的最小化问题,定义了LFA的饱和运算与消去运算,讨论了两种运算相关的一些重要性质,特别的,LRFA经过这两种运算后依然是LRFA;在定义饱和运算与消去运算的基础上给出了标准LRFA的概念,证明了标准LRFA是状态最小的惟-LRFA以及标准LRFA拥有比识别相同语言的最小DLFA更少的状态数；讨论了DLFA、LRFA以及LFA识别语言的包真含关系,并在LFA转化为DLFA算法的基础上,给出了LFA转化为DLFA的算法.

全文目录

摘要  3-4
Abstract  4-7
前言  7-11
第1章预备知识  11-19
  1.1 格与完备剩余格  11-13
  1.2 模糊集合  13-14
  1.3 模糊语言与模糊自动机  14-16
  1.4 剩余语言与剩余自动机  16-19
第2章模糊剩余有穷自动机  19-29
  2.1 模糊剩余语言  19-21
  2.2 模糊剩余有穷自动机  21-25
  2.3 LRFA的λ截自动机  25-29
第3章标准LRFA  29-43
  3.1 LFA的饱和运算  29-32
  3.2 LFA的消去运算  32-36
  3.3 标准LRFA  36-43
结论  43-45
参考文献  45-49
致谢  49-51
攻读硕士学位期间科研成果  51

模糊剩余有穷自动机

内容摘要

全文目录

相似论文