1 基本概念
1.1 定义
状态机是一种用于描述系统行为的抽象模型，用来刻画系统在若干状态之间，如何在外部输入或内部条件触发下发生转换。它强调“当前处于什么状态”“接收到什么事件”“下一步转到哪里”这三类信息，因此特别适合表示离散、规则明确、阶段性变化的过程。
在形式化研究中，状态机通常由状态集合、输入集合、状态转移规则以及必要时的输出规则构成。不同领域对其具体定义略有差异，但核心思想一致：系统并非在任意时刻都可做任意动作，而是受到当前状态的约束，并按照既定规则响应。
1.2 状态
“状态”是状态机的基本单位，表示系统在某一时刻的内部条件、配置或所处阶段。状态既可以是抽象标记，也可以对应具体变量组合，例如程序中的“已登录”“加载中”“错误”等情形，或电路中的不同控制位组合。
状态的意义在于压缩系统历史。对于许多问题，并不需要记录完整过去，只需知道当前状态即可推断后续行为。因此，状态机特别适合描述具有记忆但记忆范围有限的系统。
1.3 输入与输出
输入是触发状态变化的事件、信号或符号，输出则是系统对输入作出的可观测反应。输入可以来自外部环境，也可以来自内部时钟、计数器或条件判断；输出则可能表现为动作执行、信号产生、文本识别结果或控制指令。
并非所有状态机都显式包含输出。有些模型只关注状态转移本身，用于判断某串输入是否被接受；另一些模型则同时描述输入与输出，常用于控制系统、协议交互和界面响应。
1.4 状态转移
状态转移是状态机的核心机制，指系统在某个输入条件下从当前状态迁移到另一个状态。转移通常由规则或函数给出，体现为“若在状态 A 遇到输入 x，则转到状态 B”。
这种机制使状态机能够表达流程顺序、分支判断、循环重复等行为。若转移规则完全确定，则同一状态和输入总是对应唯一后继；若允许多个可能后继，则属于非确定性模型。
1.5 初始状态与终止状态
初始状态表示系统运行开始时所在的位置，是状态机分析的起点。终止状态则表示某种结束、接受或完成条件，在很多模型中也被称为接受状态、终态或最终状态。
初始状态与终止状态共同决定了状态机对输入过程的整体意义。例如，在识别字符串时，初始状态是读入前的位置，终止状态则决定输入是否被接受；在工作流模型中，终止状态往往对应任务完成或流程关闭。
2 历史与发展
2.1 早期思想来源
状态机的思想可追溯到对机械装置、逻辑开关和有限步骤过程的研究。早期自动装置、继电器电路以及计数器系统，都体现了“根据当前情况和触发条件改变状态”的基本思路。
随着数学逻辑和形式语言研究的发展，人们逐渐意识到，许多看似复杂的动态系统，其实可以通过少量状态和清晰规则加以描述。这为后来的自动机理论奠定了基础。
2.2 形式化定义的建立
20世纪中期，状态机与自动机理论被系统地形式化，成为研究可计算性与语言识别的重要工具。学者们开始用集合、映射和逻辑公式来严格定义状态、输入与转移关系，使其从工程经验上升为数学对象。
这一阶段的重要成果是把“机器行为”抽象为可证明、可分析的形式系统。由此，状态机不再只是具体装置的描述，而成为可以讨论等价性、最小性和可判定性的理论框架。
2.3 在计算理论中的发展
在计算理论中，状态机被用来研究哪些语言或问题可以由有限记忆系统处理。有限状态模型尤其重要，因为它与正则语言、正则表达式以及若干自动化处理过程密切相关。
与此同时，更复杂的模型也陆续出现，用以处理更强的记忆需求和更丰富的交互结构。状态机理论因此逐渐形成多个分支，从基础的有限自动机扩展到带栈、带概率、带并发与时序约束的形式。
2.4 现代扩展与应用
现代状态机已不局限于理论计算，而是广泛进入软件工程、硬件设计、嵌入式系统、交互设计和形式验证等领域。工程上常借助状态机组织复杂逻辑，使行为更清晰、边界更明确、测试更方便。
同时，状态机也与模型检查、协议分析、用户界面管理和事件驱动架构结合，形成了许多实用工具。随着系统复杂度提高，分层、并发和概率等扩展形式也日益常见。
3 数学形式化
3.1 五元组与七元组表示
状态机常用五元组或七元组来表示。基础形式一般包含状态集合、输入字母表、转移函数、初始状态与接受状态；若还考虑输出，则会加入输出集合和输出函数，形成更完整的描述。
这种表示法的优点在于结构明确，便于证明和比较不同模型。通过统一的符号化表达，状态机可以被纳入严格的数学推理体系。
3.1.1 状态集合
状态集合是模型中所有可能状态的总和，通常记作有限集合，但在某些扩展模型中也可为可数集合。每个状态都是系统配置的一种抽象表示，彼此之间通过转移关系相连。
状态集合的设计直接影响模型复杂度。若划分过粗，模型可能无法准确反映行为；若划分过细，则会增加分析负担，甚至导致状态数量迅速膨胀。
3.1.2 输入字母表
输入字母表是系统可接受的输入符号集合，常记为有限集合。实际应用中，它可以表示字符、事件、消息、按钮操作或传感器信号等。
输入字母表的作用是限定状态机所能处理的事件类型。不同输入符号会诱发不同转移，因此它决定了模型的观察粒度和表达范围。
3.1.3 转移函数
转移函数定义了在给定状态和输入下，系统将进入何种后继状态。对于确定性模型，转移函数通常是单值映射；对于非确定性模型，则可能对应多个后继状态的集合。
转移函数是状态机行为的数学核心。通过它，可以精确描述条件分支、顺序推进、异常处理和重复循环等逻辑。
3.1.4 输出函数
输出函数用于规定状态机在某种状态或某次转移下产生什么输出。不同模型对输出的位置安排不同：有的与状态相关，有的与转移相关，还有的二者兼有。
输出函数使状态机不仅能判断“会到哪里”，还可以回答“会产生什么”。这对于控制器、通信协议和交互系统尤其重要。
3.2 可达性与闭包性质
可达性研究从初始状态出发，哪些状态能够经过若干次转移到达。若某状态无法从初始状态到达，则通常可视为冗余状态，可在简化模型时移除。
闭包性质则关注状态机在特定运算下是否仍属于同类。例如，若对某些语言进行并、交、补等操作后，结果仍可由同类状态机识别，就说明该类模型具有相应的封闭性。这些性质对于理论分析和构造证明非常重要。
3.3 等价性与最小化
状态机等价性指两个模型在外部可观察行为上是否一致。若它们对所有输入序列给出相同的接受结果或输出行为，则可视为等价。
最小化则是寻找在功能不变前提下状态数最少的等价模型。该过程有助于减少冗余、提高执行效率，也能让模型结构更清晰。
3.3.1 状态等价
状态等价通常指两个状态在未来所有可能输入下表现相同，因此可以合并。判定状态等价是最小化算法中的关键步骤。
从直观上看，若两个状态对外界的反应完全无法区分，那么保留二者并无必要。状态等价因此成为模型压缩的重要依据。
3.3.2 最小状态机
最小状态机是在等价类意义下状态数最少的状态机。对于有限状态模型，最小化结果通常是唯一的，或者在状态命名不同的情况下唯一到同构。
最小状态机便于实现和验证，也能揭示系统行为的本质结构。它常用于编译器、协议规范和硬件控制器设计。
3.4 不变量与判定性质
不变量是在状态演化过程中始终成立的性质，例如某些标志位不会同时为真，或某个资源计数永不为负。通过分析不变量，可以帮助验证系统是否遵循设计约束。
判定性质则研究某些问题是否存在算法可在有限时间内判断答案，如某状态是否可达、某串输入是否被接受、两个模型是否等价等。状态机理论中，部分问题可判定，部分则在更强模型中变得复杂甚至不可判定。
4 状态机类型
4.1 有限状态机
有限状态机是状态数有限的一类状态机，也是最常见的基础模型。它使用有限数量的状态描述系统行为，因此特别适合表示模式匹配、简单控制与协议流程。
4.1.1 确定性有限状态机
确定性有限状态机在任一状态和输入下，都只有唯一的后继状态。它结构简单，易于实现和分析，是理论与工程中最常用的形式之一。
由于没有歧义，确定性模型便于直接执行，也便于做最小化和等价判断。
4.1.2 非确定性有限状态机
非确定性有限状态机允许同一状态和输入对应多个可能后继。它在理论上常用于简化构造和证明，有时能更紧凑地表达某些语言或条件。
虽然其执行方式看似“多路并行尝试”，但在表达能力上与确定性有限状态机等价，只是在描述和转换方式上更灵活。
4.2 带输出的状态机
带输出的状态机不仅关心接受与否，还关心在运行过程中产生什么反应。此类模型常用于控制器、接口和信号系统。
4.2.1 Mealy 机
Mealy 机的输出与当前状态和输入共同相关，因此输出往往在转移发生时产生。它通常具有较高的响应灵敏度，能较快对输入变化作出反应。
在实现上，Mealy 机有时比其他模型更节省状态数，但输出设计需要更谨慎，以避免转移条件复杂化。
4.2.2 Moore 机
Moore 机的输出只依赖于当前状态，而不直接依赖输入符号。这样一来，输出变化通常出现在状态切换之后，结构更稳定、语义更直观。
Moore 机在硬件控制和界面状态管理中较常见，因为其输出规则清晰，便于调试与验证。
4.3 层次状态机
层次状态机把状态按层级组织，允许一个状态内部再包含子状态。这样可以把复杂系统拆分为若干层次，减少平铺式状态图的冗长。
这种结构特别适合描述具有阶段与子流程的系统。例如某个主流程在不同阶段下，又分别包含不同的局部行为模式。层次化设计能够显著增强可读性。
4.4 并发状态机
并发状态机描述多个状态区域同时运行、相互协调的情形。它适用于多个子系统并行工作、但又共享某些事件或资源的场景。
这种模型比单一路径状态机更接近真实系统，但分析难度也更高。并发引入后，状态组合数量往往迅速增加，需要借助分解和同步机制处理。
4.5 概率状态机
概率状态机在转移规则中引入概率因素，即在某状态和输入下，可能以不同概率进入不同后继状态。它常用于随机过程、故障建模和部分智能决策任务。
此类模型能表达不确定环境中的平均行为或统计特征，因此在通信、可靠性分析和预测性建模中具有价值。
4.6 时序状态机
时序状态机除了状态和输入外，还考虑时间约束，如超时、延迟、持续时长或定时触发条件。它适用于实时系统、嵌入式控制与交互协议。
时间因素的引入使模型更贴近实际运行环境，但也使分析更复杂。很多系统的正确性，恰恰取决于事件是否在规定时间内发生。
5 计算能力与理论性质
5.1 可识别语言
状态机能够识别某些形式语言，即判断输入串是否满足特定规则。可识别语言的种类取决于状态机类型和其记忆能力，有限状态模型通常对应较低复杂度的语言类。
语言识别是状态机理论的重要应用，它连接了机器行为与符号模式之间的关系。通过该视角，可以把许多规则检测问题转化为自动化判定过程。
5.2 正则语言与状态机
有限状态机与正则语言之间存在紧密对应关系。一般来说，正则语言正好可以由某类有限状态机识别，而有限状态机可接受的语言也构成正则语言的核心部分。
这一对应关系使状态机成为研究正则表达式、词法规则和简单模式匹配的基础工具。很多文本处理任务，本质上都可归结为正则语言识别。
5.3 判定问题
状态机理论中的判定问题主要关注某些性质是否存在有效算法可做出结论。常见问题包括接受、等价、可达以及最小化等。
这些问题既有理论意义，也有实践价值。它们决定了模型是否适合自动分析、自动验证与自动优化。
5.3.1 接受问题
接受问题是判断某个输入串是否会被状态机接受。对有限状态模型而言，通常可以通过模拟运行直接得到答案。
在实际应用中，接受问题对应规则匹配、协议校验和状态验证等任务，是最基础也最常见的判定之一。
5.3.2 等价性问题
等价性问题判断两个状态机是否对所有输入表现一致。该问题在模型合并、版本比较和规范验证中很重要。
对于某些有限模型，等价性可以通过最小化或构造对偶分析解决；但在更复杂系统里，这一问题可能显著变难。
5.3.3 可达性问题
可达性问题是判断某个状态是否能从初始状态到达。它可用于发现死代码、冗余分支、不可用功能或潜在故障路径。
可达性分析是模型检查和系统调试中的常用手段，能够帮助工程人员理解系统的实际运行边界。
5.4 状态爆炸现象
状态爆炸指随着系统模块增加、并发增强或变量展开，状态总数急剧增长的现象。即使原始规则并不复杂，组合后的状态空间也可能大到难以穷举。
这是状态机应用中的典型难题。为缓解这一问题，常采用抽象、分层、符号化表示和局部验证等方法，以降低分析成本。
6 设计与建模方法
6.1 状态图
状态图以图形方式表示状态与转移关系，节点代表状态，箭头代表转移。它直观、易读，适合用于需求分析、流程说明和设计评审。
状态图的优势在于能迅速展示系统结构及关键路径，但当状态过多时也容易变得拥挤。因此在复杂场景下，通常需要配合分层或模块化表达。
6.2 状态转移表
状态转移表用表格列出各状态在不同输入下对应的后继状态或输出结果。它适合精确记录规则，便于实现和测试。
与图形表示相比，表格更强调形式清晰和查找方便，尤其适合输入种类较少而规则明确的系统。
6.3 事件驱动建模
事件驱动建模强调系统在事件到来时才进行状态处理。每个事件都会触发检查、判断和必要的转移，因此与消息队列、回调机制和异步系统十分契合。
这种方法有助于将复杂系统拆成离散触发点，减少连续逻辑的混杂，使设计更接近实际运行方式。
6.4 分层与模块化设计
分层设计把复杂状态机拆为若干层级，每层处理不同粒度的行为；模块化设计则按功能拆分子状态机，并通过接口或同步事件连接。二者都旨在降低复杂度，提高复用性。
在大型系统中，这种组织方式不仅便于维护，也便于团队协作和局部验证。一个清晰的模块边界，往往比单纯增加状态更有效。
6.5 形式验证与模型检查
形式验证是利用数学方法证明模型满足某些性质的过程，模型检查则通过自动遍历状态空间来验证性质是否成立。状态机是这类方法的重要输入对象。
通过形式验证，可以发现设计中的遗漏、冲突和死锁风险。模型检查尤其适合分析有限或可抽象为有限的状态系统，因此在硬件与协议验证中应用广泛。
7 应用领域
7.1 编译原理
状态机在编译原理中具有基础地位，尤其适用于文本扫描和规则预处理。它帮助编译器把原始字符流转化为更高层次的语言单元。
7.1.1 词法分析
词法分析常用有限状态机识别标识符、关键字、数字、运算符与注释等模式。通过状态转移，扫描器能够将连续字符划分为词法记号。
这一过程是编译器前端的重要环节，决定了后续语法分析能否顺利进行。状态机的引入使规则识别更高效，也更容易维护。
7.1.2 语法前处理
在某些语言处理流程中，状态机可用于语法前处理，如处理转义、字符串边界、预处理指令或简单嵌套结构。它通常不直接承担完整语法分析，而是完成辅助性识别工作。
这类应用强调“先整理、再解析”，使复杂输入更适合后续处理模块。
7.2 软件工程
在软件工程中，状态机常用于组织业务流程、界面交互和异常处理。它能把原本分散在多个条件分支中的逻辑统一为可视化、可验证的结构。
7.2.1 用户界面状态管理
用户界面通常具有“空闲”“加载中”“成功”“失败”“编辑中”等状态。状态机能清晰表示这些状态之间的转换，使按钮可用性、弹窗显示和页面跳转更加一致。
这种方式有助于减少界面逻辑混乱，避免出现难以追踪的边界情况。
7.2.2 协议与流程控制
软件系统中的协议交互、订单流程、审批步骤等，都适合用状态机表达。每一步动作都在特定状态下发生，并受到输入事件的约束。
借助状态机，流程规则可以被明确固化，便于检查非法操作、重复提交和超时处理。
7.3 硬件设计
状态机在数字硬件设计中极为常见，尤其适用于控制器、接口逻辑和时序管理。由于硬件行为通常是离散且同步的，状态机能够直接映射这些特征。
7.3.1 数字电路控制器
数字控制器负责管理数据通路、操作顺序和响应时机。状态机可将复杂控制信号拆解为若干状态与转移，方便综合与验证。
在有限状态范围内，这种设计方式结构紧凑，能有效减少控制逻辑的歧义。
7.3.2 通信协议控制
通信协议往往要求发送、等待、确认、重传等阶段严格有序。状态机能够清晰刻画这些阶段以及它们之间的转换条件。
因此，在接口控制器、总线协议和收发器设计中，状态机几乎是标准方法之一。
7.4 自然语言处理
在自然语言处理里，状态机常用于简单句法识别、文本模式检测和有限结构分析。对于较规则的语言现象，它能提供稳定、快速的处理方案。
虽然自然语言整体远比有限状态系统复杂，但在某些局部任务中，状态机仍然十分实用，例如分词辅助、格式识别和模板化表达处理。
7.5 自动控制系统
自动控制系统中的状态机常用于模式切换与工作阶段管理，例如启动、正常运行、暂停、故障和恢复。它与连续控制算法配合，可以更好地组织系统逻辑。
这种用法特别适合需要明确工作阶段的设备。状态机负责离散决策，控制器负责数值调节，两者结合能提高系统稳定性。
7.6 游戏与交互系统
游戏角色行为、菜单导航、任务流程和交互动画都常用状态机描述。它使不同动作之间的切换更自然，也方便管理复杂的触发条件。
在游戏开发中，状态机还常用于角色 AI 和界面逻辑，帮助将“待机、奔跑、攻击、受击”等行为整理成清晰的行为图。
8 实现与工具
8.1 编程语言中的状态机实现
在编程语言中，状态机常通过枚举、类、函数指针或表驱动方式实现。具体做法取决于项目规模与语言特性，但基本思路都是显式保存当前状态，并根据事件决定下一步。
这种实现方式可读性较好，也便于单元测试。对于复杂系统，常将状态机封装为独立模块，以避免逻辑散落在各处。
8.2 图形化建模工具
图形化工具可以让开发者通过拖拽节点和连线建立状态图，并自动生成代码或验证结果。它们降低了建模门槛，尤其适合需求讨论和教学场景。
这类工具的价值不仅在于画图，还在于让状态、事件和转移规则保持一致，减少文档与实现脱节的问题。
8.3 自动生成与代码转换
一些工具能够从状态图或形式规范自动生成可执行代码、测试用例或验证模型。这类自动化手段可减少手工编码错误，并提高实现与设计之间的一致性。
在某些工程流程中，状态机模型甚至被视为“源代码”的一部分，直接参与生成目标程序。
8.4 测试与调试方法
状态机的测试通常关注状态覆盖、转移覆盖、异常路径和边界条件。调试时则常检查是否存在遗漏转移、死状态、错误回退或循环卡死。
由于状态机结构清晰，问题定位往往比散乱的条件分支更容易。借助日志、可视化和模拟输入，可以较快发现模型中的偏差。
9 相关概念
9.1 自动机
自动机是状态机的更广泛理论背景，通常指能够根据输入和内部状态进行形式化计算的机器模型。状态机可看作自动机理论中的基础类型之一。
9.2 图灵机
图灵机是研究可计算性的经典模型，具有比有限状态机更强的记忆能力。与之相比，状态机更适合描述有限记忆和局部决策过程。
9.3 Petri 网
Petri 网用于描述并发、同步与资源竞争等问题。与状态机相比，它更擅长表达多个事件同时发生或相互制约的结构。
9.4 过程代数
过程代数研究并发系统的组合、交互与等价关系。它与状态机在系统建模上有相通之处，但更强调进程之间的代数运算与行为比较。
9.5 有限状态控制器
有限状态控制器是状态机在工程中的具体化形式，常用于实现控制逻辑、协议管理和模式切换。它通常以硬件电路或软件模块的方式出现。
10 典型问题与案例
10.1 交通信号灯模型
交通信号灯是最经典的状态机案例之一。其状态通常包括红灯、绿灯和黄灯，并按照固定顺序循环切换，每个状态保持一定时间。
这一模型简单直观，适合用于说明状态、转移和定时机制之间的关系，也常被用作入门示例。
10.2 自动售货机模型
自动售货机可用状态机描述投币、选货、出货和找零过程。不同状态对应不同余额与操作权限，输入则包括投币、选项和取消等动作。
这一案例展示了状态机如何处理条件分支和资金累计，是工程建模中的常见范例。
10.3 门禁与解锁流程
门禁系统通常包含待机、验证、打开、关闭和报警等状态。只有在凭证正确或条件满足时，系统才会从锁定转向开启。
这种模型强调安全性和时序约束，常用于说明状态机如何管理权限判断和异常处理。
10.4 网络协议握手
网络协议握手过程一般由若干固定阶段组成，如请求、响应、确认与建立连接。每一步是否成功都会影响后续状态，因此非常适合用状态机表达。
该案例显示了状态机在通信控制中的实际价值，也体现出对顺序、超时和重试的精细管理。
10.5 用户登录状态管理
用户登录状态管理通常涉及未登录、已登录、过期、重新验证和退出等状态。不同状态决定可访问的功能与页面行为。
这一应用在现代软件中十分常见，尤其适合说明状态机如何统一处理身份变化、会话失效和跳转逻辑。