DFA的最小化

null确定的有穷自动机（DFA）的最小化确定的有穷自动机（DFA）的最小化DFA的最小化DFA的最小化1.什么是最小化? 2.能不能最小化? 3.怎样最小化?1.什么是最小化？1.什么是最小化？定义：DFA的最小化就是寻求 状态数最小的 与原DFA等价的 DFA 意义：最小化可以降低编译器构造的复杂度、提高编译器的运行效率。最小化的例子最小化的例子A2:b1aA3:{ambn|m≧0,n ≧1}2.能不能最小化？2.能不能最小化？定理： 对于一个DFA M =（K,∑, f, k0, kt)， 存在一个唯一最小状态（就状态数而言） DFA M’ =（K’,∑, f’, k0’, kt’) 与之等价。 （证明略） 3.怎样最小化－－例子13.怎样最小化－－例子1aabS1SaS3bS2abaS3Sa怎样最小化－－例子1小结怎样最小化－－例子1小结消除多余状态 什么是多余状态？ 从这个状态没有通路到达终态；S1 从开始状态出发，任何输入串也不能到达的那个状态。S2 如何消除多余状态？ 删除怎样最小化－－例子2怎样最小化－－例子2bba10b2b等价状态，合并怎么最小化－－例子2小结怎么最小化－－例子2小结合并等价状态 什么是等价状态？ 如何寻找等价状态？ 如何合并？等价状态等价状态在有穷自动机中，两个状态s和t等价的条件是： 一致性条件——状态s和t必须同时为终态或非终态。 蔓延性条件——对于所有输入符号，状态s和状态t必须转换到等价的状态里。 如果状态s和状态t不等价，则称这两个状态是可区别的。等价状态等价状态6 与 7等价3 与 4等价1与 5可区别c∑＝｛a,b,c,d｝合并等价状态的目标合并等价状态的目标 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。 合并等价状态A 1,2,3,4,5,6,7nullc合并等价状态 －－－分割法nullc合并等价状态 －－－分割法null 3 6 3 5 4 7 3 5ab 1 3 2 2 4 2 3 6 3 5 4 7 3 5 5 4 6 6 7 6cdΠ1Π2ab 1 3 2 2 4 2 5 4 6 6 7 6cdΠ2Π1Π3c合并等价状态 －－－分割法null 5 4 3 6 3 5 4 7 3 5ab 1 3 2 2 4 2 6 6 7 6cdΠ1 3 6 3 5 4 7 3 5ab 1 3 2 2 4 2 5 4 6 6 7 6cdΠ1Π3Π2Π2Π3Π4c合并等价状态 －－－分割法null 5 4 3 6 3 5 4 7 3 5ab 1 3 2 2 4 2 6 6 7 6cdΠ1Π2Π3Π4 B C C D C Bab A C A D D cd最小化－例子最小化－例子null175aaabbb632bbbccdd4nullnullΠ1Π2nullΠ1Π2Π3nullΠ1Π2Π3Π4nullΠ1Π2Π3Π4null1总结总结1.什么是最小化? 没有多余状态(死状态) 没有两个状态是互相等价（不可区别） 2.能不能最小化? 有定理保证，一定存在最小状态的DFA与之等价 3.怎样最小化? 消除多余状态 合并等价状态 识别等价状态－－分割法（重点） 合并等价状态