书本上关于DFA最小化的方法的文字说明比较晦涩,因此在这里举个实例来说明....题目:最小化下图所示的DFA
1.写出DFA的状态转换矩阵
2.初始状态划分
把所有状态按照”是否为终结状态”,划分为2个集合:
3.考察每个元素数量大于2的集合
判断这些集合的元素经过推导后,所到达的状态的集合...当前所有集合变为{1,2}{3}{4}{5}{6,7}
再进行验证可发现,到这一步为止,不再有新的切分,因此切分完成.
4.重命名状态,画出新的转换矩阵及DFA
重命名:
新的转换矩阵,其中状态4,5为终结状态...最小化后的DFA: