2.1 DFA 设计与执行：让每个状态都有明确含义

本课设计一个识别“以 abb 结尾”的确定有限自动机，并把状态图变成可执行的转移表。

本课目标

• 写出 DFA 的五元组定义；
• 用状态不变量而不是猜图构造 DFA；
• 理解拒绝状态与完整转移函数；
• 用测试覆盖状态和转移边界。

1. DFA 的五个组成部分

确定有限自动机写作：

$$M=(Q,\mathrm{\Sigma },\delta ,q_0,F).$$

• $Q$：有限状态集合；
• $\mathrm{\Sigma }$：输入字母表；
• $\delta :Q\times \mathrm{\Sigma }\to Q$：转移函数；
• $q_0\in Q$：起始状态；
• $F\subseteq Q$：接受状态集合。

“确定”有两层含义：给定状态和输入符号，恰好有一个下一状态；没有不读取输入符号的 $\epsilon$ 转移。形式定义中的 $\delta$ 是全函数，每个状态对每个字母都要有去处。图上省略的失败边通常隐含指向拒绝或陷阱状态。

2. 扩展转移处理整个字符串

单步转移只读一个符号。扩展转移函数 ${\delta }^{\ast }$ 递归定义为：

$${\delta }^{\ast }(q,\epsilon )=q,$$$${\delta }^{\ast }(q,wa)=\delta ({\delta }^{\ast }(q,w),a).$$

DFA 接受字符串 $w$，当且仅当：

$${\delta }^{\ast }(q_0,w)\in F.$$

自动机不会因为“曾经经过接受状态”就自动接受；必须在读完整个输入后检查最终状态。词法分析中的最长匹配会额外记录最后一次接受位置，那是扫描器策略，不是 DFA 定义的一部分。

3. 先写状态不变量

对语言

$$L=\{w\in \{a,b{\}}^{\ast }\mid w\text{ 以 }abb\text{ 结尾}\},$$

状态只需记录：当前输入后缀与目标 abb 的最长前缀重合多长。

状态	已读前缀满足的不变量
q0	当前后缀与 abb 的最长前缀重合长度为 0
q1	当前以 a 结尾
q2	当前以 ab 结尾
q3	当前以 abb 结尾，接受状态

由此得到完整转移表：

当前状态	读 a	读 b
q0	q1	q0
q1	q1	q2
q2	q1	q3
q3	q1	q0

q3 读到新字符后仍需继续匹配。它不是终止状态；例如 abba 不以 abb 结尾，应从 q3 转到 q1 并最终拒绝。

4. 转移表就是一种实现

下面的 Python 3.9 以上版本示例接受有限字符串或符号序列。把代码保存后运行，所有断言通过时不会输出内容：

from collections.abc import Iterable

TRANSITIONS = {
    "q0": {"a": "q1", "b": "q0"},
    "q1": {"a": "q1", "b": "q2"},
    "q2": {"a": "q1", "b": "q3"},
    "q3": {"a": "q1", "b": "q0"},
}
ACCEPTING = {"q3"}

def accepts_ending_abb(symbols: Iterable[str]) -> bool:
    state = "q0"
    for symbol in symbols:
        if symbol not in {"a", "b"}:
            raise ValueError(f"字母表不包含 {symbol!r}")
        state = TRANSITIONS[state][symbol]
    return state in ACCEPTING

cases = {
    "": False,
    "abb": True,
    "aabb": True,
    "ababb": True,
    "abba": False,
    "bbb": False,
}
for text, expected in cases.items():
    assert accepts_ending_abb(text) is expected

字母表外的输入如 abc 会抛出 ValueError；转移表本身缺边则应暴露配置错误，不要也伪装成用户输入有误。长度为 $n$ 的合法字母表输入执行 $n$ 次转移，时间复杂度为 $O(n)$，额外状态空间为 $O(1)$。若问题要求确认任意位置都没有违规字符，最坏情况下必须查看整个输入；但具体实现仍可能在遇到非法字母时提前失败。

5. 两种常见构造方法

按“已经知道什么”拆状态

例如识别同时包含 a 和 b 的串，可以让状态表示两个布尔事实：是否见过 a、是否见过 b。理论组合有四种，正好得到四个状态。

按“对未来输入的反应是否相同”合并状态

如果两个历史前缀面对任意后续字符串都会同时接受或同时拒绝，就不需要分成两个状态。这一思想由 Myhill–Nerode 关系严格刻画，也是 DFA 最小化的理论基础。

6. 陷阱状态何时需要显式出现

识别标识符时，一旦首字符是数字，后续任何字符都无法让整个字符串重新合法。可以进入陷阱状态：

start --letter/_--> identifier
start --digit/other--> dead
identifier --letter/digit/_--> identifier
identifier --other--> dead
dead --any--> dead

若扫描器是按 token 工作，“其他字符”也可能意味着当前 token 结束，而不是整个输入非法。因此同一状态图不能脱离输入协议解释：是在判定完整字符串，还是从字符流中识别一个最长 token？

7. 测试应覆盖状态意义

不要只列几个“看起来正常”的字符串。针对每个状态设计：

• 能到达该状态的最短输入；
• 从该状态到接受的输入；
• 只差一个字符却应拒绝的输入；
• 空串和字母表外字符；
• 接受后继续输入的情况。

状态不变量还能成为测试断言：处理任意前缀后，当前状态应与该前缀的最长目标后缀一致。

常见误区

• 接受状态没有出边：DFA 必须继续处理剩余输入。
• 图上没画的边表示原地不动：通常表示省略的失败边，语义必须明确。
• 状态名称本身就是设计：只写 q7 不会自动解释状态。先写不变量，否则编号排得再整齐也可能一起走错。
• DFA 只能识别固定字符串：有限状态可表达无限正则语言，例如任意长度的奇偶计数。

练习

1. 设计识别“包含子串 abb”的 DFA，并与“以 abb 结尾”比较接受状态的出边。
2. 设计识别二进制数值对 3 取模为 0 的 DFA，解释每个状态的余数含义。
3. 为 ASCII 标识符判定器补全陷阱状态与测试。
4. 给本课代码增加一个函数，返回最终状态和完整状态轨迹。

小结

DFA 的核心不是圆圈和箭头，而是有限、可检验的历史摘要。状态不变量说明已经知道什么，完整转移表说明每个新符号如何更新这份摘要。

下一课允许机器同时保留多个可能状态。它不会扩大正则语言的范围，却会让“选择”和“可选路径”的构造简单得多。