状态机

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

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

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

有两种类型的基本状态机

确定性有限状态机

这种状态机只允许在任何允许的输入情况下进行一次可能的转换。这就像“if” 语句 中的 if x then doThis else doThat 不可能。计算机必须执行其中一个选项。

非确定性有限状态机

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

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

在图 1中，状态从状态 1 开始；给定输入 'X'，状态更改为状态 2，或者给定输入 'Y'，状态更改为状态 3。

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

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

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