有限状态自动机

共同骨架 ​

有限状态自动机由有限状态集 $Q$、输入字母表 $\mathrm{\Sigma }$、初态 $q_0\in Q$、接受状态集 $F\subseteq Q$ 与带输入标号的转移结构组成。把转移先写成关系

$$\mathrm{\Delta }\subseteq Q\times \mathrm{\Sigma }\times Q,$$

就能同时容纳确定与非确定版本。对字公理库字Word · String从某个有限位置集到字母表的函数，即有限符号序列。 $w=a_1\cdots a_n$，一条运行是状态序列

$$q_0,q_1,\dots ,q_n,(q_{i-1},a_i,q_i)\in \mathrm{\Delta }.$$

若存在一条运行终止于 $F$，自动机接受 $w$。DFA公理库确定性有限自动机Deterministic finite automaton · DFA具有有限状态、总转移函数并逐符号读取输入的确定性计算模型。要求每个 $(q,a)$ 恰有一个后继；NFA公理库非确定性有限自动机Nondeterministic finite automaton · NFA转移可同时给出多个后继状态的有限状态机。允许零个、一个或多个后继。两者共享有限状态、逐符号读取和终态接受这副骨架，但转移的量词不同。

直觉 ​

读到输入前缀后，自动机不会保留整段历史，只把后续判断仍需知道的信息压缩成当前状态。状态集有限，意味着这种摘要的种类不随输入长度增长：它能记住奇偶性、长度模数、有限后缀或协议阶段，却不能精确保留一个任意大的计数。

把本页理解成一张有限的带标号控制图，比把它预先等同于 DFA 更稳妥。确定性规定每一步只有一条路，非确定性允许同时保留多条候选路径；“有限状态”本身只约束记忆容量，并不替其中任何一种运行语义作选择。

例子与边界 ​

要识别二进制字中 1 的个数是否为偶数，只需“偶”和“奇”两个状态。每读到 0 留在原状态，每读到 1 切换状态，初态与接受态都是“偶”。这里转移恰好唯一，所以它是一台 DFA，也自然属于本页描述的有限状态模型。

模式匹配常更适合先画成 NFA：在读到可能的模式起点时分出一条候选路径，只要某条路径完整匹配便接受。两种表示都不能获得无界存储；语言 $\{0^n{1}^n:n\ge 0\}$ 需要记住任意大的 $n$，因此任何固定有限状态集最终都会混淆两个不同计数。

“有限状态机”在工程里还可指没有接受集合的控制器，或带输出的 Moore、Mealy transducer。本页讨论的是读取有限字并以终态判断接受的 automaton。若输入是无限字，则需要 Büchi 等 $\omega$-自动机另行规定接受条件；若转移带时钟、栈或寄存器，新增的存储也会改变模型能力。

推论与应用 ​

DFA 与 NFA 识别同一类正则语言公理库正则语言Regular language能被某个有限自动机识别的形式语言。，但表示大小可能相差指数级；具体的子集构造见DFA–NFA 等价定理公理库DFA–NFA 等价定理DFA–NFA equivalence · Subset construction每个 NFA 都可由识别同一语言的 DFA 模拟。。正则表达式、词法分析器、有限协议监控和硬件控制器都可落到有限状态图上，随后再根据执行需求选择确定化、按位并行模拟或保持非确定表示。

有限状态控制也可作为更强模型的离散外壳：下推自动机公理库下推自动机Pushdown automaton · PDA带无界栈存储的有限控制自动机。在其上增加栈，时间自动机增加实值时钟。共同骨架帮助比较模型，但不能把这些扩展的额外存储重新算作“有限状态”。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Chapter 1.
• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Chapters 1–2.