等价性在自动机极小化中的应用

论文摘要

自动机理论的研究始于20世纪40年代，经过几十年的发展，自动机理论已成为计算机科学中的一个重要分支，并应用于计算机科学的许多领域，如编译程序构造、文本处理、结构型数据翻译以及开关线路设计等，它是计算机软、硬件研究的重要基础理论。自动机理论的研究主要涉及两个方面，分别是正则表达式和有穷自动机，正则表达式和有穷自动机的描述能力是等价的，任何正则表达式都可以转化成识别它所描述的语言的有穷自动机。判断一个给定的语言是非正则语言通常使用泵引理，然而，这一过程相对比较繁琐，本文通过引入等价性原理，提出了正则语言的代数判定定理，大大简化了正则语言的判定步骤。有穷自动机的化简是一个十分重要的问题，在等价的前提下，自动机的状态越少，意味着越节省软件和硬件资源。状态的最小化过程是指将自动机的状态集划分成一些不相交的子集，使得任何两个不同的子集中的状态都是可区分的，而同一子集中的任何两个状态都是等价的。最后，我们可以将子集用其中一个元素代表。本文通过等价性原理，引入等价类的概念，并在此基础上提出了确定型有穷自动机的最小化算法，即等价归并算法，利用该算法，可以将某一给定的确定型有穷自动机状态集上的等价状态归并掉，生成与其等价的最小化的确定型有穷自动机。对于非确定有穷自动机的化简，本文同样通过引入等价类的概念，在参照确定型有穷自动机最小化算法的基础上，提出了非确定型有穷自动机的最小化算法。

论文目录

• 摘要
• Abstract
• 第一章 前言
• 1.1 研究背景
• 1.2 研究的主要内容及意义
• 1.3 本文的结构安排及主要工作
• 第二章 有穷自动机与正则表达式
• 2.1 引言
• 2.2 确定型有穷自动机
• 2.2.1 确定型有穷自动机的形式定义
• 2.2.2 DFA识别的语言
• 2.3 非确定型有穷自动机
• 2.3.1 非确定性有穷自动机的形式定义
• 2.3.2 确定型有穷自动机与非确定型有穷自动机的等价性
• 2.3.3 带ε转移的非确定型有穷自动机
• 2.4 正则表达式
• 2.4.1 正则表达式的运算符及其构造
• 2.4.2 正则表达式的应用
• 2.5 有穷自动机和正则表达式的转换
• 2.5.1 从 DFA到正则表达式
• 2.5.2 通过消除状态把 DFA转化为正则表达式
• 2.5.3 根据正则表达式构造自动机
• 2.5.4 自动机的运算
• 第三章 正则语言的判定
• 3.1 引言
• 3.2 正则语言的泵引理
• 3.3 泵引理的改进与加强
• 3.4 正则语言的代数判定定理
• 第四章 确定型有穷自动机的最小化
• 4.1 引言
• 4.2 基本概念
• 4.3 确定型有穷自动机的最小化算法
• 4.4 验证
• 4.5 算法的程序实现
• 第五章 非确定型有穷自动机的最小化
• 5.1 引言
• 5.2 基本概念
• 5.3 位置自动机
• 5.4 偏导自动机
• 5.5 序（跟随）自动机
• 5.6 NFAs化简的基本思路
• 5.7 非确定型有穷自动机的最小化算法
• 5.8 算法验证
• 第六章 全文总结及进一步的工作
• 致谢
• 参考文献