词计算的形式模型及模糊自动机的最小化算法

作     者：徐芳 

作者单位：电子科技大学 

学位级别：硕士

导师姓名：舒兰

授予年度：2006年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：词计算 格值有限状态自动机 格值正则文法 格值正则语言 Mizumoto型模糊有限状态自动机 

摘      要：词计算是用词取代数值进行计算及推理的方法,是感知计算理论的基础。本文在Lotfi A. Zadeh教授、应明生教授、邱道文教授等人的工作基础上,提出了词计算的两种新的形式模型——基于格值有限状态自动机的词计算形式模型和基于格值正则文法的词计算形式模型,对词计算的形式模型作了进一步研究和探讨。此外,本文对格值有限状态自动机的一种特殊类型——Mizumoto型模糊有限状态自动机的状态最小化约简问题也作了一些探讨,给出了Mizumoto型模糊有限状态自动机的一种状态最小化约简算法。本文主要采用了比较和类比、分析与综合、归纳、反证等研究方法。具体地说,本文的主要内容如下: 1.格值有限状态自动机的研究:首先,提出了格值有限状态自动机的概念,它的状态转移函数定义为? : Q×A×Q→L,即从Q×A×Q到L的映射,其中L是一个完全分配格。然后,给出了基于格值有限状态自动机的数值计算的形式模型。同时,建立了输入是词的格值有限状态自动机的转移函数以及格值有限状态自动机所接收的语言的定义。最后,严格证明了一个刻画基于格值有限状态自动机的数值计算和基于格值有限状态自动机的词计算之间的联系的一个基本定理。 2.格值正则文法的研究:首先,提出了格值(超)正则文法的概念,并给出了格值(超)正则语言的定义,同时给出了两个格值文法等价的刻画。然后,证明了每个格值正则语言都是格值超正则语言。最后,严格证明了一个刻画基于格值正则文法的词计算和基于格值正则文法的数值计算之间的联系的一个基本定理。 3.格值模型的等价性:给出了一个重要定理,严格证明了格值有限状态自动机所识别的语言类和格值正则文法所生成的语言类是一致的。 4.模糊自动机的最小化算法:首先,引入了Mizumoto型模糊有限状态自动机两种状态等价关系;然后,根据这两种等价关系,定义了Mizumoto型模糊有限状态自动机的状态最小化形式;接着,证明了对于每一个Mizumoto型模糊有限状态自动机,都存在一个等价的状态最小化的Mizumoto型模糊有限状态自动机,并且给出了一个状态最小化约简算法;最后,通过一个例子对该算法进行详细说明。