状态机
状态机是一种用于设计算法的数学抽象概念。它可以读取一组输入,并根据这些输入转换为不同的状态。
状态是系统等待执行转换时的进展的状况的描述,其中转换是当条件满足或接收到事件时执行的一组动作。在状态图中,圆圈表示每个可能的状态,箭头表示状态之间的转换。
通过观察最终状态,你可以推测出导致该状态的一系列输入。
基本状态机有两种类型:
- 确定有限状态机
-
这种类型的状态机对于任何允许的输入只允许一种可能的转换。这就像“if”语句中的
if x then doThis else doThat
,计算机必须执行两者之一。 - 非确定有限状态机
-
在某些状态下,一个输入可以导致多个不同的状态。
图 1:确定有限状态机。
在图 1 中,状态从状态 1 开始;给定输入“X”,状态变为状态 2;给定输入“Y”,状态变为状态 3。
图 2:非确定有限状态机。
在图 2 中,给定输入“X”,状态可以保持不变或者变为状态 2。
值得一提的是,任何正则表达式都可以由状态机表示。