SICI · 天机门 · 第四章

有限状态机:计算的数学模型 · 炼气四层

画个圈连根线就描述了一切——这句话,状态爆炸之雾说对了一半。

门楣刻字:「M = ( S, I, O, δ, λ )」
序章

幻境入口 · 状态之门

画个圈,连根线,就以为描述了一切?

状态幻演之境的入口没有门。只有一面浮空的石壁,上面爬满了发光的圆圈和箭头——像活物一样缓慢蠕动、分裂、消失。

加法之台,ALU算术逻辑单元

你攥着 ch03 炼成的触发器,以为那就是状态机。石壁旁薄雾低旋。

诺依曼老祖 诺依曼老祖

「你在 ch03 造过一个'1011'检测器。你以为那就是状态机?那只是它的影子。真正的状态机是一个数学模型——五元组。你来定义它。」

状态爆炸之雾 状态爆炸之雾

「画个圈,连根线,就以为描述了一切?」

反直觉下注 · 随手画的状态图合法吗?

先下注:你认为随手画的状态图就是合法的状态机吗?👆 点击下方按钮下注

状态机不是"画图"——是一个五元组 M=(S, I, O, δ, λ)。图形是它的投影,数学定义才是本体。你以为你在画图,其实你在定义一个形式系统。
第一幕 · 甜头

Moore之眼 · 慢一拍的稳

输出只看状态——稳如磐石,但永远慢一拍

石壁后方是一座圆形殿堂,墙上嵌满密密麻麻的输出窗口——每个窗口对应一个状态,窗口里亮着该状态的输出值。

诺依曼老祖 诺依曼老祖

「把你的输出函数 λ 挂在状态上——λ:S→O。进去看看。」

状态爆炸之雾 状态爆炸之雾

「稳。稳到迟钝。」

Moore 机搭建 · 输出 λ:S→O,输入"101"看时序

为每个状态标注输出值,输入序列 101,看检测灯何时亮——比输入慢一个时钟周期。

输入序列
拍 0
喂入序列后拖动时钟游标,看输出始终"追着"状态跑——慢一拍。
Moore 机的输出 λ:S→O,只看状态——稳如磐石,但永远"慢一拍"。输出跟着状态走,状态跟着时钟走。你问它"现在",它回答你"上一拍"。
第一幕 · 机敏

Mealy之手 · 快一拍的险

输出依赖状态和输入——即时响应,但会跟着噪声说谎

转身殿的墙上没有固定窗口——取而代之的是无数只手,每只手抓着两条线:一条连着当前状态,一条连着当前输入。

诺依曼老祖 诺依曼老祖

「把输出函数 λ 挂在转移边上——λ:S×I→O。输入一变,输出立刻变。」

状态爆炸之雾 状态爆炸之雾

「快。快到危险。」

Mealy 机改造 · 输出从节点移到边,即时响应

输出 λ:S×I→O 挂在转移边上。输入"101"时检测灯即时亮——但注入毛刺会看见输出"说谎"。

喂入序列看即时响应;再注入毛刺,看 Mealy 输出在那一瞬跟着跳——一个"假的101"让灯误亮一拍。
Mealy 输出 λ:S×I→O,即时响应——快如闪电,但输入一抖它就跟着抖。Moore 慢一拍但从不撒谎,Mealy 快一拍但会跟着噪声说谎。稳与快之间,没有免费的午餐。
第二幕 · 崩塌

映射之桥 · 转换的代价

等价不等于免费——状态数与毛刺的拉扯

一座悬空石桥横跨深渊,桥面上刻着两行字:左"Moore→Mealy",右"Mealy→Moore"。薄雾第一次明显膨胀了一圈。

诺依曼老祖 诺依曼老祖

「它们能互相转换。去试。」

状态爆炸之雾 状态爆炸之雾

「等价?世界上没有免费的等价。」

双向转换器 · Moore ↔ Mealy + 代价天平

亲手做双向转换:Mealy→Moore 按输出值拆分状态(4→6),Moore→Mealy 合并等价输出状态(6→4)。看天平能否两全。

Moore 端 4 状态数↑ / 稳定性↑
Mealy 端 4 状态数↓ / 毛刺风险↑
两个方向都试一次,看代价天平是否平衡。
Moore 和 Mealy 在表达能力上等价,但转换有代价——Moore→Mealy 省状态但引入毛刺,Mealy→Moore 消毛刺但增加状态。等价不等于免费。每一次转换,你都在用状态数换稳定性,或用稳定性换状态数。
第二幕 · 挣扎

矩阵台 · 状态转移表

图能藏住的数量,表藏不住

矩阵台是一座巨大的棋盘格石台,行列分明。你把 S3 那台 6 状态 Moore 机的转移铺上去——6 个状态、2 种输入,12 行。还好。

「再加一个输入信号呢?」6 状态、4 种输入组合——24 行。你的手开始慢了。薄雾从石台底部漫上来。

状态爆炸之雾 状态爆炸之雾

「继续加。我看你填到第几行开始发抖。」

STT 填充 + 输入增长实验 · 规模 = 状态数 × 输入组合数

为 6 状态 Moore 机填表,再点"加输入信号"看列数翻倍、矩阵面积爆炸。

6 状态 × 2 组合 = 12 格
每加一位输入,列数翻倍。拖到 3 位输入时,96 格已经需要滚动——薄雾漫过膝盖。
STT 的规模 = 状态数 × 输入组合数。每多一位输入信号,列数翻倍。画几个圆圈看起来不多,列成表才知道——每一个圆圈背后,都站着 2^k 列等着你填。
第二幕 · 权衡

编码之环 · 三种编码

二进制省触发器,独热简逻辑,格雷少毛刺

