複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/狀態轉移表/53535600
複製
複製成功

狀態轉移表

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

目錄

  1. 1 簡介
  2. 2 常見形式
  3. ▪ 一維狀態表
  4. ▪ 二維狀態表
  5. 3 變換成狀態圖

狀態轉移表簡介

狀態表是指定“狀態機”的多種方式之一，其他方式包括狀態圖，和“特徵等式”。 [1] 

狀態轉移表常見形式

狀態轉移表一維狀態表

也叫做特徵表，一維狀態表比二維版本更像真值表。輸入通常放置在左側，分隔於在右側的輸出。輸出將表示這個機器的下一個狀態。下面是有兩個狀態和兩個組合輸入的狀態機的簡單例子：
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
S1和S2最可能表示單一位0和1，因為單一位只有兩個狀態。

狀態轉移表二維狀態表

狀態轉移圖典型的是二維表。有兩種安排它們的常用形式。
  • 垂直（或水平）維指示當前狀態，水平（或垂直）維指示事件，表中的單元格包含在時間發生時的下一個狀態（和可能的聯繫於這個狀態轉移的動作）。
<b>狀態轉移表</b>
事件
狀態
E1
E2
...
En
S1
-
Ay/Sj
...
-
S2
-
-
...
Ax/Si
...
...
...
...
...
Sm
Az/Sk
-
...
-
（S:狀態, E:事件, A:動作, -:違法轉移）
  • 垂直（或水平）維指示當前狀態，水平（或垂直）維指示下一個狀態，單元格包含導致特定下一個狀態的事件。
<b>狀態轉移表</b>
下一個
當前
S1
S2
...
Sm
S1
Ay/Ej
-
...
-
S2
-
-
...
Ax/Ei
...
...
...
...
...
Sm
-
Az/Ek
...
-
（S:狀態, E:事件, A:動作, -:不可能轉移） [1] 

狀態轉移表變換成狀態圖

有可能從表格繪製狀態圖。下面給出步驟：
  1. 繪製圓圈表示給出狀態。
  2. 對於每個狀態，檢索對應的行繪製到目的狀態的箭頭。如果自動機是NFA則對一個輸入字母可能有多個箭頭。
  3. 指定一個狀態為開始狀態。開始狀態在自動機的形式定義中給出。
  4. 指定一個或多個狀態為接受狀態。它也在自動機的形式定義中給出。 [1] 
參考資料
  • 1.    Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X