有限状态机

What · 是什么

有限状态机(Finite State Machine, FSM)是描述'按字符逐一转移状态'的数学模型。DFA 是五元组 (Q, Σ, δ, q0, F)：有限状态集、字符集、转移函数、起始状态、接受状态集。DFA 接受的语言恰为正则语言；NFA 与其等价(幂集构造)。竞赛应用：判断二进制数奇偶/偶长串、KMP 自动机、AC 自动机(Trie+失配链接)、后缀自动机、序列自动机、DP 套 DP(内层 DP 状态建自动机外层 DP 计数)。

Why · 为什么

How · 实现

伪代码

# 一般 DFA 模拟
def run_dfa(delta, q0, accept, s):
  q = q0
  for ch in s:
    q = delta[q][ch]
  return q in accept

# 例: 判断二进制串是否为偶数(从左到右, 末位决定)
# 状态 0: 已处理前缀对应偶数, 状态 1: 奇数
# 转移: 读0偶数保持偶, 读1变奇; 奇读0变偶, 奇读1保持奇

Python 实现

def is_even_binary(bits):
    """DFA 判定二进制串是否表示偶数。
    状态 q=0 表示当前前缀是偶数, q=1 表示奇数。
    """
    q = 0
    for ch in bits:
        if ch not in '01':
            raise ValueError('非法字符')
        if q == 0:
            q = 0 if ch == '0' else 1
        else:
            q = 0 if ch == '0' else 1
    return q == 0


def build_kmp_automaton(pattern):
    """构造 KMP 自动机。
    状态 i 表示已匹配 pattern 前 i 个字符;
    delta[i][c] 为读入 c 后应到的状态。
    用失配函数实现(简化版)。
    """
    m = len(pattern)
    # 前缀函数
    pi = [0] * m
    for i in range(1, m):
        j = pi[i - 1]
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    # 字符集
    alpha = set(pattern)
    delta = {i: {c: 0 for c in alpha} for i in range(m + 1)}
    for i in range(m + 1):
        for c in alpha:
            if i < m and c == pattern[i]:
                delta[i][c] = i + 1
            elif i == 0:
                delta[0][c] = 0
            else:
                delta[i][c] = delta[pi[i - 1]][c]
    return delta, m


def kmp_count(text, pattern):
    """用自动机统计 pattern 出现次数(含重叠)。"""
    delta, m = build_kmp_automaton(pattern)
    q = 0
    cnt = 0
    for ch in text:
        if ch in delta[q]:
            q = delta[q][ch]
        else:
            q = 0
        if q == m:
            cnt += 1
    return cnt


if __name__ == '__main__':
    # 二进制偶数判定
    assert is_even_binary('0') is True
    assert is_even_binary('1') is False
    assert is_even_binary('1010') is True
    assert is_even_binary('101') is False
    assert all(is_even_binary(f'{i:b}') == (i % 2 == 0) for i in range(30))

    # KMP 自动机计数
    assert kmp_count('aaaa', 'aa') == 3
    assert kmp_count('ababcabab', 'ab') == 4   # 位置 0,2,5,7
    assert kmp_count('abc', 'def') == 0
    assert kmp_count('abcabc', 'abc') == 2
    assert kmp_count('abcababcabc', 'abc') == 3  # 位置 0,6,8(重叠)

    print('binary even check (0..29): OK')
    print('kmp automaton counts:')
    print('  aaaa/#aa  =', kmp_count('aaaa', 'aa'))
    print('  ababcabab/#ab =', kmp_count('ababcabab', 'ab'))
    print('  abcabc/#abc= ', kmp_count('abcabc', 'abc'))
    print('All fsm tests passed!')

易错点

• 自动机是模型不是算法: 描述时需明确转移表与失配状态, 别漏未定义字符的转移
• KMP 自动机要处理失配回退: 未定义转移在竞赛中常加一个显式 fail 状态
• DFA 计算复杂度 O(n) 但转移表空间 O(S|Σ|); 字符集大时用 dict 稀疏存储
• NFA 多分支必须并行维护状态集, 勿用单状态直接模拟
• DP 套 DP 的'内层DP状态'是外层状态, 构造前先确认状态上界避免指数爆炸

例题

信源

• OI Wiki✓ https://oi-wiki.org/misc/fsm/
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/misc/fsm.md
• web✓ https://en.wikipedia.org/wiki/Finite-state_machine