12.1 有限状态机

第 2.4 节说明，组合电路只根据当前输入产生输出。同一个输入向量出现两次，电路两次的输出一定相同。然而，许多系统必须记住之前发生过什么：闸机处于锁定状态时和已经解锁时，面对同一个动作会有不同反应；交通灯也必须知道自己当前处在哪个阶段。本节要加入的正是这种能力：用一个小而精确的状态保存必要的记忆。

1. 从电路的瞬间画面走向随时间运行的系统

状态是对过去信息的压缩描述，只保留会影响系统未来行为的部分。我们不需要记录完整历史，只需要区分那些会导致未来反应不同的情况。

考虑一个地铁闸机：

• 处于 Locked（锁定） 状态时，投入硬币应当解锁；
• 处于 Unlocked（解锁） 状态时，推动闸杆应让一人通过并重新锁定；
• 推动已锁定的闸机，状态不变；
• 向已经解锁的闸机再次投币，状态也不变。

两个可能状态组成集合

所有可能输入组成输入字母表，用希腊大写字母 sigma 表示：

这里的“字母表”只是指一个有限的输入符号集合。由 $\Sigma$ 中符号排成的有限序列叫作输入串。例如

是长度为 $3$ 的输入串。不含任何符号的串叫作空串，记为 $\varepsilon$。

2. 转移函数

系统在某个当前状态下收到一个输入后，迈向下一个状态，这一步叫作一次转移。转移函数写作

符号 $\delta$ 读作 “delta”，是这个函数的名字。笛卡尔积 $Q\times\Sigma$ 包含所有 $(q,a)$ 形式的配对，其中 $q$ 是当前状态，$a$ 是输入。因此，$\delta(q,a)$ 的意思是“在状态 $q$ 收到输入 $a$ 后的下一个状态”。

对于闸机，

完整函数可以写成一张状态转移表：

读取一个单元格时，先用行选当前状态，再用列选输入，交叉单元格就是下一状态。每个“状态—输入”配对都恰好有一个答案，因此这条规则既是确定的，也是完备的：

• 确定性：每个状态—输入配对恰好有一个下一状态；
• 完备性：每个可能的状态—输入配对都定义了下一状态。

同样的信息也可以画成有向状态图。每个状态是一个顶点，每次转移是一条标有输入的有向边：

(起点) ──► [Locked]

[Locked]   ──coin──► [Unlocked]
[Locked]   ──push──► [Locked]       （自环）
[Unlocked] ──coin──► [Unlocked]     （自环）
[Unlocked] ──push──► [Locked]

从一个状态回到自身的边叫作自环。从黑色起点标记出发的箭头指出初始状态，记作 $q_0$。这里

这并不是一套全新的图论。它直接复用了第 11 章：状态是顶点，输入是有向边的标签，而处理输入串就是沿着图走一条游走。

3. 跟踪输入串

要跟踪一台机器，先位于 $q_0$，再从左到右逐个处理输入符号。对于

完整轨迹为：

所以最终状态是 Unlocked。请注意关键区别：同一个输入 push 可能得到不同的下一状态，因为当前状态保存了记忆。

常见错误是处理每个输入前都跳回初始状态。初始状态只在第一个符号之前使用一次。此后，每一步的下一状态都会成为下一步的当前状态。

亲手操作实体闸机，同时观察状态卡片与轨迹账本同步更新。然后开启维护模式，重放同一输入串，找出行为发生变化的第一条转移。

4. 接受输入串：确定有限自动机

有时机器需要对整个输入串回答“是”或“否”。确定有限自动机，简称 DFA，在状态机上增加了一组接受状态：

除 $F$ 外，每个部分都已经出现过：

• $Q$：有限状态集合；
• $\Sigma$：有限输入字母表；
• $\delta$：转移函数；
• $q_0\in Q$：初始状态；
• $F\subseteq Q$：接受状态集合。

读完整个输入串后，如果最终状态属于 $F$，DFA 就接受这个串；否则拒绝它。只有处理完所有输入符号之后，才判断是否接受。

例：以 01 结尾的二进制串

令 $\Sigma=\{0,1\}$。我们的目标是只接受最后两个符号为 $01$ 的输入串。机器只需要记住三种情况：

• $q_0$：已处理的前缀目前既不以 $0$ 结尾，也不以 $01$ 结尾；
• $q_1$：已处理的前缀以 $0$ 结尾；
• $q_2$：已处理的前缀以 $01$ 结尾。

状态转移表为：

