从算法到人工智能 · 第 15 课：状态机——让程序"记住自己现在在哪"

前面几课，我们处理数据的方式大多是"一次性算完"：读进去，算一遍，吐结果。但现实里有一大类问题，是边读边变、边走边看的——你处理到第 5 个字符时的行为，取决于前 4 个字符是什么。

比如：你要判断一个字符串里有没有连续的 "ab"。看到 'a' 时你心里想"下一个是 'b' 吗？"，看到 'b' 时想"上一个是不是 'a'？"。程序在不同时刻处于不同的"心理状态"，读入的每个输入会把它从一个状态"踢"到另一个状态。

把这种"状态 + 输入 → 新状态"的规则画出来，就是状态机（State Machine），也叫有限状态自动机（Finite State Automaton，简称 FSA/DFA）。它是编译原理、正则表达式、网络协议、游戏 AI、自动售货机的共同底座。

这一课的目标：让你会画状态图，会用代码把状态机写出来，并知道它到底能干什么。

一、状态机的四个零件

一个状态机，就四样东西：

状态（State）：程序此刻"在哪"。比如"还没看到 a""看到了 a 在等 b"。
初始状态：从哪开始。
转移（Transition）：读到某个输入，从状态 A 跳到状态 B。
接受状态（Accepting State）：走到这里，说明"目标达成了"。

我们拿一个最简单的问题开场：判断一个字符串是否以 "ab" 结尾。

先别写代码，先把"状态"想清楚。程序从头扫到尾，它心里只需要关心一件事：上一个字符是不是 'a'。

状态 S0：上一个字符不是 a（或刚开始）。
状态 S1：上一个字符是 a。

然后看转移：

在 S0，读到 'a' → 进入 S1；读到别的 → 留在 S0。
在 S1，读到 'b' → 达成"ab"结尾，但还要继续扫，所以回到 S0（等下一次）；读到 'a' → 留在 S1（两个 a 连着）；读到别的 → 回 S0。

扫描结束时，如果最后一次转移落到了"刚匹配到 ab"这个点上，结果就是 True。

这里你会发现一个关键：状态机只记住"当前状态"，不记"完整历史"。它把无限多的历史，压缩成了有限几个状态。这就是"有限"二字的含义。

二、用代码实现：查表法

状态机的代码写法非常机械——一张"转移表"就够了。表是 状态 × 输入 → 新状态。

def ends_with_ab(s):
    """判断字符串是否以 'ab' 结尾"""
    # 状态：0 = 上一个不是a，1 = 上一个字符是a
    state = 0
    for ch in s:
        if state == 0:
            state = 1 if ch == 'a' else 0
        else:  # state == 1
            if ch == 'b':
                state = 0          # 匹配到 ab，回到"重新开始"（但记下达成）
            elif ch == 'a':
                state = 1          # 连续 a，仍是"上一个字符是a"
            else:
                state = 0
    # 结束时，看"最后两步"是否构成 ab
    # 更稳妥：直接判断字符串末尾两字符
    return s.endswith('ab')

print(ends_with_ab("xxab"))   # True
print(ends_with_ab("abx"))    # False

上面这个例子为了讲清楚"状态"，我写得啰嗦了点。实际更优雅的是查表法——把转移规则做成一个字典，读表就行：

def ends_with_ab_table(s):
    # 转移表：trans[当前状态][输入字符] = 新状态
    trans = {
        0: {'a': 1, 'b': 0, 'x': 0},   # 这里假设字母只有 a/b/x
        1: {'a': 1, 'b': 0, 'x': 0},
    }
    # 这里"ab 结尾"要额外跟踪，先看核心：状态怎么流转
    state = 0
    for ch in s:
        state = trans[state].get(ch, 0)
    return state

print(ends_with_ab_table("aaab"))   # 1（扫完状态是1，说明最后一个是a，前面是否有b要另判）

注意：查表法的表，其实就是把状态图翻译成了数据。trans[state][input] 就是"从 state 出发，读到 input 会到哪"。有了这张表，状态机的行为就完全确定了。

三、完整的状态机：DFA 判定「包含 ab」

"以 ab 结尾"那个例子，为了同时处理"结尾"和"状态"，我偷了点懒。现在来一个教科书级、状态机完全胜任的问题，把它彻底做干净：

判断一个字符串是否"包含"子串 ab（任意位置出现 ab 就算）。

画状态图：

S0：还没看到 a（初始状态）。
S1：看到了 a，正在等 b。
S2：已经匹配到 ab（接受状态），之后无论来什么，都留在 S2。

