基于简单路径上的识别字实现DFA的最小化

摘要

DFA最小化的关键在于给出状态集合中所有的等价类.根据状态等价的定义,若能求出每一状态在其所有识别路径上的识别字,则通过比较这些状态的识别字,就可获得状态集合中所有的等价类.现有文献中并未采用这一方法,原因是对于某些状态,可能存在一些较为复杂的识别路径,若按这些路径逐一求出对应的识别字,则有一定的难度.文中基于识别路径中的简单路径,给出一种基于简单路径上的识别字实现DFA最小化的算法.该算法可作为现有算法的一个有益补充.