状态转移表

一维状态表编辑

也叫做特征表，一维状态表比二维版本更像真值表。输入通常放置在左侧，分隔于在右侧的输出。输出将表示这个机器的下一个状态。下面是有两个状态和两个组合输入的状态机的简单例子：

S₁和S₂最可能表示单一位0和1，因为单一位只有两个状态。

二维状态表编辑

状态转移图典型的是二维表。有两种安排它们的常用形式。

• 垂直（或水平）维指示当前状态，水平（或垂直）维指示事件，表中的单元格包含在时间发生时的下一个状态（和可能的联系于这个状态转移的动作）。

（S:状态, E:事件, A:动作, -:违法转移）

• 垂直（或水平）维指示当前状态，水平（或垂直）维指示下一个状态，单元格包含导致特定下一个状态的事件。

（S:状态, E:事件, A:动作, -:不可能转移）

下面给出机器M的状态转移表和状态图。

状态转移表 输入 状态 1 0 S1 S1 S2 S2 S2 S1

状态图

表格各列枚举所有可能的给机器的输入。表格各行枚举所有可能的状态。从上面给出的状态转移表，可以轻易的看出如果机器处在S₁（第一行），并且下一个输入是字符1，则机器将停留在S₁。如果字符0到达了，机器将转移到可在第二列见到的S₂。在图中这指示为从S₁到S₂的标记了0的箭头。

对于非确定有限自动机（NFA），一个新输入可以导致机器进入多于一个状态，因此是非确定性的。这在状态转移表中指示为一对花括号包围的所有目标状态的集合。下面给出一个例子。

这里的非确定机器处在状态S₁读入一个输入0将导致它同时处在两种状态，即状态S₂和S₃。最后的列定义特殊字符ε的合法转移。这个特殊字符允许NFA在没有输入的时候移动到不同状态。在状态S₃，NFA可以移动到S₁而不消耗任何输入字符。上述两种情况使描述的有限自动机是非确定性的。

有可能从表格绘制状态图。下面给出步骤：

1. 绘制圆圈表示给出状态。
2. 对于每个状态，检索对应的行绘制到目的状态的箭头。如果自动机是NFA则对一个输入字母可能有多个箭头。
3. 指定一个状态为开始状态。开始状态在自动机的形式定义中给出。
4. 指定一个或多个状态为接受状态。它也在自动机的形式定义中给出。

• Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X