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