有限状态自动机

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

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

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

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

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

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

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

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

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

经典正则表达式公理库正则表达式Regular expression从空语言、空字与单符号语言出发，经并、连接和 Kleene 星有限构造的语言表达式。与有限自动机在“能够描述哪些有限字语言”这一层面等价：表达式提供组合语法，自动机提供逐步运行语义。这一限定见证的是表达能力，不是说一个表达式就是一台机器，也不保证双向翻译保持表示大小。