FSM 机器

有限状态机 (FSM)，有时称为有限自动机 (FSA)（复数自动机），或本质上是遗传算法，是计算的数学公式。它是一种提取和分析，在任何特定时刻只能处于有限数量的状态之一。为了响应特定的刺激，FSM 可以从一种形式转变为另一种形式；这种转变被称为“移位”。FSM 以模式、起始状态和引起每次移位的刺激的形式表示。有限状态机有两种类型：确定性有限状态机 (DFSM) 和非确定性有限状态机 (NDFSM)。确定性有限状态机可以像非确定性有限状态机一样构建。状态机的活动可以在一些智能技术中观察到，这些技术执行一系列由提供给它们的事件组成的预定活动。便利店在收集到正确组合的代币时分发品牌，楼梯的停靠模式由乘客接收的天花板决定，停车标志在汽车准备好时修改系列，以及串联门锁需要按正确顺序输入一系列符号，这些都是简单的例子。

与其他数值模拟（包括图灵计算机）相比，有限状态机具有非常低的计算能力。由于计算资源的差异，图灵计算机可以执行某些计算任务，而 FSM（有限状态机）不能。这是因为 FSM 中的阶段数量限制了其容量。

一个例子：投币式闸机

旋转门是可以通过状态机表达的基本操作的一个例子。闸机是一种在腰部高度有三个旋转臂的障碍物，一个在入口处，用于控制地铁系统和主题公园景点的入场。最初，手臂是关闭的，阻碍了入口并禁止顾客进入。通过将硬币或代币插入旋转门上的孔中，手臂被解锁，允许单个顾客通过。一旦顾客通过，手臂就会保持锁定状态，等待放入另一枚硬币。

将旋转门视为状态机，它有 2 个可设想的阶段：锁定阶段和解锁阶段。有两个参数可以改变其状况：将硬币插入框架 (coin) 和尝试推动手臂 (push)。尝试推动手臂对锁定位置没有影响。无论接口推多少次，它始终保持在锁定位置。插入硬币意味着向系统提供硬币输入，将状态从受限变为解锁。相反，顾客推开手臂并提供推动刺激，将状态返回到锁定。

旋转门神经网络可以用状态转换表来描述，该表显示了每个可能状态之间的转换（取决于提供给机器的输入）以及每个输入产生的结果。

一种基本方法，即单位向量，也可以用来描绘横向状态机。一条边维持每个阶段（圆圈）。从一个阶段到另一个阶段的移动由顶点（箭头）表示。引起移位的刺激在每条线上标明。一个返回原始状态的圆形箭头表示一个不产生情况变化的输入（包括在解锁状态下输入的硬币）。黑点移动到锁定组件表示它处于其起始点。

术语和概念

状态是平台当前情况的表示，因为它等待执行移位。移位是当满足标准或发生事件时必须执行的一系列活动。例如，在声音设备上收听广播（设备处于“广播”阶段）时，接收到“下一首”输入会导致设备转到最后一个频道。当设备处于“CD”模式时，“下一首”刺激使公司能够前进到下一张唱片。多种行为由相似的输入触发，具体取决于当前情况。

在一些有限状态机描述中，将操作与状态相关联也是可行的。

进入动作是在进入某个状态时所做的任何事情。

退出动作是离开某个状态时执行的操作。

FSM 的插图

状态与事件表

状态转换表有各种形式。最常见的形式如下所示：当前状态（例如，B）和刺激（例如，Y）的组合表示下一个状态（例如，C）。图表中未明确详细说明整个活动，必须通过参考来补充。使用状态图，您可以创建 FSM 定义，该定义提供所有行为的详细信息。

状态转换表

统一建模语言 (UML) 机器

状态机使用统一建模语言中的符号进行描述。UML 状态设备超越了经典有限状态系统限制，同时保留了其主要特征。UML 状态网络包括诸如分层结构、堆叠状态和垂直区域等新概念，同时还扩展了操作的概念。统一建模语言状态机展现了 Goopy 和图灵机器的特性。它们允许执行依赖于平台配置和特别明显的活动，如在 Mealy 系统中，以及与阶段而不是相位相连的进入和退出操作，如在图灵机器中。

规范和描述语言状态机

描述和规范语言是 ITU 规范，包含概念并包括表达过渡行为

• 发送通知
• 获取事件通知
• 设置计时器
• 暂停计时器
• 开始另一个并发状态机
• 最终决定

为了使有限状态系统能够运行，SDL 集成了称为“抽象数据类型”的基本数据结构、活动语言和实现逻辑。

简单有限状态机

描绘 FSM 有多种方法，包括上图所示的方法。

FSM 的用法

除了在模拟响应网络中的应用之外，有限状态系统在许多领域都很重要，例如电气工程、语言学、软件工程、心理学、生理学、算术、计算机游戏开发和推理。有限状态系统是计算几何学和计算理论中研究的一种设备。有限状态系统在计算机工程中经常用于模拟 Web 应用程序、设计设备、数字设备、软件开发、翻译器、安全机制以及计算和语言学研究。

FSM 的类型

接受器、传感器、分类器和序列器都是有限状态系统的类型。

• 接受器

接受器（也称为识别器或检测器）生成一个二进制数，指示传入输入是否被确认。接受器的条件要么是接受，要么是非接受。一旦所有信息都已获取，如果当前状态是接受状态，则输入被确认；否则，它将被拒绝。在大多数情况下，输入是一串符号（字符）；不需要干预。如果起始状态也是一个接受条件，则接受器将进入无限循环。该图演示了一个接受字符串“lovely”的接受器。此接受器中唯一接受的阶段是阶段 7。

一个表示是符号系列的一个（可能是无限的）集合，如果存在某个接受器接收该集合，则该集合是一种规则语言。例如，具有偶数个 0 的字符变量集合是一种规则语言（如图所示），而所有字符串的集合“不”是其持续时间是一个大整数的字符串。

接受器也可以定义为指定一种语言，该语言包含购买者批准的所有字符串，但不包含任何被拒绝的字符串；该语言由接受器识别。接受器识别的语言是规则语言。

该图显示了一个接受阶段的实例：一个确定性有限自动机 (DFA)，它确定二进制表示字符串是否具有偶数个 0。

S1（也称为初始位置）表示已输入偶数个 0 的状态。因此，S1 是一个可接受的状态。如果二进制系列包含偶数个 0，则此接受器将完成一个已批准的阶段（包括任何不包含 0 的二进制字符串）。此接受器接受的字符串包括 ?（整数值）、1、11、11...、00、010、1010、10110 等。

• 分类器

分类器是包含项的一个子集，当 n 大于 2 时，它们提供 n 元响应。

• 换能器

传感器使用动作来生成与给定输入和/或状态关联的输出。它们用于过程控制以及自然语言处理。

系统控制应用程序有两种类型

摩尔机

FSM 只使用入口事件。因此，输出只由状态决定。摩尔方法的优点是简化了行为。看看自动门。状态机识别两个导致转换的指令：“command_open”和“command_close”。在“打开”阶段的入口活动 (E:) 启动一个打开门的电机，而在“关闭”阶段的入口活动 (E:) 启动一个关闭门的电机。当电机完全打开和关闭时，“已打开”和“已关闭”阶段终止它。它们向外部环境（例如，其他物理系统）传达状态：“门已打开”或“门已锁定”。

米利机

FSM 还使用输入操作，这意味着输出取决于输入和状态。Mealy FSM 的实现通常会减少国家的数量。图 7 描绘了一个 Mealy FSM，它提供了与 Moore 实例相似的行为（该行为取决于实现的 FSM 执行模型，并且将适用于虚拟 FSM，但不适用于事件驱动 FSM）。有两个输入活动 (I:)：“如果收到关闭命令，启动电机关闭门”和“如果收到打开命令，启动电机解锁门”。未描绘过渡阶段“打开”和“关闭”。

• 序列器

序列器（也称为生成器）是一种具有单个输出语言的接收器和转换器。它们只生成一个系列，可以看作是接收器或转换器输出向量。

确定

还有非确定性（NFA、GNFA）和确定性（DFA）自动机。确定性算法中的每个阶段对于每个可能的输入都只有一个移动。非确定性算法中的一个输入可能导致某个特定状态的一个、一个以上或没有移位。任何非确定性自动机都可以使用数据类型构建过程转换为具有等效功能的（通常更复杂的）确定性自动机。

“组合 FSM”是只有一个阶段的有限状态机 (FSM)。它只允许在进入状态时进行操作。当大量有限状态系统必须协同工作时，这种方法很有用，并且将完全算法部分视为一种 FSM 以适应功能原型是很有利的。