编码之环是三座同心圆环,每座环上刻着同一种状态序列的不同编码。诺依曼老祖:「同一个状态机,三种编码。选一种,看后面会发生什么。」

状态爆炸之雾 状态爆炸之雾

「编码不就是二进制吗?000/001/010……你想复杂了。」

三编码切换器 · 触发器数 / 逻辑复杂度 / 毛刺风险

在三种编码间切换,实时看触发器数、次态逻辑、毛刺波形。每种都试一遍。

触发器数
次态逻辑
毛刺风险
状态数 6
三种编码各试一遍,看触发器数与毛刺的拉扯。拖状态数滑块看二进制与独热的差距拉大。
三种编码各有取舍——二进制省触发器但译码复杂、独热多触发器但次态逻辑极简、格雷折中且毛刺最少。编码不是查字典——是在触发器数量、逻辑复杂度和毛刺风险之间做三角权衡。
第二幕 · 再崩塌

化简殿 · 隐含表之极限

砍掉的是冗余,不是骨架

化简殿中央悬着一张巨大的隐含表——三角网格,每一格代表一对状态的等价性判定。薄雾已经漫到膝盖。

诺依曼老祖 诺依曼老祖

「你 S3 的 6 状态 Moore 机——也许有冗余。去找。」

状态爆炸之雾 状态爆炸之雾

「找吧。把多余的砍掉。砍完了,你看还剩多少。」

隐含表三角网格 · 逐格判定等价状态

点击格子判定:输出不同标 ✗,输出+次态相同标 ✓,条件等价标琥珀。✗ 会自动传播。填完 6 状态合并,再切 12 状态撞"不可再化简"。

✓ 等价 ✗ 不等价 ? 条件
原始状态6
化简后
格子数 C(n,2)15
判定完毕后合并;再切到 12 状态机,化简到 8 状态撞"不可再化简"。
等价状态合并能减少冗余,但不可消除问题本身的内在复杂度。化简砍掉的是你的浪费,不是问题的本质。有些状态天生就不同——就像有些选择没有捷径。
第三幕 · 顿悟

铸阵台 · 三段式电路

次态逻辑 + 状态寄存器 + 输出逻辑

铸阵台上有一座熔炉,旁边摆着你在 S5 选好编码、S6 化简完毕的状态机。诺依曼老祖:「把它浇铸成电路。三段——次态逻辑、状态寄存器、输出逻辑。」

诺依曼老祖 诺依曼老祖

「三段拼合,电路亮了。再看这个计数器——你 ch03 造过。它也是状态机,状态按固定序列循环,是 FSM 的特例。」

三段式浇铸 · STT → 次态逻辑 + D 触发器 + 输出逻辑

把 STT 拆成"次态函数"和"输出函数",分别浇铸成组合逻辑,中间夹一列 D 触发器。

依次浇铸三段,电路亮起;再分析计数器、探测幽灵状态。
FSM 电路 = 次态组合逻辑 + 状态寄存器 + 输出组合逻辑,三段式。计数器是输入恒定的特殊 FSM。但编码空间里可能有未使用的"幽灵状态"——不处理它们,电路可能在上电时走入歧途。
第三幕 · 综合

综合之台 · 三件作品

序列检测器 · 自启动 · 握手协议

综合之台铺着三块空白石板,每块旁边刻着任务。诺依曼老祖:「三件作品。造完,你就是真正的状态机师。」你顺利造完前两件。到第三块时,REQ 和 ACK 两个信号在状态图上交织——状态数开始跳涨。

状态爆炸之雾 状态爆炸之雾

「再加一个信号。我看你还画不画得下。」

三件作品 · 全流程综合 + 状态膨胀

① "1011" 重叠检测器
② 自启动设计
③ 握手协议 REQ/ACK
状态数 4
依次完成三件作品;第三件每加一位控制信号,状态数翻倍——薄雾暴涨成幕。
从状态图到电路,全流程贯通。自启动是让机器在任何起点都能回到正轨的保险。但握手协议每多一个控制维度,状态空间就乘以 2——这不是设计的问题,是维度本身在膨胀。
终幕 · 对决

状态爆炸之雾 · 排除法收网

三问拦路,状态账待清

三块石板上的状态图全部碎裂。雾从裂缝中涌出,凝成一面无边无际的墙——墙上密密麻麻爬满了状态节点,多到数不清。

状态爆炸之雾 状态爆炸之雾

「我是状态爆炸之雾。我不住在你的错误里——错误你能改。我住在你'以为可以穷举一切'的地方。每多一个输入变量,状态空间就翻一倍。三问。答错一题,雾就厚一分。」

诺依曼老祖 诺依曼老祖

「你的刻痕,够用了。」

渊账累计 0 笔 · 三问全对后清零

尾声

幻演圆满 · 状态之舞

炼气四层 · 状态之舞 · 圆满

雾散尽时幻境重归清朗。石壁上的状态图碎片缓缓归位,拼成一张完整的知识图谱。

诺依曼老祖 诺依曼老祖

「你入门了。不是因为你画完了所有状态——你永远画不完。是因为你学会了什么时候放下笔。但——状态机本身能不能被'计算'?有没有一种语言,比圆圈和箭头更强大?这些问题,在更后面的章节等你。」

知识图谱点亮 · 把十五个碎片排成认知链

点击下方碎片,按因果顺序点亮认知链。从 FSM 定义到状态爆炸,你走过的每一步都在这条链上。

排错处会闪烁红光,提示该知识点依赖的前置知识。
M=(S,I,O,δ,λ)
五元组 M=(S, I, O, δ, λ),五个字,描述了半个计算理论。你画不完所有的状态——但你不需要。承认边界,是更高维度的开始。
ch05 数据通路与控制单元 🔒(点亮全部图谱后开启)