● 摘要
本文的主要内容是研究自动机与文法对基于词的计算.Zadeh 最早提出“模糊逻辑＝基于词的计算”,介绍了模糊计算是粒度计算(granular computing)的最基本的计算工具.应明生教授建立了一种研究自动机对基于词的计算的新模型,指出经典的自动机是基于值的计算,而对于模糊自动机应用模糊扩张原理,创建一种很好的接受模糊词的模型,并讨论了有限自动机和下推自动机对基于词的计算的模型.李永明教授提出了一种新的模糊自动机模型,即格值自动机,在一个比以往研究的模糊自动机更广的框架--格半群意义下来研究自动机理论,并指出格值自动机比一般模糊自动机能识别更广泛的模糊语言.而在经典自动机与一般模糊自动机中,有一个更重要的结论是文法生成的语言与自动机识别的语言等价.由此,我们也会去想文法是否同样能对词进行计算？
本文主要的目的是对模糊的不精确的输入数据进行处理,称为基于词的计算.这为自动机理论创造了一个新的模型.我们主要讨论的是自动机中最基础也是最重要的两类,即有限自动机和下推自动机.与之相对应的文法也将作为讨论对象,即正则文法和上下文无关文法对基于词的计算,且证明了基于词的计算是通过基于值的计算来实现的.
本文共分四章.第一章是预备知识,主要介绍模糊集理论和格半群的概念及性质.第二章介绍词的定义、模糊有限自动机对基于词的计算、模糊双向有穷自动机对基于词的计算及格值有限自动机对基于词的计算,它们都可以通过基于值的计算来实现.第三章介绍正则文法对基于词的计算的处理,其中重点介绍格值正则文法对基于词的计算,并给出了其格值模型的等价性:即格值有限自动机所识别的语言和格值正则文法所生成的语言是相同的.第四章证明了两类下推自动机接受语言的等价性,讨论了模糊下推自动机的对基于词的计算模型，并介绍了上下文无关文法对基于词的计算的模型.其中,格值上下文无关文法着重选取了格值Greibach范式文法来讨论.总之,文法对基于词的计算最终可以通过对基于值的计算来实现.