有限自动机（DFA / NFA）

父级：regular-languages

一台机器，只有一个有限的状态集合，别无其他——从左到右读取输入，随之改变状态；若最终停在接受状态则接受。

DFA

一个确定性有限自动机是一个五元组 (Q, Σ, δ, q₀, F)：状态集 Q，字母表 Σ，转移函数 δ : Q × Σ → Q，起始状态 q₀，接受状态集 F ⊆ Q。对输入 w，从 q₀ 出发按 δ 逐个符号转移；当且仅当最终所处状态属于 F 时接受。

NFA

一个非确定性有限自动机允许 δ 返回一个状态集合作为下一状态（δ : Q × Σ → Q 的某个子集），并允许ε-转移（不读任何符号就改变状态）。只要存在某条运行路径最终停在 F 中，它就接受 w。

关键事实

• NFA 等价于 DFA。 子集（幂集）构造法把一个 NFA 转换成一个 DFA，其状态是 NFA 状态的集合——语言不变，但状态数最多可达 2ⁿ（这种膨胀是真实存在的）。
• 最小 DFA 是唯一的。 合并不可区分的状态（Hopcroft 算法）会得到一个规范的、状态数最少的 DFA；它的状态数等于 Myhill–Nerode 等价类 的数目。
• 没有记忆。 唯一的"状态"就是有限个 Q 中的一个——所以有限自动机无法计数无界的数量（因此识别不了 aⁿbⁿ，见 regular-languages）。

有限自动机是正则语言这一类的机器面孔；表达式面孔是 regular-expressions，文法面孔是 regular-grammar，三者由 regular-equivalences 统一在一起。