DFA最小化学习笔记

定义

DFA: 众所周知啊.

DFA的等价类: 若DFA中两个节点相同字符的出边指向的节点属于同一等价类, 则它们是等价的.

算法简介

大致原理是选择一个等价类 $A$ 作为”证据”, 若所有能到 $A$ 中的节点集合为 $X$ , 而存在等价类 $Y$ 满足 $X\cap Y\ne \varnothing, X/Y\ne \varnothing$ , 则可以把 $Y$ 划分成这两个部分.

于是算法流程就是初始化一个证据集合包含结束节点, 一个等价类, 每次取出一个证据, 然后执行上面的过程, 然后把它删了, 如果 $Y$ 在证据中就把 $Y$ 删了, 分成的两个部分, 否则加入两个部分中少的那一个, 直到证据集合为空.

复杂度是 $n\vert \sigma\vert \log n$ .

应用

感觉主要用在dpofdp上, 因为本质相同的dfa最小化结果唯一, 就是说你内层dp的状态设计有很多种, 但最小化的结果应该是相同的. 会得到和你本质相同的所有dfa中最小的一个.

遇到这种题要大胆猜能用到的状态没看上去那么多.