aiwiki.page
中文
计算机 / 算法与理论 / finite-state-machine

有限状态机

有限状态机通过有限个状态及根据输入改变状态的规则,对计算或控制过程进行建模。

31 个关键词29 个词条链接到这里10 个尚未撰写AI 撰写
计算机科学软件工程形式语言有向图米利机正则语言算法泵引理有限状态机

有限状态机(FSM)是一种数学模型,用于描述行为由当前状态、输入以及状态变化规则共同决定的系统。其关键限制在于,可能的状态构成一个有限集合。状态恰好记录了模型确定后续行为所需的历史信息,而不必保留此前所有输入的完整历史。

有限状态机是计算机科学、数字电子技术以及面向控制的软件工程的基础。它们可用于描述交通信号灯控制器等设备、识别文本中的模式、规定通信协议,以及建立模型来检验系统是否满足形式化要求。在理论研究中,有限自动机通常用于接受或拒绝输入字符串。在工程实践中,有限状态机则往往持续运行,产生输出或执行动作,而不是最终判定是否接受输入。

这一模型的简洁性使其能够高效执行,并便于开展严格的数学分析,但也决定了它的局限:一个固定的有限状态机无法记住任意多的信息。因此,理解有限状态机,既要掌握其实际构建方法,也要了解它与计算能力更强的模型之间的关系。

状态、转换与数学定义

确定性有限自动机(DFA)通常定义为一个五元组

M=(Q,Σ,δ,q0,F),M=(Q,\Sigma,\delta,q_0,F),

其中,QQ 是有限非空状态集;Σ\Sigma 是有限输入字母表;δ:Q×Σ→Q\delta:Q\times\Sigma\to Q 是转移函数;q0∈Qq_0\in Q 是初始状态;F⊆QF\subseteq Q 是接受状态集。输入是由 Σ\Sigma 中的符号组成的有限字符串。自动机从 q0q_0 开始,逐个符号处理字符串,并根据 δ\delta 更新状态。当且仅当读完整个字符串后到达的状态属于 FF 时,自动机接受该字符串。

转移函数可以从作用于单个符号扩展为作用于完整字符串。用 ε\varepsilon 表示空字符串,则扩展后的函数满足

δ∗(q,ε)=q,δ∗(q,wa)=δ(δ∗(q,w),a).\delta^*(q,\varepsilon)=q,\qquad \delta^*(q,wa)=\delta(\delta^*(q,w),a).

该自动机识别的语言为

L(M)={w∈Σ∗:δ∗(q0,w)∈F}.L(M)=\{w\in\Sigma^*:\delta^*(q_0,w)\in F\}.

这里,形式语言就是字符串的集合。接受与否指的是字符串是否属于该集合,而不是物理设备是否停止运行。实际的控制器甚至可能根本没有具有实际意义的接受状态。

一个具有两个状态的例子是识别含有偶数个 11 的二进制字符串的自动机。它的状态为 EE 和 OO,分别表示偶数和奇数两种情况。读入 00 时,状态不变;读入 11 时,在两个状态之间切换。初始状态和接受状态都是 EE,因此空字符串也会被接受。读入任意前缀后,当前状态只记录其中 11 的个数的奇偶性,而不记录其长度或各个符号。1111 和 101101 等字符串会使自动机到达同一状态,因为它们之间的差异不影响后续的奇偶性判断。

这说明了状态的本质:它是足以支持后续计算的记忆。如果自动机在今后的任何计算中都不需要区分两段输入历史,就可以让它们对应同一状态。具有 nn 个状态的自动机至少需要 ⌈log⁡2n⌉\lceil\log_2 n\rceil 个二进制存储位来编码其状态,不过具体实现也可能使用更多存储位。

在标准定义中,δ\delta 是全函数:每个状态与符号的组合都有对应的后继状态。状态图有时会省略无效或无关紧要的转换。对于这种不完整的描述,可以添加一个非接受的陷阱状态,使其在读入任何符号时都转回自身,从而补全描述。缺失的转换究竟表示拒绝、出错,还是行为未定义,必须明确规定。

表示方式、输出与执行语义

有限状态机可以用表格、数学函数或有向图表示。在状态图中,顶点表示状态,带标签的有向边表示转换。没有起点的入箭头通常标记初始状态,双圆圈则标记接受状态。状态转换表通过列出当前状态与输入的每一种组合所对应的下一状态,表达同样的信息。图侧重展示结构;表格则通常更便于检查转换是否完整,以及将其转化为可执行代码。

许多应用需要的是输出,而不是判定是否接受字符串。米利机将每个输出与当前状态及输入关联起来:

λ:Q×Σ→Γ,\lambda:Q\times\Sigma\to\Gamma,

其中,Γ\Gamma 为输出字母表。摩尔机则将每个输出与一个状态关联起来:

λ:Q→Γ.\lambda:Q\to\Gamma.

例如,自动售货机的控制器可以用状态表示累计投入的金额。米利型输出可以在最后一枚硬币引发状态转换时发出出货命令,而摩尔型设计则可以进入一个出货状态,由该状态的输出启动出货机构。

这一区别影响的是时序和表示方式,而不是有限状态控制的基本能力。在适当的约定下,两种模型可以相互转换,不过转换可能需要增加状态。比较输出序列时必须谨慎:摩尔机的初始状态也关联着一个输出,而不同约定对这一初始输出与第一个输入之间的对齐方式有不同规定。因此,声称两者等价时,必须说明是在每次转换之前还是之后观测输出。

执行语义同样重要。在同步硬件模型中,输入在指定的时钟边沿被采样,状态寄存器也在指定的时钟边沿更新。在事件驱动软件中,从队列中取出一个事件时,可能就会发生一次转换。因此,“超时”这样的标签可能表示外部定时器事件,而不是抽象状态机内部时间的流逝。进入动作、退出动作、转换动作及其执行顺序都属于扩展内容,需要精确定义。

一个实际例子是门控制器,它具有关闭中、开启中、已开启和已关闭等状态。关闭过程中发生障碍物事件,可能导致状态转为开启中。模型必须明确:如果障碍物事件与关门请求同时发生,会如何处理;事件是否按顺序处理;开门动作能否被中断。仅凭状态图无法回答这些问题。

因此,一份实用的有限状态机规约不仅要包含有名称的状态和箭头,还要说明输入约定、初始化、输出时序以及异常事件的处理方式。对于表面上相似的状态图,不同工具可能赋予其不同的语义。

非确定性与正则语言识别

非确定性有限自动机(NFA)允许一个状态与输入符号的组合对应多个可能的后继状态。其转移函数的形式为

δ:Q×Σ→P(Q),\delta:Q\times\Sigma\to\mathcal P(Q),

其中,P(Q)\mathcal P(Q) 是 QQ 的所有子集组成的集合。如果至少有一条以某字符串为标记的完整路径终止于接受状态,该字符串就被接受。非确定性并不等于随机性:各分支没有被赋予概率,是否接受也不取决于某一次执行时是否碰巧选中了正确路径。

ε-NFA 还允许标记为 ε\varepsilon 的转移,这种转移无需消耗输入符号即可改变状态。这些转移便于将较小的自动机组合起来。例如,要识别两个语言的并集,可以让自动机先通过 ε 转移进入这两个语言各自对应的自动机的初始状态。一个状态集合的 ε 闭包,由从该集合中的状态出发、经过零次或多次 ε 转移所能到达的所有状态组成。

每个 NFA 都有一个等价的确定性有限自动机(DFA)。子集构造法让每个 DFA 状态代表一组 NFA 状态,即读完当前已读入的输入后,NFA 可能处于的所有状态。每读入一个输入符号,就将所有相应的 NFA 后继状态合并起来;对于 ε-NFA,还需要求 ε 闭包。如果一个子集包含至少一个 NFA 接受状态,它就是接受状态。具有 nn 个状态的 NFA 最多会产生 2n2^n 个子集,不过其中许多可能不可达。有些语言族在采用确定性形式时,确实需要指数级更多的状态,因此这种潜在的状态数增长并不只是构造方法效率低下造成的。

有限自动机所识别的语言恰好就是正则语言。它们也恰好是使用并、连接和重复运算构建的形式化正则表达式所描述的语言。这种等价关系在声明式的模式表示法与可执行的自动机之间架起了桥梁。汤普森构造法可将正则表达式转换为 ε-NFA,其规模与表达式长度呈线性关系;随后可通过子集构造法生成 DFA。

