DFA：每步只有一条路

一台 deterministic finite automaton 由五样东西给定：一组状态、一个字母表、一个 start state、一组 accept state，以及转移函数 $\delta$，它规定「在某状态读到某字符，去哪个状态」。确定性的约束在于：对每个（状态，字符）组合，$\delta$ 给出恰好一个去向。读一个串的过程因而完全确定，从 start state 起步逐字符照 $\delta$ 跳，读完看落点是不是 accept state。

1 · 一台判整除的三态机器

这台机器读二进制串，判断它代表的数能否被 3 整除。状态只记当前余数是 0、1 还是 2：多读一个 bit 时数值由 $v$ 变成 $2v + b$，余数随之更新，这三条更新规则就是状态之间的转移。读完停在余数 0 的状态即接受。

确定性直接给出运行代价：读 $n$ 个字符恰好跳 $n$ 次，每跳一次是 $O(1)$ 的查表，整段输入 $O(n)$，只过一遍且指针不回头。代价转移到了构造期，这张转移表与全部状态都得预先备好。NFA 页的取舍正相反：表小巧，但读的时候要同时考虑多种可能。