差分语义

其他范围的定义可用于表征状态机。有一些用于分析和创建感觉集成算法的方法。它们将多级模块（通常有多个当前状态）、流程图和真值表集成到一种特定语言中，最终形成独特的语法和解释范围。正如 Harel 的初始状态系统一样，这些真值表允许分层堆叠阶段、正交区域、状态策略和过渡决策。

FSM 的实现

软件应用

使用有限状态设备开发软件程序时，通常使用以下参数

• 使用自动机编程。
• 事件触发的有限状态机
• 模拟有限状态机是具有有限数量的设备。
• 声明模型结构。

硬件应用

FSM 可以通过嵌入式软件设备、可编程逻辑、逻辑操作以及触发器或开关在通信系统中实现。特别是，开发的系统需要使用寄存器来保存系统状态、一块组合电路来决定数据结构以及一个辅助组合电路单元来决定 FSM 的结果。Richards 调节器是传统的硬件实现。

梅德韦杰夫机器的结果明确地附着在相位开关上，从而减少了触发器和输出之间的滞后时间。

可以通过相编码来改进低功耗计算机程序的能耗。

编译器和 FSM

在脚本语言处理器的接口中，有限自动机经常被使用。这样的前端可以由多个有限状态系统组成，这些系统执行词法分析器和解码器。词法分析器从一系列字母中构建一系列语言符号（如特殊字符、字符串和符号），处理器从中构建语法结构。解析器和词法分析器管理计算语言学中的常规和上下文无关形态。

FSM 的增强

创建一个具有最少数量的阶段但能完成相同任务的系统是最大化 FSM 的含义。Hopcroft 最小化技术是实现这一目标最快的算法。另一种方法是使用推理列表或 Moore 约简算法。非循环 FSA 也可以按排序顺序进行约简。

数学模型

下述形式化活动是根据广义分类给出的。

确定性有限状态机 (DFSM)，有时也称为确定性有限状态接收器，是一个四元组设备 (Σ, S, s0, δ, F)。

此处，

Σ: 它是输入字母表（一个不为 null 的有限字符集合）。

S: 它是一个非空的有限子序列。

s0: 它是一个第一阶段，S 的一个组成部分。

δ: 它被称为状态转换函数。Δ:S x Σ → S（在（NDFA）非确定性有限自动机中，它将是 δ: S x Σ → Ƥ(S)），因此 δ 将提供一组状态）。

F: 它是最终条件集合，是 S 的一个（可能为 null 的）子集。

ϵ 在确定性和非确定性 FSM 中，通常允许将 δ 视为分量操作，即 δ (s, x) 不必为 S ϵ S 和 x ϵ Σ 的每个排列指定。如果 FSM M 处于阶段 s，下一个符号是 x，并且未指定 δ (s, x)，则 M 可能会报告问题（即拒绝输入）。这在典型的状态机公式中很重要，但在更改系统时则不那么重要。在其标准结构中，一些过程可能需要总函数。

有限状态机具有与图灵计算机相似的计算能力，但其磁头只能执行“读取”操作，并且必须始终从左向右移动。也就是说，任何有限状态系统接受的基本短语也由有限图灵机识别，反之亦然。

六元组有限状态传感器 (Σ, Г, S, s0, δ, ω)，其中

Σ: 它是输入字母表（一个有限的非空字符集合）；

Г: 它是输出字母表（一个有限的非空符号集合）；

S: 它是非空的有限对象集合。

s0: 它是第一阶段，S 的一个组成部分；

δ: 是初始状态的变量；

ω: 它是产生结果的操作。

如果输出函数由阶段和输入符号（ω: S x Σ → Г）确定，则该描述符合 Mealy 范式，可以表示为 Mealy 设备。如果输出系统定义依赖于状态（ω: S → Г），则描述符合 Moore 模型，可以描述为 Moore 设备。半自动机或转换机是没有最终输出的（FSM）有限状态机。

如果忽略 Moore 机器 ω (s0) 的初始输出符号，则可以通过将每个 Mealy 更改的目标函数（即，标记每个边界）与终端 Moore 状态的输出符号相关联，轻松地将其转换为结果 Mealy 机器。

由于 Mealy 机器阶段可能在其接收阶段（边缘）上具有多个输出标签，因此相反的转换更加困难。每个此类阶段必须分为多个 Moore 机器状态，每个状态对应一个事件输出符号。