基于等价类的非确定有穷自动机最小化方法的研究
有穷自动理论给出了一类计算模型，这种模型在计算机科学的若干应用领域都有着重要的作用。有穷自动机可以是确定型有穷自动机(DFA)或非确定型有穷自动机(NFA)，识别的语言类称为正则语言。有穷自动机的最小化是一个十分重要的问题。这里所说的最小化是指在等价的前提下，对有穷自动机进行转换，使得经转换所得到的有穷自动机状态结点最少，但它仍然与原来有穷自动机等价。一般来说，自动机的状态结点越少，意味着越节省软件和硬件资源，实现它的程序也越简练。 本文主要研究和探索基于等价类的非确定型有穷自动机的最小化。主要研究内容包括以下三个方面： (1)关于有穷自动机与正则语言的关系介绍了有穷自动机的基础知识，正则语言的性质以及引入状态转换图的概念证明有穷自动机和正则表达式的等价性。 (2)基于等价类的确定型有穷自动机最小化算法的分析研究了确定型有穷自动机和非确定型有穷自动机的等价性，并在确定型有穷自动机的状态集上引入等价关系，给出了等价类的算法，利用该算法将自动机生成与其等价的最小化自动机。 (3)基于等价类的非确定型有穷自动机最小化算法的研究结合确定型有穷自动机基于等价类的最小化算法，本文给出一种新的基于等价类的非确定型有穷自动机最小化算法。一旦使用这种等价归并方法，我们从同一个正则表达式构造的非确定型有穷自动机总是比位置自动机、基于偏导的自动机、序自动机状态结点少。实验证实了该算法。
- 作者：
- 张丽
- 学位授予单位：
- 贵州大学
- 专业名称：
- 计算机技术
- 授予学位：
- 硕士
- 学位年度：
- 2006年
- 导师姓名：
- 许道云
- 中图分类号：
- TP301.1；TP312
- 关键词：
- 有穷自动机；正则语言；等价关系；等价类；最小化算法
- Finite automata；Regular language；Equivalence relation；Equivalence class；Minimization；Algorithm