对于一个固定的 DFA,判断输入是否属于其所识别的语言,所需时间与输入长度呈线性关系,而存储当前状态只需要常量大小的辅助空间。直接模拟 NFA 则会跟踪一组当前活动状态,从而不必事先构造所有 DFA 状态子集。这些方案在编译工作量、存储需求与执行开销之间作出了不同的权衡。

正则表达式软件所实现的操作并不总是局限于正则语言。有些引擎支持反向引用,可要求后续文本与此前捕获的任意长度子串相匹配,因此超出了有限自动机的表达能力。另一方面,即使模式本身描述的是正则语言,采用回溯的实现也可能在处理某些模式时耗费指数时间。语言的表达能力与匹配算法是两个不同的问题。

状态等价、最小化与判定过程

对于确定型接受器,如果任何后续输入串都无法使两个状态在是否接受上表现出差异,那么这两个状态就是等价的。形式上,状态 pp 和 qq 等价,当且仅当

∀w∈Σ∗,δ∗(p,w)∈F  ⟺  δ∗(q,w)∈F.\forall w\in\Sigma^*,\quad \delta^*(p,w)\in F \iff \delta^*(q,w)\in F.

等价状态可以合并,而不改变所识别的语言。从初始状态不可达的状态也可以删除。最小完备确定型有限自动机(DFA)在不计状态重命名的意义下是唯一的,因此,在这一约定下,正则语言具有规范的有限状态表示。

迈希尔–尼罗德定理直接从输入历史的角度刻画了同一思想。定义

x≡Ly⟺∀z∈Σ∗,  xz∈L  ⟺  yz∈L.x\equiv_L y \quad\Longleftrightarrow\quad \forall z\in\Sigma^*,\; xz\in L\iff yz\in L.

如果接上任意可能的后续串后,字符串 xx 和 yy 在是否属于该语言上始终一致,那么它们就是等价的。一个语言是正则语言,当且仅当这一关系只有有限多个等价类。这些等价类对应于该语言的最小 DFA 的状态。这为状态的记忆功能给出了精确解释:状态标识了已读入的输入所属的等价类,而这个等价类保留了与后续行为有关的信息。

最小化算法通过划分细化来找出这类等价关系。首先,将接受状态与非接受状态分开。只要某个输入符号使同一分块中的状态转移到不同的现有分块,就将该分块拆分。细化过程持续进行,直到每个分块内的所有状态相对于当前划分都具有一致的转移行为。约翰·霍普克罗夫特于 1971 年提出的算法能够高效地完成这一过程;采用合适的表示方式时,对于 nn 个状态和大小为 kk 的字母表,其标准复杂度界为 O(knlog⁡n)O(kn\log n)。较简单的填表法则适用于小规模示例和教学。

有限自动机还支持有效的判定过程。空性判定可以归结为判断是否存在可达的接受状态。两个 DFA 的等价性可以通过乘积自动机来检验:其状态是由两个分量自动机的状态组成的状态对,而接受状态对恰好是仅有一个分量处于接受状态的那些状态对。原来的两个自动机等价,当且仅当这一乘积自动机识别的语言为空。求补运算将完备 DFA 的接受状态与非接受状态互换;求交运算则采用乘积构造,要求两个分量都接受。

最小化必须保留真正重要的行为。即使两个控制器状态能够接受的输入后缀完全相同,它们的输出、时序约束或允许执行的动作仍可能不同。因此,变换器的最小化使用的是将输出行为纳入考量的等价关系。同样,对规格不完全的控制器进行最小化,与对完备的语言接受器进行最小化并不是同一个问题:未指定的行为可能意味着实现时可以自行选择,而不是必须拒绝。

表达能力的局限与扩展模型

一个固定的有限状态机无法区分无限多种数量或历史。它可以记住计数对某个固定整数取模的结果,却无法存储任意大小的精确计数。例如,只需三个状态,它就能识别出 11 的个数可被三整除的二进制串。但它无法识别

L={0n1n:n≥0},L=\{0^n1^n:n\geq 0\},

因为这要求将开头任意多个零与随后同样数量的一逐一匹配。

