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

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

Discussion and Improvement on Minization to DFA Algorithm in Equivalence Property Problem

The aspect such as studying,testing,mixing up in procedure system,probability automaton having the poor automaton is minimal melt question has importance.Make use of the equivalence relation that automaton state has assembled to assemble to the automaton state minimalization,being molten an automaton with equal in value minimum of plain automaton function thereby,owed content the priority being lexical analysis.Many algorithms compiling and translating DFA that principle books introduces minization is "division law ",is an algorithm's turn to have certain problem but,from the main body of a book starting to a few peculiar DFA treatment,have analysed the "division law " algorithm leak in the field of equivalence principle,and have suggested that to minimized problem improvement algorithm.