一、一个自动机只有三样东西

状态集合、输入、转移。数学上叫五元组（再多一个起始状态、一个接受状态）， 但真正要写的只有这三样。 教材用的例子是自动售货机。它里面记的不是「收了多少钱」，而是「攒到哪一档了」—— 这就是状态。

二、表驱动：把「有哪些情况」和「怎么处理」拆开

同一件事也可以写成一串条件判断。两种写法在各件事上的代价不一样，Demo 第三段列了五项：

三、状态会相乘

Demo 第四段做了一件很朴素的事： 一扇门有 2 个状态，一盏灯有 2 个状态。要描述「门和灯同时处在什么状况」，就得用组合状态。 2 × 2 = 4。这不是巧合，是乘法：两套独立的状态合起来，状态数是乘的。 三个各有 4 个状态的部件凑一起，就是 4 的 3 次方 = 64；五个部件 1024；六个部件 4096。 Demo 那张表列到第六行，就是为了让这个数字难看。 这就是「状态爆炸」。真实的系统不会把状态摊平成一张大表，而是分成几个小自动机各管一摊， 只在对得上的时候对一下暗号。这套办法叫层级状态机，或者直接叫状态图。 顺带说一句：并发程序里的「状态空间爆炸」是同一个东西。验证一个多线程程序为什么难， 就是因为线程数一多，组合状态数就把内存吃完了。

四、「有限」这两个字卡在哪

Demo 第五段出了一道题：一串 a 后面跟同样多的 b，判断 a 和 b 个数是不是一样多。 自动机没有变量，想数数只能靠「数到第几个就停在第几个状态」。

五、它在软件里的位置

四个地方，一句话一个。

六、动手 Demo：从售货机到「数不清的 a」

这段代码里有两件事：一张表怎么跑，和一台机器怎么被「有限」卡住。 前台那部分是个字典，键是「(当前状态, 输入)」，值是下一状态。查一次就是一次取值，没有分支。 后面那部分用同一个构造函数造了一串自动机，状态数从 4 试到 64，各自去认 a^n b^n。 它们只有 K 不一样。

TABLE = {
    (u'待机', u'五角'): u'五角',
    (u'待机', u'一元'): u'一元',
    (u'五角', u'五角'): u'一元',
    (u'五角', u'一元'): u'该出货',
    (u'一元', u'五角'): u'该出货',
    (u'一元', u'一元'): u'该出货',
    (u'待机', u'退币'): u'待机',
    ...
}

def run(seq):
    """按表跑一串输入，碰见表里没有的组合就停。"""
    st = u'待机'
    for act in seq:
        nxt = TABLE.get((st, act))
        if nxt is None:
            return u'卡住'
        st = nxt
    return st

def build(K):
    """K 个状态的自动机：a 让计数加一，b 让计数减一。"""
    trans = {}
    for s in range(K):
        trans[(s, u'a')] = s + 1 if s < K - 1 else None
        trans[(s, u'b')] = s - 1 if s > 0 else None
    return trans

实跑输出：

--------------------------------------------------------------------
状态转移表
--------------------------------------------------------------------
==============================================================

[1] 自动机就是一张表

  卖饮料的机器，只认三个动作：投五角、投一元、退币。
  它里面记的不是钱，是「攒了多少」这一个状态：

  状态：待机、五角、一元、该出货

    当前状态    收到      下一状态
    ----------------------------------
    待机        五角      五角
    待机        一元      一元
    待机        退币      待机
    五角        五角      一元
    五角        一元      该出货
    五角        退币      待机
    一元        五角      该出货
    一元        一元      该出货
    一元        退币      待机
    该出货      退币      待机

  这张表就是整个程序。没有循环、没有计算、没有变量，
  只有「现在在哪、听到什么、去哪」三件事。
  状态一共 4 个，动作一共 3 个，表最多 12 行。

[2] 按表跑一串输入

  输入：五角、五角、一元

    待机     收到「五角  」→ 五角
    五角     收到「五角  」→ 一元
    一元     收到「一元  」→ 该出货

  最后落在「该出货」，可以出货

  输入：五角、退币、一元、五角

    待机     收到「五角  」→ 五角
    五角     收到「退币  」→ 待机
    待机     收到「一元  」→ 一元
    一元     收到「五角  」→ 该出货

  最后落在「该出货」，可以出货
  退币之后状态回到待机，前面投的那五角等于白投——
  状态一清，历史就没了。这是自动机最要紧的一条性质。

[3] 同一件事，用 if 堆出来会怎样

  不用表，改成一串条件判断，最直接的写法是这样：

    if 状态 == 待机 and 动作 == 五角: 状态 = 五角
    elif 状态 == 待机 and 动作 == 一元: 状态 = 一元
    elif 状态 == 五角 and 动作 == 五角: 状态 = 一元
    ...

  状态 4 个、动作 3 个，组合 12 种；表里写了 10 行，
  剩下的 2 种组合得靠 else 兜住。

  两种写法在各件事上的代价：

    要做的事              查表        if 堆
    ----------------------------------------------
    加一个状态「两元」    加几行数据  重排判断顺序
    加一个动作「扫码」    加几行数据  到处补条件
    查「某个组合怎么办」  一次取值    顺着读完
    验证没漏组合          数表的行数  跑用例才知道
    解释给同事听          把表画出来  把代码读一遍

  这不是风格问题。表把「有哪些情况」和「怎么处理」拆开了，
  所以情况有几种能数出来，漏没漏也能看出来。

[4] 两个自动机一起跑，状态数是乘起来的

  一扇门有 2 个状态（关、开），一盏灯有 2 个状态（灭、亮）。
  要描述「门和灯同时处在什么状况」，就得用组合状态：

    关-灭  关-亮  开-灭  开-亮
    一共 2 x 2 = 4 种

  这不是巧合，是乘法。三个各 4 状态的部件凑在一起，
  组合状态就是 4 的 3 次方 = 64 种：

    1 个部件（每个 4 状态）：4 种组合状态
    2 个部件（每个 4 状态）：16 种组合状态
    3 个部件（每个 4 状态）：64 种组合状态
    4 个部件（每个 4 状态）：256 种组合状态
    5 个部件（每个 4 状态）：1024 种组合状态  ← 已经数不过来了
    6 个部件（每个 4 状态）：4096 种组合状态  ← 已经数不过来了

  所以真实的系统不会把状态摊平成一张大表，
  而是分成几个小自动机，各管一摊，只在对得上的时候对一下暗号。
  状态爆炸是有限自动机最现实的敌人。

[5] 「有限」这两个字卡在哪里

  出一道理题：一串 a 后面跟同样多的 b，比如 ab、aabb、aaabbb，
  判断「a 和 b 的个数是不是一样多」。

  自动机要判断这件事，只能靠「数到几」。可状态是有限的，
  数到第几个就得记在第几个状态里。下面真造若干台这样的机器，
  状态数从 4 试到 64，看每台最多能认多长的串：

    状态数    最长认得的 n    实际用掉
    --------------------------------------------
    4         3               4 个
    8         7               8 个
    16        15              16 个
    32        31              32 个
    64        63              64 个

  状态翻一倍，能数的长度也只翻一倍。想让它在任意长的串上都不出错，
  状态数就得是无穷大 —— 那就不是「有限」自动机了。

  实际写程序时没人真去数状态，因为程序里有个整数计数器，
  计数器能到 20 亿，等于白送了 20 亿个状态。
  自动机理论里的「有限」，说的是不许有这种计数器。

  记住这条界线就够了：能用「现在处在哪一档」说清楚的事，
  自动机都干得漂亮（词法分析、协议握手、电梯调度、游戏里的敌人 AI）；
  一旦要「记住一个数」，就轮到带栈或带内存的模型出场了。

第一段先把表摆出来。注意 TABLE.get((st, act)) 返回 None 的时候程序停住 —— 这就是「表里没写的情况」，不是错误，是设计的一部分。十二种组合只写了十行， 另外两种（该出货状态又收到硬币）按物理常识该忽略。 第二段跑两串输入。第二串里有个「退币」， 状态从「五角」回到「待机」—— 前面投的那五角等于白投，因为状态一清，历史就没了。这是自动机最要紧的性质： 记忆全在状态里，状态没了，记忆就没了。 第三段那张对照表里没有数字，但它是这一节最该记住的。 表把「有哪些情况」和「怎么处理」拆成两件事： 情况有几行、漏没漏，是数出来的；处理写在哪，是另一件事。if 堆把两件事搅在一起， 改一处得重读一遍。 第四段是乘法。2 × 2 = 4 太小儿科，但 4 的 5 次方 = 1024、4 的 6 次方 = 4096 就不是了。 真实系统的状态从来不是「设计出来的」，是「乘出来的」。 第五段是这一节的骨头。4 个状态认到 n=3，8 个认到 n=7，64 个认到 n=63。 一条直线，斜率是 1。这就是「有限」的代价：想多认一位，就得多一个状态。 最后那列「实际用掉」是给较真的人看的。每台机器都刚好用掉全部 K 个状态 —— 不是浪费， 是这种构造恰好把状态用满了。换个构造能省一些，但省不出数量级：线性就是线性。

30 秒实验

1. 在 TABLE 里加一行 (u'待机', u'扫码'): u'两元'，重跑第二段。 不用改 run，一个字都不用改 —— 这就是表驱动的好处。
2. 把第五段的 K 换成 128，看最长能认的 n。应该是 127。不信这个规律的话再试 100 —— 应该是 99。
3. 把 build 里撞到顶时返回的 None 改成 s（原地不动）。 那么它会把 a^10 b^10 在 K=8 时一路认下去、最后判错 —— 错法变了，错还是错。

常见误区

1. 以为状态机就是 if-else 换了种写法。差别不在写法，在「情况」变成了一份可数的数据。 数得出来，才能验证没漏。
2. 以为状态越多越聪明。状态是乘起来的，加一个维度可能翻几倍。 智能体设计里最常见的错误就是「再加一个状态就能解决」，结果状态空间炸了。
3. 以为「有限」是个理论玩具。一个整数计数器就是 20 亿个状态，程序员的日常早就越过了这条线。 「有限」约束的是理论模型，不是你的代码。
4. 以为自动机只能处理字符串。售货机、电梯、红绿灯、TCP 连接，都是自动机。 它的适用面是「一档一档的处境」，跟字符没关系。

自动机的下一个状态是确定的 —— 现在是这一步，下一步一定去那儿。 可现实里下一步往往是「大概去哪」。 下一节把转移表里的箭头换成概率，同一个骨架换一种读法，就成了马尔可夫模型。

• ☐ （本节完，下一节 3.3 马尔可夫模型）

相关笔记

• 人工生命模型
• 马尔可夫模型
• 状态驱动智能体
• 📘 图解人工智能 · 索引