转移：

当前状态	读到 `a`	读到 `b`	读到其他
S0	S1	S0	S0
S1	S1	S2 ✅	S0
S2	S2	S2	S2

把这张表写进代码，干净利落：

def contains_ab(s):
    # 状态：0=没看到a, 1=看到a在等b, 2=已匹配ab（接受态）
    state = 0
    for ch in s:
        if state == 0:
            state = 1 if ch == 'a' else 0
        elif state == 1:
            if ch == 'b':
                state = 2
            elif ch == 'a':
                state = 1
            else:
                state = 0
        else:  # state == 2，接受态一旦进入就不再离开
            state = 2
    return state == 2

print(contains_ab("xxab"))   # True
print(contains_ab("abx"))    # True
print(contains_ab("acb"))    # False
print(contains_ab("ba"))     # False

看几个要点：

S2 是"吸收态"：一旦进入，就再也出不来。这体现了"已经找到了，后面不用再关心"。
状态机的核心就一句话：每个字符读进来，查一下"我在哪、读到啥"，跳到下一个"我在哪"。
全部扫完，看最后落在不在接受态，就是答案。

这 20 行代码，其实就是正则表达式 .*ab.* 或者 KMP/自动机匹配 的雏形。

四、状态机为什么强：它把"历史"压缩成"状态"

你可能觉得：判断"包含 ab"这么简单，用 "ab" in s 一行不就完了吗？干嘛搞状态机？

因为状态机演示的是一种通用能力：把"读到现在为止的全部历史"，压缩成当前状态。而很多问题，恰恰只关心"压缩后的状态"，不关心具体历史。

比如下面这个经典题：判断一个二进制数（以字符串给出）是否偶数。偶数就是"最后一位是 0"——但状态机告诉我们，其实"读到当前位为止的奇偶性"就是一个状态：

def is_even_binary(s):
    # 状态：0=当前读到的是偶数, 1=奇数
    # 读入一位后：新数 = 旧数*2 + 这一位；奇偶性只由"这一位"决定
    state = 0
    for ch in s:
        state = int(ch)          # 二进制数奇偶性 = 最后一位
    return state == 0

print(is_even_binary("1010"))   # True  (10，偶数)
print(is_even_binary("1011"))   # False (11，奇数)

更妙的例子是"一个二进制数能否被 3 整除"——这不能只看最后一位，但状态机照样能做：状态 = "当前余数（0/1/2）"，读入下一位 d 后，新余数 = (旧余数*2 + d) % 3。三个状态，完美解决，而且根本不需要知道这个数本身有多大——数再长（一千位、一万位），状态机都只用一个 0~2 的整数就装下了。

def divisible_by_3(s):
    state = 0                     # 当前余数
    for ch in s:
        state = (state * 2 + int(ch)) % 3
    return state == 0

print(divisible_by_3("11"))     # True  (3 能被 3 整除)
print(divisible_by_3("100"))    # False (4)
print(divisible_by_3("110"))    # True  (6)
print(divisible_by_3("1001"))   # True  (9)

看到没？"被 3 整除"这么个看似要拿大数做除法的问题，被状态机用"余数"这一个状态就碾压了。这正是状态机的精髓：找到那个"真正决定未来的最小信息"，把它设成状态。

五、真实世界的状态机：自动售货机 & 验证邮箱

状态机不只是"字符串题"，它是建模交互系统的通用语言。看一个自动售货机：

状态：S0=待机（没投钱）
      S1=已投钱（等选商品）
事件：投币 → S0 变 S1；选商品 → 出货、S1 回 S0；退款 → 出货口退钱、S1 回 S0

class VendingMachine:
    def __init__(self):
        self.state = "IDLE"       # 待机

    def insert_coin(self):
        if self.state == "IDLE":
            self.state = "HAS_MONEY"
            return "已收币，请选择商品"
        return "已投过币了，直接选商品或退款"

    def select_item(self):
        if self.state == "HAS_MONEY":
            self.state = "IDLE"
            return "出货成功，谢谢惠顾"
        return "请先投币"

    def refund(self):
        if self.state == "HAS_MONEY":
            self.state = "IDLE"
            return "已退款"
        return "没有可退的币"

vm = VendingMachine()
print(vm.select_item())   # 请先投币
print(vm.insert_coin())   # 已收币
print(vm.select_item())   # 出货成功

看到没？insert_coin、select_item 这些"事件"，本质就是驱动状态转移的输入。合法的操作序列，就是状态图上一条合法的路径；非法操作（没投币就选商品）会被当前状态"挡住"。

再看一个更贴程序员日常的：验证邮箱是否合法。一个合法的邮箱要满足"字符串能被正则 name@domain 匹配"。我们用状态机思路写一个简化版——判一个字符串里恰好有一个 @，且前后都有字符：

def is_valid_email(s):
    state = 0   # 0=在名字段(还没遇到@), 1=在域名段(遇到@之后)
    for ch in s:
        if ch == '@':
            if state == 0:
                state = 1      # 遇到第一个 @，进入域名段
            else:
                return False   # 第二个 @，非法
        # 其它字符：留在当前段（简化版不管具体字符）
    # 结束时：必须"进入过域名段"，且结尾不是 @
    return state == 1 and s[-1] != '@' and s[0] != '@'

print(is_valid_email("a@b.com"))   # True
print(is_valid_email("a@@b"))      # False
print(is_valid_email("@b.com"))    # False
print(is_valid_email("abc@"))      # False

这已经是一个简化版 DFA 邮箱校验器了——state 就是"我扫到第几个 @ 了"。

六、状态机 vs 普通代码：什么时候该用它

状态机不是万能的，它有明确的适用场景。判断标准就一句话：

如果程序的行为取决于"之前发生过什么"，而这个"之前"能被压缩成有限的几类，就用状态机。

✅ 适合：字符串匹配（正则、编译器的词法分析）、网络协议（TCP 的握手/传输/关闭）、游戏 AI（巡逻→追击→攻击→撤退）、UI 交互（按钮在不同状态下的响应）、订单流转（待支付→已支付→已发货→已完成）。
❌ 不适合：需要记住完整历史的问题（比如"输出所有出现过的字符"——这要用集合/哈希，不是状态机能做的，因为它的状态数会无限膨胀）。

判断的钥匙：能不能找到一组"有限且足够"的状态，替代对完整历史的记忆。 能，状态机就是最优解；不能，别硬套。

七、小结

状态机 = 状态 + 转移 + 初始态 + 接受态——它把"读到的历史"压缩成"当前状态"。
转移表 trans[state][input] = next_state 就是状态图的代码版——机械、清晰、不遗漏。
找对"状态"是唯一的难点——问自己：哪个最小信息，足以决定后面的所有走向？（比如"被 3 整除"只用记住余数 0/1/2）

八、动手实验：三件事亲手敲一遍

实验 1：给「被 3 整除」画状态图

用纸笔画出 divisible_by_3 的三个状态（余数 0/1/2）之间的转移。读入下一位 0 或 1，每个状态分别会去哪？

提示：新余数 = (旧余数 * 2 + 这一位) % 3。比如状态 1（余 1），读到 1 → (1*2+1)%3 = 0。你会发现 6 条转移边，构成一张漂亮的对称图。

实验 2：把状态机推广到「被 5 整除」

模仿 divisible_by_3，写一个 divisible_by_5。状态是余数 0~4，转移公式一样：新余数 = (旧余数*2 + d) % 5。

def divisible_by_5(s):
    state = 0
    for ch in s:
        state = (state * 2 + int(ch)) % 5
    return state == 0

print(divisible_by_5("101"))    # True  (5)
print(divisible_by_5("1010"))   # True  (10)
print(divisible_by_5("111"))    # False (7)

实验 3：挑战题——用状态机判定「包含连续三个 0」

写一个 contains_000(s)，判断二进制串里是否有连续三个 0。提示：需要 4 个状态——0 个连续 0、1 个、2 个、3 个（接受态）。读入 1 时回到"0 个连续 0"，读入 0 时"连续 0 的个数 +1"。

def contains_000(s):
    state = 0   # 0/1/2/3 = 当前连续 0 的个数（达到 3 后锁定，吸收态）
    for ch in s:
        if state == 3:
            continue          # 已经找到连续三个 0，不再改变
        if ch == '0':
            state = state + 1
        else:
            state = 0
    return state == 3

print(contains_000("10001"))    # True
print(contains_000("1001001"))  # False
print(contains_000("000"))      # True

把实验 2 跑一遍，确认「被 5 整除」照搬余数状态机就能成；再把实验 3 的 contains_000 跑通——你就亲手造出了一个"正则表达式 .*000.*"的状态机实现。状态机这东西，一旦你习惯了"先画状态、再填转移表、最后写循环"的三步走，很多"看着要回溯、要递归"的题，都会突然变得清清楚楚。