书本上关于DFA最小化的方法的文字说明比较晦涩,因此在这里举个实例来说明....题目:最小化下图所示的DFA
1.写出DFA的状态转换矩阵
2.初始状态划分
把所有状态按照”是否为终结状态”,划分为2个集合:
3.考察每个元素数量大于2的集合
判断这些集合的元素经过推导后,所到达的状态的集合...在经过切分后,当前所有集合变为{1,2}{3,4}{5,6,7}
3.2 Round2
由于状态6,7经过a后,得到的状态4是集合{3,4}的子集.而状态5经过a后,得到的状态{7}是集合{5,6,7...在经过切分后,当前所有集合变为{1,2}{3,4}{5}{6,7}
3.3 Round3
由于状态3经过b后,得到的状态5是集合{5}的子集.而状态4经过b后,得到的状态{6}是集合{6,7}的子集....最小化后的DFA: