状态机

一、什么是状态机

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation.

​ ----有限状态机（FSM）或有限状态自动机（FSA）、有限自动机，或简称状态机，是计算的数学模型。

状态机是有限状态机（FSM）或有限状态自动机（FSA）或有限自动机的简称，是计算的数学模型。它是一种抽象机器，可以在任何给定时间恰好处于有限数量的状态之一。FSM可以从一种状态变为另一种状态来作为对某些输入的响应；从一种状态到另一种状态的变化称为转换（transition）。FSM 由其状态列表、初始状态和触发每个转换的输入定义。有限状态机有两种类型——确定性有限状态机（deterministic finite-state machines）和非确定性有限状态机（non-deterministic finite-state machines）。确定性有限状态机可以构造成与任何非确定性有限状态机等效。

状态机的行为可以在现代社会的许多设备中观察到，

二、示例：投币式旋转闸门

由状态机建模的简单机制的一个示例是旋转门。作为一个状态机，旋转门有两种可能的状态：锁定和解锁。有两种可能的输入会影响其状态：将硬币放入槽中（coin）和推动手臂（push）。锁定状态下，推臂无效；无论输入多少次推送，它都保持在锁定状态。投入硬币——即给机器一个硬币输入 ——将状态从锁定转变为解锁。在解锁状态下，投入额外的硬币无效；也就是说，提供额外的硬币输入不会改变状态。但是，客户通过双臂推动，给出推动输入，将状态切换回锁定。

旋转门状态机可以用一个状态转换表来表示，显示每个可能的状态，它们之间的转换（基于给机器的输入）和每个输入产生的输出：

Current State	Input	Next State	Output
Locked	coin	Unlocked	Unlocks the turnstile so that the customer can push through.
	push	Locked	None
Unlocked	coin	Unlocked	None
	push	Locked	When the customer has pushed through, locks the turnstile.

旋转栅门状态机也可以用称为状态图（上图）的有向图来表示。每个状态由一个节点（圆圈）表示。 边线（箭头）显示从一种状态到另一种状态的转换。每个箭头都标有触发该转换的输入。不引起状态变化的输入（例如处于 Unlocked 状态的硬币输入）由返回原始状态的圆形箭头表示。 从黑点到 Locked 节点的箭头表示它是初始状态。

三、确定性

在确定性自动机（DFA）中，每个状态对于每个可能的输入都只有一个转换。在非确定性自动机（NFA）中，输入可以导致给定状态的一个、多个或没有转换。幂集构造算法可以将任何非确定性自动机转换为具有相同功能的（通常更复杂的）确定性自动机。