基于神经网络的模糊自动机 ——模糊文法推导及格值自动机的最小化

论文摘要

文法推导是解决诸如语言识别、图像中的对象识别、蛋白质结构预测和基因结构预测等问题的一种合适的方法,而实现文法推导的其中一种方式就是人工神经网络。由于文法和自动机的等价性,用神经网络实现文法推导实际上就是从神经网络提取自动机。首先,本文介绍了文法推导的神经网络方法。文中分别从传统文法推导和模糊文法推导这两方面进行阐述,主要介绍了该方法的网络拓扑结构、权重学习算法和自动机提取算法等。在总结前人工作的基础上,作者将离散化思想引入二阶反馈神经网络中,提出了一种新的用于学习模糊文法的神经网络拓扑结构,并给出了相应的神经网络的权重学习算法,从而解决模糊文法推导问题。此外,本文研究了自动机的最小化方法。文中先概括前人在模糊自动机的最小化问题上的工作,然后本文提出了优化等价关系和优化同余关系等定义,并把模糊自动机推广为格值自动机,运用代数学理论,推导出了一种新的格值自动机的最小化算法。本文中,作者的具体工作概括如下:1.基于神经网络的模糊自动机的研究。首先,将离散化思想引入网络结构,提出了多级离散化函数,得到了一种用于模糊文法推导的、支持多输入字符的自聚类反馈神经网络,并推导出针对该网络模型的权重学习算法——伪梯度算法,一旦网络训练成功,网络的内部状态是有限和稳定的,从而解决了神经网络的内部状态对于长的未见字符串的稳定性问题,并且省略了用聚类的方法从网络提取自动机这个步骤,简化了模糊自动机的学习和提取过程。在提出网络结构和学习算法以后,给出了仿真的结果。2.格值自动机的最小化算法的研究。首先,提出了优化等价关系和优化同余关系的定义,并将其应用到格值自动机的状态空间上,运用代数学理论,获得相应的等价类,构造出商空间,从而得到商格值自动机;然后在给出两个格值自动机等价的定义的基础上,证明了原格值自动机与商格值自动机的等价性,又由格值自动机的最小性的定义,证明了商格值自动机的最小性。在完成理论的证明后,提出了能在计算机上实现的格值自动机的最小化算法,并给出了实例说明。本文主要采用了比较、归纳、分析与综合等理论推导方法,并进行实验仿真和实例验证。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究意义
• 1.2 研究现状
• 1.3 主要工作
• 第二章 文法和自动机的基本理论
• 2.1 引言
• 2.2 文法与语言
• 2.3 自动机与语言
• 2.4 文法与自动机的关系
• 第三章 基于神经网络的传统文法推导
• 3.1 文法推导
• 3.2 神经网络和自动机在知识表示上的等价性
• 3.3 用二阶反馈神经网络进行传统文法推导
• 3.4 用自聚类反馈神经网络进行传统文法推导
• 第四章 基于神经网络的模糊文法推导
• 4.1 引言
• 4.2 用反馈神经网络进行模糊文法推导
• 4.3 用自聚类反馈神经网络进行模糊文法推导
• 第五章 模糊自动机的最小化算法
• 5.1 引言
• 5.2 基于可代替性划分的模糊有限自动机的最小化
• 5.3 基于同余和同态的模糊自动机的最小化
• 第六章 格值自动机的最小化算法
• 6.1 引言
• 6.2 基于优化同余的格值自动机的最小化算法
• 第七章 结论
• 致谢
• 参考文献
• 攻硕期间取得的研究成果