确定性有限自动机

DFA 的当前状态是已读前缀的充分摘要。若两个前缀把机器带到同一状态，那么以后接上任何相同后缀，它们都将经过相同的剩余运行并作出相同决定。设计状态时，应直接判断哪些前缀对所有未来都能安全地视为同一种情况；圆的数量只是这项判断的结果。

总转移让每个输入都有完整运行。实现中省略的边通常只是排版简写，数学上应指向一个拒绝死状态；否则交换接受态与拒绝态时，原先“没有下一步”的输入会无处可去，补集构造便失效。死状态把所有无法恢复的失败历史压缩成同一摘要，属于语言语义的一部分。

DFA 可以一遍扫描输入，运行时间为 $\mathrm{\Theta }(|w|)$，额外控制记忆只需记录当前状态。这里没有声称状态表很小：一个语言可能正则，却需要指数多的显式状态。有限状态限制表达能力，状态复杂度衡量同一限制下表示究竟有多昂贵。

HTTP 头部以字节模式 \r\n\r\n 结束。识别“输入中已经出现该分隔符”的 DFA 可用 $q_0,\dots ,q_4$；在尚未匹配成功时，$q_k$ 表示当前前缀的最长后缀恰是模式长度为 $k$ 的前缀，$q_4$ 表示已经见过完整分隔符并保持接受。

例如读到 \r\n\r 时位于 $q_3$。若下一个字节是 \n，进入 $q_4$；若又是 \r，不能简单清零，因为这个新字节本身仍可能是下一次匹配的开头，应退到 $q_1$。这条“最长仍可延续后缀”不变量同时规定了所有失败转移，也是 KMP 类模式自动机不会漏掉重叠匹配的原因。

正确性可按前缀长度归纳。初始空前缀的最长匹配长度为零；每读一个字节，转移表把旧候选后缀与新字节拼接，再保留最长的模式前缀。因而到达 $q_4$ 当且仅当某个已读前缀以完整分隔符结束；把 $q_4$ 设为接受自环后，最终接受恰好等价于整个输入曾包含该模式。

图中的奇偶 DFA 展示另一类摘要：状态只记 1 的计数模 $2$，而不是精确计数。它能处理任意长输入，因为未来只会关心奇偶两种余数。语言 $\{0^n{1}^n:n\ge 0\}$ 则要求在后半段取回任意大的 $n$；任何固定状态集都会混淆两个不同前导计数，因此不可能由 DFA 识别。

DFA 的唯一运行使补集、乘积构造、等价检查和最小化尤其直接。两个 DFA 可同步运行在状态对上；搜索一个“恰有一侧接受”的可达状态，就能找到区分两种语言的见证字，若不存在则语言相等。

虽然 DFA 在语法上限制更严，子集构造证明它与 NFA 在表达能力上等价；代价是一个 $n$ 状态 NFA 的等价 DFA 最坏可能需要 $2^n$ 个状态。自动机最小化公理库有限自动机最小化Finite automaton minimization · DFA minimization删除不可达状态并按全部未来后缀的行为划分状态，构造识别同一语言的唯一最小 DFA。随后删除不可达状态，并把未来行为完全相同的状态合并成唯一的最小表示。

词法分析器、网络字节扫描器和有限事件监控常直接执行 DFA：每个输入只做一次表查找，运行路径可复现，也没有回溯爆炸。若确定化状态过多，则可以保留 NFA 或按需生成实际到达的子集；这是表示策略的折中，不是更换语言语义。