确定有限自动机(DFA)

定义

确定有限自动机(Deterministic Finite Automaton,DFA)是一种有限状态机:由状态集合、输入字母表、转移函数、初始状态与接受状态集构成,任一状态对任一输入符号有且仅有一个后继状态。读完输入后停在接受状态即接受该字符串。

与 NFA 的关系

非确定有限自动机(NFA)允许同一输入有多个转移或空转移,书写更自然;子集构造法可把任意 NFA 转换为等价 DFA,代价是状态数最坏指数级膨胀。两者识别能力相同,恰为正则语言。

应用

词法分析器生成器(如 Flex)把记号的正则定义编译为 DFA,以每字符一次转移的线性时间切分源码;RE2 等正则引擎用 DFA/NFA 模拟避免回溯型引擎的指数级最坏情形(ReDoS);网络入侵检测的多模式匹配同样依赖自动机。

性质

DFA 可用 Hopcroft 算法最小化,得到唯一的最小等价自动机。