初始状态是 $q_0$，接受集合是 $F=\{q_2\}$。跟踪 $1101$：

最终到达接受状态 $q_2$，所以 $1101$ 被接受。

5. 把 delta 从一个符号扩展到整个输入串

原来的函数 $\delta$ 一次处理一个输入符号。现在定义扩展转移函数 $\delta^*$，让它处理整个输入串：

其中，$\Sigma^*$ 表示由 $\Sigma$ 中符号组成的所有有限输入串，包括 $\varepsilon$。递归定义为

这里 $x$ 是已经处理的前一段输入串，$a$ 是最后一个符号。第一条规则说明“什么都不读”不会改变状态；第二条规则说明：先处理前一段 $x$，再处理最后的 $a$。

DFA 接受 $w$ 的充要条件是

6. 用不变式说明状态的含义

我们怎样证明三状态机器确实识别“以 $01$ 结尾”的串？需要为每个状态写出精确的状态不变式，也就是处理完任意前缀后都应成立的陈述：

验证方法与第 5 章的循环不变式相同：

1. 初始化：还没有读入符号时，前缀是 $\varepsilon$，所以 $q_0$ 的描述正确。 2. 保持：对每个状态和每个可能的下一符号检查转移表，机器总会进入与新后缀相符的状态。 3. 结论：读完整个输入串后，处于 $q_2$ 当且仅当该串以 $01$ 结尾。

这是一段证明，而不只是列出几个成功样例。

7. 可达状态、死状态与遗漏的行为

如果存在某个输入串能让机器从 $q_0$ 到达状态 $q$，那么 $q$ 是可达的。从图的角度看，可以暂时忽略边标签，从 $q_0$ 运行 BFS 或 DFS。没有被访问到的状态就是不可达状态，它从初始状态出发永远不会影响机器行为。

死状态是一个非接受状态，并且从它出发再也不可能到达任何接受状态。DFA 一旦进入死状态，当前输入串以及它的任何后续扩展都会被拒绝。死状态可能在每个输入上都有自环，但定义的关键是“无法再到达接受状态”，而不是图画成什么形状。

这些图算法检查可以暴露设计问题：

• 不可达状态可能是多余的；
• 缺少一条转移会使机器不完备；
• 同一个状态与输入出现两条转移会破坏确定性；
• 可达死状态可能表示永久错误，也可能是意外设计出的陷阱。

8. 会产生输出的机器

自动机对整个输入串分类，而控制器通常要在运行过程中不断给出输出。

在 Moore 机中，输出只依赖当前状态。输出函数为

其中 $O$ 是输出字母表。例如名为 NorthGreen 的交通灯状态可以输出“南北绿灯，东西红灯”。

在 Mealy 机中，输出同时依赖当前状态和当前输入：

因此，它可以在收到输入的当下立刻改变输出，而不必等待状态改变。Moore 机通常把输出写在状态节点内；Mealy 机通常在边上写成“输入/输出”。

两种模型并没有绝对优劣。应根据输出究竟需要利用哪些信息来选择。

9. 从状态机到时序电路

时序电路由三个部分组成：

1. 用于编码当前状态的存储位； 2. 计算 $\delta(q,a)$ 的组合型下一状态电路； 3. 可选的、用于计算 $\lambda$ 的组合输出电路。

如果一台机器有 $|Q|$ 个状态，$k$ 个存储位最多编码 $2^k$ 个状态。因此，状态位的最小数量为

上取整 $\lceil x\rceil$ 表示“不小于 $x$ 的最小整数”。有 $5$ 个状态的机器需要

个状态位，因为 $2^2=4<5\le 8=2^3$。

完整流程为

这把第 2.4 节的布尔电路扩展成随时间运行的机器：布尔逻辑门负责计算每一步，而已存储的状态把必要的过去带入下一步。

直接改写 DFA 状态转移表，逐个符号跟踪输入带，再启动对抗搜索，让它返回能暴露设计与“以 $01$ 结尾”规格分歧的最短输入串。

10. 现在可以建模什么

到这里，你已经能够在状态转移表、有向状态图和逐步轨迹之间转换；形式化定义 DFA；用不变式证明状态含义；识别不可达状态和死状态；区分 Moore 输出与 Mealy 输出；并把有限状态控制器与布尔电路连接起来。

最后一节会把这些思想与前面学过的计数、概率、算法、树和图结合起来。我们不再孤立地研究一种结构，而是设计并论证一个完整的智慧城市网络，让路线、决策和控制器状态协同工作。