オートマトン理論と順序論理 において、状態遷移表とは、有限状態機械が現在の状態と他の入力に基づいてどの状態（非決定性有限オートマトンの場合は複数の状態）に遷移するかを示す表である。これは本質的には真理値表であり、入力には現在の状態と他の入力が含まれ、出力に次の状態と他の出力が含まれる。
状態遷移表は有限状態機械を記述する多くの方法の1つです。他の方法としては状態図などがあります。
状態遷移表は、特性表とも呼ばれる1次元表である場合もあります。2次元形式よりも真理値表に近いものです。1次元は、状態遷移に関連する入力、現在の状態、次の状態、そして（オプションで）出力を表します。
状態遷移表は通常2次元の表です。状態遷移表を配置する方法は2つあります。
最初の方法では、一方の次元が現在の状態を示し、もう一方の次元が入力を示します。行と列の交点は、次の状態と（オプションで）状態遷移に関連する出力を示します。
2つ目の方法では、一方の次元は現在の状態を示し、もう一方の次元は次の状態を示します。行と列の交点は、状態遷移に関連する入力と（オプションで）出力を示します。
複数の有限状態機械における同時遷移は、実質的にn次元状態遷移表で表すことができ、行のペアが現在の状態（のセット）を次の状態にマッピングします。[1]これは、独立した相互依存的な有限状態機械間の通信を表現する代替手段です。
もう一方の極端な例では、単一の有限状態マシン内の各遷移に別々のテーブルが使用されています。「AND/ORテーブル」[2]は、存在するルールの決定が暗黙的に関連付けられた遷移のアクティブ化となる 不完全な決定テーブルに似ています。
偶数個の 0 を含む文字列を受け入れる有限状態マシンの 状態遷移表と対応する状態図の例を以下に示します。
状態遷移表では、有限状態マシンへのすべての可能な入力が表の列に列挙され、すべての可能な状態が行に列挙されています。マシンが状態 S 1 (最初の行) にあり、入力 1 (2 番目の列) を受け取った場合、マシンは状態 S 1に留まります。マシンが状態 S 1にあり、入力 0 (1 番目の列) を受け取った場合、マシンは状態 S 2に遷移します。状態図では、前者は S 1からS 1
に
ループする矢印 (ラベル 1) で示され、後者は S 1からS 2にラベル 0 で示される矢印で示されます。このプロセスは、マルコフ連鎖を使用して統計的に記述できます。
非決定性有限状態機械（nondeterministic finite state machine）では、入力によって機械が複数の状態をとる可能性があり、これが非決定性（nondeterministic）と呼ばれます。これは、状態遷移表において、すべての目標状態を中括弧{}で囲んで表すことで表されます。非決定性有限状態機械の状態遷移表と対応する状態図の例を以下に示します。
マシンが状態 S 2にあり、入力 0 を受信すると、マシンは同時に状態 S 1と S 2の 2 つの状態になります。
状態遷移表から状態図を描くことができます。簡単な手順を以下に示します。