形式陈述

确定性有限自动机是五元组 $(Q,\Sigma,\delta,q_0,F)$$(Q,\mathrm{\Sigma },\delta ,q_0,F)$：$Q$$Q$ 是有限状态集，$\delta:Q\times\Sigma\to Q$$\delta :Q\times \mathrm{\Sigma }\to Q$ 是转移函数，$q_0$$q_0$ 是初态，$F\subseteq Q$$F\subseteq Q$ 是接受态。读完整个字符串后位于 $F$$F$ 即接受。

直觉

机器只有固定数量的记忆状态，不能随输入增长保存信息；它擅长识别有限模式和周期性结构。

例子与边界

可以用两个状态判断二进制串中 $1$$1$ 的个数奇偶。有限自动机不能识别 $\{0^n1^n:n\ge0\}$$\{0^n{1}^n:n\ge 0\}$，因为它无法无界地记住前半段长度。

读取 0 时留在原状态，读取 1 时切换状态；双圆是接受态。

推论与应用

DFA、NFA 与正则表达式表达能力相同，用于词法分析、协议状态机、输入验证和硬件控制器。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Chapter 1.
• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Chapter 2.