模糊自动机及其语言的代数性质与应用研究

摘要

自动机与形式语言理论对于计算机系统及其语言、软件的发展具有重要的影响，它还广泛的用于生命科学，生物化学，心理学，语言学等学科。由于现实的复杂系统往往含有不确定性，研究不确定环境下的计算理论成为20世纪60年代以来的热点课题，对形式语言的刻画与分类一直是其中的一个重要的研究方向。为了缩短形式语言与自然语言之间的差距，模糊自动机的理论与应用研究迅速展开。李永明教授分别于2005年和2011年提出的基于格半群和格值的模糊自动机理论成为目前模糊自动机研究的主要方向。本文在此基础上先从代数角度研究基于序半群的模糊自动机及其代数性质，进一步，对于一般的格结构，从宽度优先和深度优先两种语义角度出发，研究了基于格的模糊正则文法理论。另外，在直觉模糊集及伪半环背景框架下进一步对下推自动机和上下文无关语言进行详细研究，为自然语言建立了适应的计算理论数学模型。本文的主要工作具体有以下几个方面:
　　 (1)基于序半群的自动机的代数性质。
　　 提出取值于序半群的模糊自动机，证明(强)后继算子和前驱算子，模糊后继和模糊前驱算子在某些条件下为闭包算子。引进弱主子机器，给出格半群上的自动机的一种唯一分解方法。以quantale为真值结构，证明这种模糊自动机的模糊子机器与模糊子系统一致。最后详细探讨了序半群上的自动机的某些算子的性质与真值结构的代数性质的内在联系。特别地，模糊后继和前驱算子的保并性质可分别由序半群的右和左分配律刻画，且当真值结构为格半群时，后继算子的幂等性可由格半群的无零因子性等价刻画。
　　 (2)基于格的模糊文法理论。
　　 基于宽度优先和深度优先语义方式，建立取值于格的模糊文法理论，这将为模糊自动机的分析提供一种必要的工具。研究取值于格的有穷自动机(简记为l-VFAs)、格值正则文法(1-RGs)及格值确定型正则文法(1-DRGs)之间的关系。结果发现，基于每一种语义方式，1-VFAs与1-RGs在接受相同的模糊语言类的定义下是等价的。进一步，证明格值确定型自动机、1-VFAs、1-RGs及1-DRGs在深度优先语义方式下是相互等价的。对任意1-RG，以宽度优先方式识别的语言与以深度优先方式识别的语言一致当且仅当真值论域l是分配格。
　　 (3)直觉模糊上下文无关语言。
　　 以直觉模糊集为真值结构，我们提出直觉模糊上下文无关文法(IFCFGs)及具有终状态的直觉模糊下推自动机(IFPDAs)。然后研究直觉模糊可识别语言的代数刻画包括分解形式和表现定理。通过引进一般化的子集构造方法，我们证明IFPDAs与它的简单形式即直觉模糊简单型下推自动机(IFSPDAs)等价，并且证明所有的直觉模糊可识别步骤函数类与所有由IFPDAs接受的语言类是一致的。进一步，得到以终状态方式接受语言的直觉模糊下推自动机和以空栈方式接受语言的直觉模糊下推自动机是等价的。另外，我们基于直觉模糊集提出乔姆斯基范式文法(IFCNF)和Greibach范式文法(IFGNF)。研究结果表明，由IFCFGs生成的直觉模糊上下文无关语言集分别与由IFCNFs生成的语言集和由IFGNFs生成的语言集相等，而且他们都等同于直觉模糊可识别步骤函数集。接下来我们研究了直觉模糊上下文无关语言的代数运算性质。最后，给出判定直觉模糊上下文无关语言的Pump引理及其实例分析。
　　 (4)伪半环上的加权下推自动机与上下文无关文法。
　　 基于转移语义和宽度优先代数语义，我们研究取值于伪半环的加权下推自动机和加权上下文无关文法(WCFG)。证明伪半环上的加权下推自动机比加权有穷自动机的计算能力更强。在转移语义方式下，以终状态方式接受形式幂级数的加权下推自动机(WPDAs)与以空栈方式接受形式幂级数的加权下推自动机(WPDAsθ)等价。对任意加权下推自动机，研究以转移语义和宽度优先代数语义识别的形式幂级数相同时的等价刻画。对任意WPDA，识别的形式幂级数的象集是有限的当且仅当伪半环是双局部有限生成的。进一步，证明若伪半环满足乘法局部有限生成的条件，则对任意WPDA，且基于转移语义方式，存在一个分明简单型加权下推自动机与之等价。最后给出证明，基于以上两种语义方式中的任一种，仅以最左推导方式生成形式幂级数的WCFGs和WPDAsθ在识别相同的形式幂级数的意义下是等价的。

目录

声明

摘要

第1章 绪论

1．1 概述

1．1．1 国内外研究的历史和现状

1．1．2 本课题的研究意义

1．2 创新点及主要内容

第2章 基于序半群的自动机的代数性质

2．1 取值于序半群的自动机定义及其性质

2．2 L-FFA的一种分解形式

2．2．1 弱子机器和弱主子机器

2．2．2 L-FEA的一种分解方法及结果

2．3 L-FFA的模糊后继和前驱算子，模糊子机器和子系统

2．4 序半群上的模糊自动机的代数刻画

2．5 实例分析

第3章 基于格的模糊文法理论

3．1 格值有穷自动机及其语言

3．2 基于格的模糊文法

3．3 格值正则文法和格值有穷自动机

3．3．1 格值正则文法和格值有穷自动机

3．3．2 格值确定型正则文法及其刻画

第4章 直觉模糊上下文无关语言

4．1 预备知识

4．2 直觉模糊下推自动机

4．3 直觉模糊上下文无关文法

4．3．1 直觉模糊文法与直觉模糊上下文无关文法

4．3．2 直觉模糊上下文无关文法的代数刻画

4．3．3 直觉模糊上下文无关语言的代数性质

4．4 直觉模糊上下文无关语言的Pump引理

第5章 伪半环上的加权下推自动机与上下文无关文法

5．1 基于伪半环的加权下推自动机

5．1．1 定义

5．1．2 加权下推自动机之间的关系

5．1．3 加权下推自动机的代数刻画

5．2 取值于伪半环的加权上下文无关文法

5．2．1 定义及其性质

5．2．2 WCFG与WPDA(θ)之间的关系

5．3 实例分析

结论

参考文献

致谢

附录A 攻读学位期间所发表的学术论文目录