有限状态机（FSM:finite-state machine ）或有限状态机（FSA:finite-state automaton）、有限自动机或简单的状态机是计算的数学模型。它是一个抽象的机器，在任何给定的时间内都可以处于有限个状态中的一个。FSM可以根据一些外部输入从一个状态更改为另一个状态；从一个状态更改为另一个状态称为转换。FSM由其状态列表、初始状态和每个转换的条件定义。有限状态机有两种类型——确定性有限状态机和非确定性有限状态机。确定性有限状态机可以构造为任何非确定性状态机。
现代社会的许多装置都可以观察到状态机的行为，这些装置根据一系列事件来执行预定的动作序列。简单的例子是自动售货机，当硬币的正确组合存放时，自动售货机分配产品；电梯，其停止顺序由乘客要求的楼层决定；交通灯，当汽车等待时改变顺序；组合锁，需要按正确的顺序输入组合号。
有限状态机的计算能力比其他一些计算模型（如图灵机）要小，计算能力的区别意味着图灵机可以完成但FSM不能完成的计算任务。这是因为FSM的内存受其状态数的限制。FSMS是在更一般的自动机理论领域进行研究的。
缘起
一个可以用状态机模拟的简单机械装置的例子是旋转栅门。旋转栅门用于控制地铁和游乐园游乐设施的进出，它是一个在腰部高度有三个旋转臂的门，一个在入口通道上。最初被锁住，堵住入口，防止顾客通过。把硬币或代币放在旋转栅门上的一个槽中，就能打开门把手，让一个顾客可以通过。客户通过后，手臂再次锁定，直到插入另一枚硬币。
作为状态机，旋转栅门有两种可能的状态：锁定和解锁。有两种可能的输入影响其状态：将硬币放入槽（硬币）和推动臂（推动）。在锁定状态下，推动臂没有任何作用；无论给多少次输入推动，它都保持锁定状态。把硬币放进去——也就是给机器一个硬币输入——将状态从锁定转换为解锁。在解锁状态下，放入额外的硬币没有效果；即，提供额外的硬币输入不会改变状态。但是，客户通过手臂推动，提供推动输入，将状态切换回锁定状态。
转门状态机可以用状态转换表表示，显示每个可能的状态、它们之间的转换（基于给机器的输入）和每个输入产生的输出：
| Current State | Input | Next State | Output |
|---|---|---|---|
| Locked | coin | Unlocked | Unlocks the turnstile so that the customer can push through. |
| push | Locked | None | None |
| Unlocked | coin | Unlocked | None |
| push | Locked | When the customer has pushed through, locks the turnstile. | None |
转门状态机也可以用一个称为状态图的有向图来表示。每个状态都由一个节点（圆）表示。边（箭头）显示从一种状态到另一种状态的转换。每个箭头都标有触发转换的输入。不引起状态变化的输入（如处于解锁状态的硬币输入）由返回原始状态的圆形箭头表示。从黑点进入锁定节点的箭头表示它是初始状态。
概念和术语
状态是对正在等待执行转换的系统状态的描述。转换是在满足条件或接收到事件时要执行的一组操作。例如，当使用音频系统收听收音机时（系统处于“收音机”状态），接收到“下一个”刺激会导致移动到下一个电台。当系统处于“cd”状态时，“next”刺激会导致移动到下一个轨道。相同的刺激根据当前状态触发不同的动作。
在某些有限状态机表示中，也可以将动作与状态关联：
进入动作：进入状态时执行。
退出操作：退出状态时执行。
表示
状态图是计算机科学和相关领域用来描述系统行为的一种图。状态图要求所描述的系统由有限数量的状态组成；有时确实如此，而有时这是一个合理的抽象。存在多种形式的状态图，它们略有不同，语义也有所不同。
状态/事件表
使用了几种状态转换表类型。最常见的表示形式如下：当前状态（例如B）和输入（例如Y）的组合显示下一个状态（例如C）。完整操作的信息没有直接在表中描述，只能使用脚注添加。包含完整动作信息的FSM定义可以使用状态表（另请参见虚拟有限状态机）。
| Current stateInput | State A | State B | State C |
|---|---|---|---|
| Input X | … | … | … |
| Input Y | … | State C | … |
| Input Z | … | … | … |
UML状态机
统一建模语言有一个描述状态机的符号。UML状态机克服了传统有限状态机的局限性，同时保留了它们的主要优点。UML状态机引入了层次嵌套状态和正交区域的新概念，同时扩展了操作的概念。UML状态机具有Mealy机器和Moore机器的特性。它们支持依赖于系统状态和触发事件的操作，如在Mealy机器中，以及与状态而非转换相关的进入和退出操作，如在Moore机器中。
SDL状态机
规范和描述语言是ITU的一个标准，其中包括描述转换中动作的图形符号：
- 发送事件
- 接收一个事件
- 启动计时器
- 取消计时器
- 启动另一个并发状态机
- 决策
SDL嵌入称为“抽象数据类型”的基本数据类型、操作语言和执行语义，以便使有限状态机可执行。
用法
除了在这里介绍的系统建模中的应用之外，有限状态机在许多不同的领域中都具有重要意义，包括电气工程、语言学、计算机科学、哲学、生物学、数学和逻辑。有限状态机是在自动机理论和计算理论中研究的一类自动机。在计算机科学中，有限状态机广泛应用于应用行为建模、硬件数字系统设计、软件工程、编译器、网络协议以及计算和语言研究。
分类
有限状态机可以细分为传感器、接收器、分类器和序列器。
接受者（识别者）
接收器（也称为识别器和序列检测器）产生二进制输出，指示是否接受接收的输入。FSM的每个状态要么是“接受”，要么是“不接受”。收到所有输入后，如果当前状态为接受状态，则接受输入；否则拒绝输入。通常，输入是一系列符号（字符）；不使用动作。
一组（可能是无限的）符号序列，又名。形式语言，如果有某个有限状态机恰好接受该集合，则称为常规语言。例如，偶数为零的二进制字符串集是一种常规语言，而长度为质数的所有字符串集不是。
机器也可以被描述为定义一种语言，该语言包含机器接受的每个字符串，但不包含被拒绝的字符串；该语言被机器“接受”。根据定义，FSM接受的语言是常规语言——如果有一些FSM接受，那么语言就是常规语言。
确定给定的有限状态接受者所接受的语言的问题是代数路径问题本身的一个实例，它将最短路径问题推广到具有由（任意）半环元素加权的边的图上。
开始状态也可以是接受状态，在这种情况下，自动机接受空字符串。
分类器
分类器是有限状态机的一种推广，它类似于接受者，在终止时生成单个输出，但有两个以上的终止状态。
换能器
传感器根据给定的输入或使用动作的状态生成输出。它们用于控制应用和计算语言学领域。
在控制应用程序中，可区分两种类型：
摩尔机
FSM仅使用入口操作，即输出仅取决于状态。摩尔模型的优点是简化了行为。考虑一个电梯门。状态机识别两个命令：“命令打开”和“命令关闭”，触发状态更改。进入动作（E:）在“打开”状态下启动电机打开车门，在“关闭”状态下启动电机在另一方向关闭门。状态“打开”和“关闭”在完全打开或关闭时停止电机。它们向外部世界（例如，向其他电梯）发出“门是开的”或“门是关的”的信号。
梅利机
FSM还使用输入动作，即输出取决于输入和状态。使用有限的FSM通常会导致状态数量的减少。示例显示了一个实施与摩尔示例中相同行为的简单FSM（该行为取决于实施的FSM执行模型，并且将起作用，例如，对于虚拟FSM，但对于事件驱动的FSM不起作用）。有两个输入动作（i:）：“如果命令关闭到达，启动电机关闭车门”和“如果命令打开到达，启动电机向另一个方向打开车门”。未显示“打开”和“关闭”中间状态。
序列器
序列器或发生器是具有单个字母输入字母表的接受器和传感器类型的一个子类。它们只产生一个序列，可以看作是接受器或传感器输出的输出序列。
决定论
另一个区别是确定性（dfa）和非确定性（nfa，gnfa）自动机。在确定性自动机中，每个状态对于每个可能的输入只有一个转换。在非确定性自动机中，输入可以导致给定状态的一个、多个或没有转换。Powerset构造算法可以将任何非确定性自动机转换为具有相同功能的（通常更复杂）确定性自动机。
只有一种状态的有限状态机称为“组合FSM”。它只允许在转换到状态时执行操作。这个概念在需要许多有限状态机一起工作的情况下是有用的，并且当把一个纯粹的组合部分看作一种适合设计工具的FSM形式时也是很方便的。
替代语义学
还有其他一些语义可以用来表示状态机。例如，有一些用于为嵌入式控制器建模和设计逻辑的工具。它们将分层状态机（通常具有多个当前状态）、流程图和真值表组合成一种语言，从而形成不同的形式主义和语义集。这些图，如Harel的原始状态机[12]支持层次嵌套状态、正交区域、状态操作和转换操作。
优化
优化一个FSM意味着找到一个具有执行相同功能的最小状态数的机器。最快的已知算法是Hopcroft最小化算法其他技术包括使用蕴涵表或摩尔约简过程。此外，非循环FSA可以在线性时间内最小化。
实施
硬件应用
在数字电路中，可以使用可编程逻辑器件、可编程逻辑控制器、逻辑门和触发器或继电器来构建FSM。更具体地说，硬件实现需要一个寄存器来存储状态变量，一个确定状态转换的组合逻辑块，以及第二个确定FSM输出的组合逻辑块。典型的硬件实现之一是理查兹控制器。
在Medvedev机器中，输出直接连接到状态触发器，以最小化触发器和输出之间的时间延迟。
对于低功耗状态机，可以通过状态编码进行优化，以最小化功耗。
软件应用程序
以下概念通常用于使用有限状态机构建软件应用程序：
- 基于自动机的程序设计
- 事件驱动有限状态机
- 虚拟有限状态机
- 状态设计模式
有限状态机和编译器
有限自动机常用于编程语言编译器的前端。这样的前端可能包含几个有限状态机，它们实现词汇分析器和语法分析器。从一系列字符开始，词汇分析器构建一系列语言标记（如保留字、文本和标识符），解析器从中构建语法树。词汇分析器和解析器处理编程语言语法的常规部分和上下文无关部分。
