状态机

状态机是一种用于设计算法的数学抽象。状态机读取一组输入，并根据这些输入改变到不同的状态。

状态是系统在等待执行转换时所处状态的描述。转换是在满足条件或接收到事件时要执行的一组操作。在状态图中，圆圈代表每个可能的状态，箭头代表状态之间的转换。

查看最终状态，您可以了解导致该状态的一系列输入。

有两种基本的状态机类型

确定性有限状态机

这种类型允许任何允许的输入只有一个可能的转换。这就像 `if` 语句一样，其中 `if x then doThis else doThat` 是不可能的。计算机必须执行两种选择中的一种。

非确定性有限状态机

给定某个状态，一个输入可以导致多个不同的状态。

图 1：确定性有限状态机。

在图 1 中，状态开始于状态 1；给定输入“X”，状态变为状态 2，或者给定输入“Y”，状态变为状态 3。

图 2：非确定性有限状态机。

在图 2 中，给定输入“X”，状态可以保持不变或变为状态 2。

请注意，任何 正则表达式都可以由状态机表示。