对DFA最小化算法等价性问题的探讨与改进

摘要

有穷自动机极小化问题的研究,在程序测试、模糊系统、概率自动机等方面具有重要意义.利用自动机状态集上的等价关系对自动机的状态集极小化,从而得到与原自动机功能等价的极小化自动机,该内容是词法分析的重点.很多编译原理书籍介绍的DFA最小化算法是"分割法",但该算法存在一定的问题,本文从对一些特殊的DFA的处理入手,分析"分割法"算法在等价原则方面的漏洞,并提出了对最小化问题的改进算法.