编译原理:DFA的最小化

书本上关于DFA最小化的方法的文字说明比较晦涩,因此在这里举个实例来说明.

题目:最小化下图所示的DFA

1.写出DFA的状态转换矩阵

2.初始状态划分

把所有状态按照”是否为终结状态”,划分为2个集合:

3.考察每个元素数量大于2的集合

判断这些集合的元素经过推导后,所到达的状态的集合,是否位于现存的任一集合的子集中.如果位于不同的子集,那么就要对这个集合进行拆分.

3.1 Round1

由于状态1,2经过a后,得到的状态6,7是集合[5,6,7]的子集.而状态3,4经过a后,得到的状态1,4是集合[1,2,3,4]的子集.因此对集合{1,2,3,4}进行切分,分为{1,2}和{3,4}两个集合.

在经过切分后,当前所有集合变为{1,2}{3,4}{5,6,7}

3.2 Round2

由于状态6,7经过a后,得到的状态4是集合{3,4}的子集.而状态5经过a后,得到的状态{7}是集合{5,6,7}的子集.因此对集合{5,6,7}进行切分,分为{5}和{6,7}两个集合.

在经过切分后,当前所有集合变为{1,2}{3,4}{5}{6,7}

3.3 Round3

由于状态3经过b后,得到的状态5是集合{5}的子集.而状态4经过b后,得到的状态{6}是集合{6,7}的子集.因此对集合{3,4}进行切分,分为{3}和{4}两个集合.

在经过切分后,当前所有集合变为{1,2}{3}{4}{5}{6,7}

再进行验证可发现,到这一步为止,不再有新的切分,因此切分完成.

4.重命名状态,画出新的转换矩阵及DFA

重命名:

新的转换矩阵,其中状态4,5为终结状态.

最小化后的DFA: