状态机

状态机是一种用于设计算法的数学抽象概念。它可以读取一组输入，并根据这些输入转换为不同的状态。

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

通过观察最终状态，你可以推测出导致该状态的一系列输入。

基本状态机有两种类型：

确定有限状态机

这种类型的状态机对于任何允许的输入只允许一种可能的转换。这就像“if”语句中的 if x then doThis else doThat，计算机必须执行两者之一。

非确定有限状态机

在某些状态下，一个输入可以导致多个不同的状态。

图 1：确定有限状态机。

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

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

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

值得一提的是，任何正则表达式都可以由状态机表示。