有限状态机

定义

有限状态机是一种只含有限个状态的抽象计算模型。它在任一时刻处于某个确定状态，根据接收到的输入符号按转移规则跳转到另一状态。与图灵机不同，有限状态机没有可读写的存储带，记忆能力仅限于当前所处的状态。

分类与原理

有限状态机分为确定型与非确定型两类。确定型机在每个状态对每个输入只有唯一的后继状态；非确定型机则允许多个候选转移，二者在识别能力上等价。机器从初始状态出发逐个读取输入，若读完后停留在接受状态则表示输入被接受。按输出方式还可分为摩尔机与米利机。

应用

有限状态机能够识别的语言恰好是正则语言，因此被广泛用于词法分析、文本匹配与协议解析。在工程实践中，它常用于实现数字电路的控制逻辑、通信协议的状态管理、游戏角色的行为控制以及正则表达式引擎。由于结构清晰、易于实现和验证，有限状态机是软硬件设计中最常用的建模工具之一。