一类非确定型有穷自动机的极小化及时间复杂性

论文摘要

本文对自动机理论的研究主要是两个方面:自动机的极小化和极小化的时间复杂性。在自动机的状态集合上定义等价关系,引入等价类,将等价的状态合并成一个状态,生成新的状态数较小的自动机。新生成的自动机与原自动机识别的语言不变,也就是说它们是等价的。这就是树图分割法的思想。利用树图分割法可以进行确定型有穷自动机的极小化。本文的重点内容是构造了一类非确定型有穷自动机,即连接型有穷自动机。这类有穷自动机是由两台确定型有穷自动机连接而成的。利用两台确定型有穷自动机状态集合上的等价关系可以构造出连接型有穷自动机状态集合上的等价关系。这类非确定型有穷自动机也可以利用树图分割法来极小化。还可以得到连接后再极小化的自动机的状态数不大于极小化后再连接的自动机的状态数。非确定型有穷自动机的情况比较复杂。往往比较大的有穷自动机没有等价状态,但将其中某两个或者几个状态进行合并并不改变它们的语言。本文给出了非确定型有穷自动机状态合并的条件。找到了非确定型有穷自动机极小化状态的临界条件。自动机极小化的时间复杂性,有效的验证了极小化算法是否有效。一般地,多项式时间内能完成的就认为该算法是有效的。确定型有穷自动机和连接型有穷自动机利用树图分割法进行极小化,它们都在状态的三次方时间内就可以完成。本文的最后给出了非确定型有穷自动机极小化算法。

论文目录

• 摘要
• Abstract
• 第一章 前言
• 1.1 研究背景
• 1.2 研究的主要内容及意义
• 1.3 本文的结构安排及主要工作
• 第二章 有穷自动机基本理论
• 2.1 引言
• 2.2 确定型有穷自动机基本概念
• 2.3 非确定型有穷自动机基本概念
• 2.4 带ε转移的非确定型有穷自动机基本概念
• 2.5 连接型有穷自动机基本概念
• 2.6 确定型有穷自动机与非确定型有穷自动机的等价性
• 第三章 确定型有穷自动机的极小化
• 3.1 确定型有穷自动机的极小化
• 3.2 验证算法
• 3.3 自动机极小化的时间复杂性
• 第四章 连接型有穷自动机的极小化
• 4.1 采用树图分割法实现连接型有穷自动机的极小化
• 4.2 算法验证
• 4.3 连接型有穷自动机极小化的时间复杂性
• 第五章 非确定型有穷自动机的极小化
• 5.1 非确定型有穷自动机极小化的相关概念
• 5.2 非确定型有穷自动机的极小化的临界条件
• 5.2.1 非确定型有穷自动机状态合并条件
• 5.2.2 非确定型有穷自动机极小化
• 5.3 非确定型有穷自动机的极小化算法
• 全文总结及进一步的工作
• 致谢
• 参考文献
• 附录