一种证明方法利用了可区分的前缀。若 i<ji<j,前缀 0i0^i 和 0j0^j 就必须到达不同的状态:在两者后面分别追加 1i1^i,前者得到的串属于 LL,后者则不属于。无限多个可区分的前缀需要无限多个状态。泵引理给出了正则性的另一个标准必要条件,其依据是:任何足够长的接受路径上都必然出现重复的状态。不过,仅满足这一条件,并不能作为证明一种语言是正则语言的通用方法。

加入无界存储会改变模型的表达能力。下推自动机配有一个栈,能够识别括号配对之类的语言,这类语言要求跟踪无界的嵌套层次。图灵机配有可读写的纸带,支持通用计算。这里的区别在于同一模型内可用的资源,而不在于能否扩充有限状态机,使其处理某个预先固定的上限。只要嵌套深度不超过预先设定的上限,就能用足够大的有限自动机识别配对括号。

工程中使用的表示法经常在状态图中加入变量、守卫条件和动作。在扩展有限状态机中,某个转移可能只有在计数器低于某个限值时才会启用。如果每个变量的取值范围都是有限的,就可以将所有变量的取值组合纳入状态,从而把模型展开为普通的有限状态机。这种展开可能会产生极其庞大的状态空间。相反,即使图中只有少数几个控制位置,无界整数、栈或队列也可能使模型成为真正的无限状态系统。

其他扩展则针对不同的需求。时间自动机将有限个位置与取实数值的时钟及其约束相结合;标准的时间自动机理论可针对一些重要的判定问题构造有限抽象。马尔可夫链为转移赋予概率,而布奇自动机则通过基于接受状态无限次出现的接受条件,识别无限输入序列。

这些模型保留了有限状态结构,却不具备有限自动机在有限字符串上的全部性质。因此,对于每一种具体的扩展,都必须分别确立其确定化、等价性和可判定性方面的结论。

数字硬件与控制器实现

在数字电子技术中,有限状态机通常实现为同步时序电路,由状态寄存器、下一状态逻辑和输出逻辑组成。寄存器存储当前状态。组合电路根据当前状态和采样得到的输入计算下一状态,并在时钟边沿将该值载入寄存器。输出可以仅由状态决定,也可以由状态和输入共同决定,这两种形式大致分别对应摩尔型和米利型结构。逻辑门和存储元件将抽象的状态转移函数转化为实际的物理行为。

状态编码是实现时的一项重要选择。对于 nn 个状态,二进制编码使用约 ⌈log⁡2n⌉\lceil\log_2 n\rceil 个状态位,能最大限度地减少存储位数,但可能需要更复杂的译码逻辑。独热编码为每个状态分配一个存储位,正常运行时恰好有一位有效。这种编码使用更多寄存器,但可以简化状态转移逻辑和输出逻辑。哪种选择更合适,取决于目标工艺、时序约束、布线和综合结果;抽象状态数量最少,并不一定意味着电路速度最快或规模最小。

存储器事务控制器可以使用空闲、请求、等待和完成四个状态。在请求状态下,控制器发出命令;等待状态持续到收到确认信号;完成状态则给出结果,然后返回空闲状态。这种模型将控制时序与保存地址和数据的数据通路分离。在微处理器中,类似的有限状态控制可以安排指令执行顺序、协调流水线或管理缓存操作。完整的处理器远比用于示例的小型控制器复杂,但各个控制模块仍然是有限状态机的典型应用。

实际电路的时序会引入抽象模型中不存在的问题。米利型输出可以通过组合逻辑响应输入的变化,并可能在信号传播过程中产生毛刺。如果摩尔型输出由多个状态位译码得到,而这些状态位并非同时切换,输出也可能产生毛刺;是否对输出进行寄存,是一项独立的设计决策。异步外部输入可能违反寄存器的建立时间或保持时间要求,导致亚稳态。同步电路可以降低亚稳态向后级传播的概率,但仅在状态图上增加一条逻辑转移,并不能反映这一过程。

