狀態轉移表

在自動機理論和時序邏輯中，狀態轉移表是展示有限半自動機或有限狀態自動機基於當前狀態和其他輸入，要移動到什麼狀態（或在非確定有限狀態自動機情況下那些狀態）的表格。「狀態表」本質上是其中某些輸入是當前狀態，而輸出包含與其他輸出在一起的下一個狀態的真值表。

狀態表是指定「狀態機」的多種方式之一，其他方式包括狀態圖，和「特徵等式」。

常見形式

一維狀態表

也叫做特徵表，一維狀態表比二維版本更像真值表。輸入通常放置在左側，分隔於在右側的輸出。輸出將表示這個機器的下一個狀態。下面是有兩個狀態和兩個組合輸入的狀態機的簡單例子：

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