一种改进的从NFA到DFA的转换算法

摘要

研究了不确定的有限自动机转换为与之等价的确定的有限自动机的算法机制和复杂性,以及传统的子集算法在转换过程中存在的大量重复遍历和无效遍历现象,并针对上述现象提出了一种改进的子集法算法MF-SUBSET.结果表明,MF-SUBSET算法通过增加状态标志和遍历路径标志来决定当前的搜索策略,能够有效地避免转换过程中的重复遍历和无效遍历操作,极大地提高了转换效率.