上页我们见过确定有限自动机——下一步永远唯一的那种机器。但「自动机」三个字到底是什么意思？先把确定的限制摘掉，从更朴素的角度看：什么是有限自动机？

同样投 5 角按 A，结果时而是可乐时而是橙汁——这种机器你敢用吗？这正是 NFA 的窘境。DFA 用「确定」二字，把下一状态钉死为唯一，彻底消除这种不可预测。

前几页我们用直觉理解了DFA——状态有限、读符号、一步步跳。要严谨地描述它『长什么样、怎么工作』，需要五个分量说清楚：M=(Q,Σ,δ,q₀,F)。

中间三圆点是Q，左侧两符号是Σ，三条虚线引出q₀、F、δ标注。

把五元组四个分量逐一对应到图上的圆节点、源箭头、带标签弧、双圈上。

把只能吃一个字符的 δ 扩展成能处理整个字符串的 δ̂，靠两条递归子句。

输入固定为 010；从左到右看递归的逐层展开。节点是“当前结果 / 已读前缀”，边表示本次调用基础转移函数 δ。

扩展转移函数告诉我们：给定任意字符串，从q0出发总能走到唯一确定的终点。但走到哪里才算是「成功」？这就要靠接受集F来下结论了。

看 DFA 如何决定取舍：串 '01' 与 '10' 走同一机器，差在最终落入何态。

上一页我们对单条字符串判定「接受/拒绝」。把所有被接受的字符串拢成一个集合，就是这台 DFA「认识」的语言。

上页我们把DFA的语言 L(M) 定义为机器接受的所有字符串的集合。现在把所有能被某个DFA接受的语言归为一类，给个名字——正则语言。这是从机器视角到语言视角的一次切换。

正则语言是「对象」，正则表达式是描述它的「笔」——初学者常混为一谈，搞清关系才能理解等价性定理。

上一页我们确认正则语言与正则表达式等价。现在换个角度：两个正则语言摆在面前，能不能并起来、交起来、取反、拼接？拼出来的还是正则语言吗？

图是DFA的可视化语言，五元组是它的形式化语言。这页教你把图'翻译'回五元组，五步走完不重不漏。

把自然语言描述的语言翻译成DFA，本质上是把约束条件编码进状态与转移里。

把 δ 物化为一颗字典，逐字符查表即完成模拟。

转移表把 δ: Q×Σ→Q 存成有限字典；逐字符 O(1) 查表推进状态，字母表守卫保证了「每读一个符号都能找到下一个状态」——这是 DFA 定义中 δ 为全函数的代码兑现。

本DFA接受首字符为0、末字符为1的二进制串。下图展示状态划分与转移规则。

左侧方案A有4个状态(含冗余);右侧方案B合并冗余后仅3个状态——即该语言的最小DFA。

4状态DFA，由「积状态构造法」得来。每个状态编码一对奇偶（a的、b的）。从双圈出发，沿输入走，落在双圈即接收。

前面我们用 DFA 接受了偶数个 a、含子串 01 的串，现在挑战一个更自然的语言：aⁿbⁿ——n 个 a 后接 n 个 b。这种「先 n 个 a 再 n 个 b」的结构，让所有 DFA 都无能为力——为什么？

非确定性听上去像额外能力——它真的让 NFA 识别更多语言吗？

前页 DFA 数偶数 a、偶数 b 还能撑住，但 a 和 b 一样多就彻底接不住。这不是 DFA 偶然掉链，而是能力边界注定——DFA 能识别的语言，恰好就是正则语言这一层。

对于 DFA M = (Q, Σ, δ, q₀, F)，字符串 w 被 M 接受的判定条件是？

• ✓DFA=(Q,Σ,δ,q0,F)，确定性=每步唯一走向
• ✓δ* 把字符级转移递归推广到字符串处理
• ✓正则语言 ≡ DFA可接受语言，二者互定边界
• ✓状态数有限 = DFA能力的根本约束
• ✓构造套路：识别状态、终态、转移三要素

先遮住答案，给自己三分钟；想不清楚再看提示。