有限状态自动机

自动机读过前缀后不会保存原文，只留下一个足以继续判断的摘要。状态名应回答“关于过去，未来还需要知道什么”，而不是机械记录“刚才读了哪个字符”。奇偶性、固定模数、最长相关后缀和协议阶段都只有有限多种摘要，因此适合有限状态；一个必须在未来原样取回的无界计数则不适合。

有限状态的限制不是运行时间短，而是记忆种类固定。自动机可以在一个长输入上执行任意多步，也可以反复经过环；无论输入多长，它在任一时刻只能从有限个控制状态中选取当前摘要。正是环让有限图能够描述无限多个字，有限并不意味着语言有限。

图表示尤其直观：节点是状态，带符号的边是一次读取，入箭头标初态，双圆标接受态。图只是五元组的可视化；布局距离、边的弯曲和状态名称都不影响语言。真正可观察的是哪些带标签路径从初态通向接受态。

考虑一个简化连接协议，事件字母表为

状态可以取 idle、open、closed 和 error。只有在 idle 读到 connect 才进入 open，open 中可以反复 send，读到 close 后进入接受态 closed；其他次序进入 error。这台机器不必记住发送了多少次，只需记住会话位于哪个阶段，因此接受任意长但顺序合法的事件字。

例如 connect send close 的运行是 idle → open → open → closed，读完时接受；connect close send 则先到 closed，随后落入 error，最终拒绝。接受态表达“如果输入现在结束便合格”，不代表后续字符可以忽略。为使规范完整，closed 上所有事件都进入 error，error 上所有事件都自环。

若规范改成“close 前的 send 次数必须等于连接时声明的任意整数”，状态就必须保存一个无界数，有限状态模型不再足够。若声明值只取 $0$ 到 $255$，仍可用有限状态实现，只是状态数可能很大；分界是记忆上界是否与输入长度无关，而不是图画起来是否方便。

工程中的“finite-state machine”有时指没有接受集合的控制器，或带输出的 Moore、Mealy 机。本页讨论的是读取完整有限字后以终态判定成员资格的接受器。加入栈、计数器、实值时钟或可写磁带都会改变配置空间，不能把这些额外存储算作一个“名字复杂的有限状态”。

输入若是无限字，也没有“读完后检查终态”的时刻。Büchi 等 $\omega$-自动机改用某些状态在无限运行中反复出现之类的接受条件；它们仍有有限控制图，却识别 ${\mathrm{\Sigma }}^{\omega }$ 上的语言，而不是本页的 ${\mathrm{\Sigma }}^{\ast }$。

输入若具有分叉层次，有限树自动机公理库有限树自动机Finite tree automaton · Bottom-up tree automaton · NFTA有限有序树上的状态汇总支持确定化、空性和语言差判定；可达闭包寻找有限运行，按节点数的动态规划构造最小反例树，并区分树与共享DAG的大小。让父节点汇总有序孩子的状态，从而识别整棵有限树。它保留有限状态与存在接受运行的思想，但接受条件放在根上，叶规则承担初始化。

有限状态模型把词法规则、固定模式搜索、有限协议监控与硬件控制统一为同一种带标签图。DFA 适合直接执行和取补，NFA 适合组合候选路径，二者之间可通过子集构造转换；选择表示影响大小与运行方式，不改变可识别语言。

经典正则表达式公理库正则表达式Regular expression从空语言、空字与单符号语言出发，经并、连接和 Kleene 星有限构造的语言表达式。与有限自动机在“能够描述哪些有限字语言”这一层面等价：表达式提供组合语法，自动机提供逐步运行语义。模型间的翻译保留语言，表示大小则可能显著变化。