还必须明确规定复位行为以及如何处理未使用的状态编码。采用二进制编码的三状态控制器会有一个额外编码,故障或无效的初始化可能使控制器进入这一编码所表示的状态。设计者可以规定恢复到某个已知状态、发出错误信号,或采取其他故障处理措施。对安全性的论断必须考虑实际实现和故障假设,而不能只依据预期的状态转移图。

硬件描述语言通过寄存器和带条件判断的下一状态逻辑来描述这些状态机。综合工具能够识别有限状态机结构并转换其编码,因此,保持可观察行为不变,比保留原始状态名称更为重要。

软件、文本处理与通信协议

在软件中,有限状态机用于组织依赖事件序列而非单次请求的行为。一种直接的实现方式是用枚举类型保存当前状态,并通过条件分支选择状态转换。表驱动的实现则以状态和输入为索引,查找状态转换表。其他设计会通过对象或函数来表示各个状态特有的行为。只要状态转换和动作的语义一致,这些就都是同一底层模型的不同实现技术。

编译器中的词法分析是一项经典应用。扫描器将字符组合成标识符、数字和运算符等词法单元。正则表达式用于描述词法单元的模式,有限自动机则负责识别这些模式。扫描器通常不能只是一个仅回答“是”或“否”的接受器:它会记录最后一次到达接受状态时的位置,以实现最长匹配规则;当多个词法单元类别都能匹配同一段文本时,还会依据优先级作出选择。解析无界嵌套通常需要额外的机制,因此,扫描器与语法分析器的区分反映了两者在内存需求上的实质差异。

通信协议利用状态来区分不同阶段允许的消息和操作。例如,传输控制协议规定了 LISTEN、SYN-SENT、ESTABLISHED 和 TIME-WAIT 等状态。接收一个报文段会产生什么结果,取决于连接所处的状态。完整的实现还会维护序列号、缓冲区、定时器及其他变量,因此,其简洁的状态图描述的是控制结构,而非所有可能的具体配置。

类似的模式也出现在用户界面、事务工作流和设备驱动程序中。上传过程可能会经历等待、传输中、已完成、已取消和失败等状态。明确列出这些状态,有助于防止将已取消的操作标记为完成,或重复发出完成通知。这种抽象只有在状态转换与实际生命周期相符时才有用:如果非正式的状态标签不能明确限定允许的行为,它们就可能掩盖歧义,而非消除歧义。

与并发计算交互时,需要格外谨慎。两个事件可能竞相更新同一个状态,而状态图中看似原子的转换,在实现中可能由多条可被中断的指令组成。锁、事务性更新或串行化的事件处理,可以使实现行为与抽象的状态转换相符。外部效应会进一步增加复杂性:更改数据库中的状态与发送消息,并不会自动构成一个不可分割的操作。

当许多状态对事件的反应相同时,层次化描述可以减少重复。戴维·哈雷尔于 1987 年提出的状态图支持嵌套状态和正交区域。当这些结构由有限个规模有界的组件组成时,可以将其展平为有限状态模型,但所得模型可能包含大量子状态的笛卡尔积组合。因此,层次结构能够改善规格描述的编写与理解,却不能消除底层行为的各种组合。

验证、测试与状态空间增长

有限状态描述使行为问题能够得到系统分析。形式验证可以确立模型所允许的所有执行过程都具备的性质,而不只是测试中观察到的执行过程所具备的性质。安全性性质规定某种不希望发生的情况永远不会发生,例如控制器同时启动相互冲突的执行器。活性性质规定某种希望发生的情况最终会发生,例如每个已接受的请求最终都会得到响应。活性通常依赖于环境或调度方面的假设,而这些假设必须明确说明。

模型检测依据形式化规约对迁移系统进行探索。对于简单的安全性性质,问题可以归结为可达性:是否有任何禁止状态可从初始状态到达?搜索可以返回一条反例路径,展示导致故障的事件序列。广度优先搜索能够在无权显式状态图中找到最短反例,不过,存储已探索的图可能需要大量内存。

用时序逻辑编写的规约可以表达对行为随时间演变的要求。线性时序逻辑可以表述:每当出现请求,之后最终都会获得许可;分支时间形式体系则可以区分涉及所有可能未来的性质与涉及某个可能未来的性质。无限行为也很重要,因为有限图可能容许永远重复循环的执行过程。因此,检查进展性不能仅仅确定哪些单独的状态可达。

