状态转移表

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

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

常见形式

一维状态表

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

A	B	当前状态	下一个状态	输出
0	0	S1	S2	1
0	0	S2	S1	0
0	1	S1	S2	0
0	1	S2	S2	1
1	0	S1	S1	1
1	0	S2	S1	1
1	1	S1	S1	1
1	1	S2	S2	0

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

二维状态表

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

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

状态转移表

事件 状态	E1	E2	...	En
S1	-	Ay/Sj	...	-
S2	-	-	...	Ax/Si
...	...	...	...	...
Sm	Az/Sk	-	...	-

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

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

状态转移表

下一个 当前	S1	S2	...	Sm
S1	Ay/Ej	-	...	-
S2	-	-	...	Ax/Ei
...	...	...	...	...
Sm	-	Az/Ek	...	-

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

例子

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

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

状态图

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

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

NFA的状态转移表

输入 状态	1	0	ε
S1	S1	{ S2, S3 }	Φ
S2	S2	S1	Φ
S3	S2	S1	S1

这里的非确定机器处在状态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