状态机

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

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

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

基本状态机有两种类型:

确定有限状态机

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

非确定有限状态机

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

图 1:确定有限状态机。

这个状态机在输入 X 时从状态 1 转换为状态 2,在输入 Y 时从状态 1 转换为状态 3

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

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

这个状态机在给定输入 X 时,或维持现有状态(状态 1),或转换为状态 2

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

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

参见