有限状态自动机（FSM）

有限状态自动机（FSM）是一种抽象的计算模型，它包含一组状态和一组能够在这些状态上执行的转移。在任何时刻，自动机都处于其中的一个状态，而它所处的这个状态，称为当前状态。自动机根据输入的转移，从一个状态转移到另一个状态。这个转移可以是确定的，也可以是不确定的。自动机的状态和转移可以用图来表示，这种图称为状态图。

初始态 即自动机开始的状态，如下面示例中1状态。

终结态 自动机的结束状态，在图中用双圆圈表示，遇到终结态，自动机可以结束。如下图中4状态。但要注意，不同的自动机匹配模式有可能并不会一遇到终结态就立即结束，有时会选择当自动机无法进行转移，并且当前处于终结态时才结束，以获得可行的最长匹配。

下图左被称为自动机的状态转移图，我们通过指针上面标记的符号，来确定拿个符号下，转移到哪个目标状态。例如，下图就显示了1状态在遇到a输入后转移到了2状态。下图右被称为自动机的状态转移表，我们通过表格中的行和列来确定下一个状态。例如，下表第二行就显示了2状态，当输入列是b时，会转移到3状态。

一般来说，有限状态自动机有两种类型：

• 确定性自动机：在任何状态，自动机都只有一个转移可以选择，这种自动机称为确定性自动机（DFA）。
• 非确定性自动机：存在一个状态，自动机在遇到一个输入时有多个转移可以选择，这种自动机称为非确定性自动机（NFA）。

这两种自动机都非常常用，上面的示例就是一个典型的DFA，因为其每个状态遇到一个输入都只能转移到一个状态。如果是NFA，在状态转移表中，一个单元格中会有多个不同可能的转移到的目标状态。