状态转移表

在自动机理论和时序逻辑中，状态转移表是展示有限半自动机或有限状态自动机基于当前状态和其他输入，要移动到什么状态（或在非确定有限状态自动机情况下那些状态）的表格。“状态表”本质上是其中某些输入是当前状态，而输出包含与其他输出在一起的下一个状态的真值表。

状态表是指定“状态机”的多种方式之一，其他方式包括状态图，和“特征等式”。

常见形式

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

A	B	当前状态	下一个状态	输出
0	0	S₁	S₂	1
0	0	S₂	S₁	0
0	1	S₁	S₂	0
0	1	S₂	S₂	1
1	0	S₁	S₁	1
1	0	S₂	S₁	1
1	1	S₁	S₁	1
1	1	S₂	S₂	0

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

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

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

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

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

状态图

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

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

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

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

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