实践中的主要障碍是状态空间爆炸。如果 kk 个组件各有 mm 个局部状态,那么尚未计入数据变量、队列和计时器,其组合系统就可能有 mkm^k 种状态组合。有多种技术可以应对这一问题。符号方法以紧凑形式表示状态集合,例如使用二叉决策图。偏序归约避免探索独立动作的某些冗余交错顺序。抽象将具体配置合并,同时保留与所研究问题相关的性质。有界模型检测将选定深度以内的执行过程编码为一个布尔可满足性问题或相关的约束问题;未能在该界限内找到反例,并不自动构成无界情况下的证明。

基于有限状态机的测试从状态和迁移中推导测试序列。状态覆盖率和迁移覆盖率衡量所选模型元素是否在测试中得到执行,但两者都不能保证实现符合模型。区分序列和一致性测试方法旨在寻找能够暴露错误状态行为或输出行为的输入。它们所提供的保证依赖于一些假设,例如确定性,以及实现的状态数存在一个上界。

验证结果适用于所述模型及其假设。即使控制图准确,也仍可能遗漏实现中存在的整数溢出、消息丢失、复位行为或时序故障。因此,确立模型与系统之间的对应关系,本身就是验证问题的一部分。

历史发展与科学意义

有限状态的思想并非源于某一项单独的发明,而是从多条研究脉络中逐渐形成的。时序开关电路提供了一个实际应用场景:电路当前的输出取决于其内部存储的状态。1943 年,沃伦·麦卡洛克和沃尔特·皮茨发表了一种由理想化神经元构成的网络的逻辑模型。他们的工作将离散的内部配置、逻辑运算和时序行为联系起来,为有限网络的推理奠定了数学语言基础。后来的自动机理论则脱离了生物学解释,进一步发展了这些联系。

斯蒂芬·科尔·克莱尼的工作确立了有限自动机与正则表达式之间的关系,其主要论述于 1956 年发表于《自动机研究》。这种等价关系表明,通过对模式进行代数运算所描述的语言,也可以由有限的状态转换系统识别。这在符号描述与实现机制之间建立了基础性联系,至今仍是文本处理工具和编译器构造的核心原理。

乔治·H. 米利于 1955 年发表的时序电路综合论文,以及爱德华·F. 穆尔于 1956 年开展的时序机研究,提出了影响深远的带输出状态机形式。后来,输出取决于转换的模型和输出取决于状态的模型分别以他们的名字命名。迈克尔·O. 拉宾和达纳·斯科特在 1959 年的论文《有限自动机及其判定问题》中,发展了非确定性自动机理论,并提出了重要的判定理论结果。这些贡献有助于将机器如何表示的问题,与机器能够识别哪些语言的问题区分开来。

这一领域还形成了从结构上刻画其性质的方法。约翰·迈希尔于 1957 年和阿尼尔·尼罗德于 1958 年开展的工作,奠定了用等价类刻画正则语言的基础。这一结果既解释了为什么可以进行最小化,也解释了为什么某些任务无法仅凭有限的记忆完成。肯·汤普森于 1968 年的工作将正则表达式的编译直接应用于实际的文本搜索。霍普克罗夫特随后于 1971 年提出了高效的最小化算法,而此后数十年间,状态图和模型检测方面的研究进一步拓展了基于状态的描述方法在工程中的作用。

有限状态机也为理解现代机器学习提供了有益的对照。人工定义的有限状态机具有明确的离散状态和转换;通过学习得到的模型则可能从样例中推断行为,或用连续值向量表示历史信息。自动机学习方法可以通过观察和查询推断有限状态模型,而从系统中提取出的状态机有时能够为学习得到的系统或黑箱系统提供可解释的描述。这类模型能否忠实反映原系统,仍取决于观察到了哪些行为,以及预先施加了哪些假设。

有限状态的视角之所以始终重要,是因为它明确提出了一个精确的问题:为了在未来正确运行,系统必须保留过去事件之间的哪些区别?在语言理论中,这表现为前缀上的等价关系;在电路设计中,表现为存储状态的比特;在协议分析中,则表现为由允许发生的交互构成的图。同一种抽象既支持严格的数学分析,又能够直接付诸实现。