DFA最小化

[lihongjie0209]

最小DFA

对于每个正则语言，都存在一个最小自动机接受它，即一个有着最小状态数目的DFA，且这个DFA是唯一的（除去状态命名不同的差别）。[2][3] 最小DFA保证了其在模式匹配等计算应用中开销的最小。

在不影响原始DFA所接受语言的情况下，有两类状态可以被移除或合并，以实现最小化过程。

• 不可达状态指DFA在任意输入串下都无法达到的状态。
• 等价状态指在同一输入串下不产生区别的状态。

DFA最小化通常要经历三个步骤，分别对应于相关状态的移除或合并。因为等价状态的消解开销高昂，通常会将其放到最后一步。