确定性有限自动机

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

扩张转移还满足 ${\delta }^{\ast }(q,uv)={\delta }^{\ast }({\delta }^{\ast }(q,u),v)$：可以先处理前段，再从所得状态处理后段。这可对 $v$ 的长度归纳证明，也是“同状态的前缀对所有后缀不可区分”的准确代数依据。

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

例如语言 $a^{\ast }b(\epsilon \mid b)$ 的最小完整 DFA公理库有限自动机最小化Finite automaton minimization · DFA minimization删除不可达状态并按全部未来后缀的行为划分状态，构造识别同一语言的唯一最小 DFA。有四态：尚无 $b$、恰一个 $b$、恰两个 $b$、永久失败。若省略最后一态并把缺边解释为立即拒绝，可以画成三态部分机器；这是一种表示约定，不能把三态图直接当作总转移函数。读到 $ba$ 或 $bbb$ 时，完整机器仍有明确状态，部分机器则已没有运行。只有先补回死状态，再翻转接受标记，才能正确识别补语言。

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 识别。

非正则性的冲突可明确写出。若有 $m$ 个状态，$m+1$ 个前缀 $\epsilon ,0,\dots ,0^m$ 中必有 $0^i,0^j$ 到达同一状态，其中 $i<j$。两者再读同一个后缀 $1^i$，机器必须给出相同答案；但 $0^i{1}^i$ 属于目标语言，$0^j{1}^i$ 不属于。矛盾来自同一状态无法区分所需的未来，而不是仅仅来自计数很大。

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

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

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