DFA的最小化

为什么最小化

DFA的最小化即寻求状态数最小的，且与原DFA等价的DFA

意义：最小化可以降低编译器构造的复杂度，提高编译器的运行效率

最小化是否存在

P56 定理3.2：对任意一个DFA N都存在一个等价的DFA M使得M包含最少的状态数，且M唯一(状态名不同的同构情况除外)

最小化算法

前置知识

1.状态之间的等价与可区分：

假设s和t为M的两个状态

• 若分别从状态s和状态t出发都能读出某个字α而停止于终态，则称s和t等价

• 存在一个字α，使得s和t一个读出α停止于终态，另一个读出α停止于非终态，则称s和t可区分

因此通过空串，一切非终态和终态之间都是可区分的

2.无用状态和不可达状态

无用状态：不存在从该状态到达终态的路径
不可达状态：不存在从初态到达该状态的路径

eg：

详细步骤

1.预处理：删除N中所有的无用状态和不可达状态

2.对N的状态集进行划分

• 初始划分：Π={F,S-F [,{error}] }

• 对Π的每个子集P进行划分，直到Π中任意两个不同子集的状态是可区分的，而同一子集的任何两个状态是等价的(划分依据)

划分的依据：

对于任意一个状态子集
I j = { q 1 , q 2 , q 3 . . . q k } I_j = \bigr\{{q_1,q_2,q_3...q_k}\bigr\} Ij​={q1​,q2​,q3​...qk​}
若存在一个输入字母表中的a，使得
T ( q i , a ) = s , T ( q j , a ) = t , s 和 t 不 在 当 前 划 分 Π 的 任 何 一 个 状 态 子 集 中 T ( q i , a ) 和 T ( q j , a ) 的 任 何 一 个 无 定 义 T(q_i,a)=s,T(q_j,a)=t,s和t不在当前划分Π的任何一个状态子集中\\ T(q_i,a)和T(q_j,a)的任何一个无定义 T(qi​,a)=s,T(qj​,a)=t,s和t不在当前划分Π的任何一个状态子集中T(qi​,a)和T(qj​,a)的任何一个无定义
则可以把 I j I_j Ij​一分为二

3.让每个子集选出一个代表，同时消去该子集的其他状态

实例

P55 图3-13