状態遷移表

オートマトン理論と順次論理において、状態遷移表とは、有限状態機械が現在の状態と他の入力に基づいてどの状態（非決定性有限オートマトンの場合は複数の状態）に移行するかを示す表である。これは本質的には真理値表であり、入力に現在の状態と他の入力が含まれ、出力に次の状態と他の出力が含まれる。

状態遷移表は、有限状態マシンを指定するための多くの方法の 1 つです。他の方法としては、状態図があります。

一般的な形式

一次元

状態遷移表は、特性表とも呼ばれる 1 次元表である場合もあります。2 次元形式よりも真理値表によく似ています。1 次元は、状態遷移に関連付けられた入力、現在の状態、次の状態、および (オプションで) 出力を示します。

2次元

状態遷移表は通常、2 次元の表です。これを配置するには、2 つの一般的な方法があります。

最初の方法では、次元の 1 つが現在の状態を示し、もう 1 つが入力を示します。行と列の交点は、次の状態と (オプションで) 状態遷移に関連付けられた出力を示します。

2 番目の方法では、次元の 1 つが現在の状態を示し、もう 1 つが次の状態を示します。行と列の交点は、状態遷移に関連付けられた入力と (オプションで) 出力を示します。

その他の形式

複数の有限状態マシンの同時遷移は、行のペアが現在の状態（のセット）を次の状態にマップするn次元状態遷移表で効果的に表示できます。 ^[1]これは、独立した相互依存する有限状態マシン間の通信を表現する代替手段です。

もう一方の極端な例では、単一の有限状態マシン内の各遷移に個別のテーブルが使用されています。「AND/ORテーブル」^[2]は、存在するルールの決定が暗黙的に関連付けられた遷移のアクティブ化となる不完全な決定テーブルに似ています。

例

偶数個の 0 を含む文字列を受け入れる有限状態マシンの状態遷移表と対応する状態図の例を以下に示します。

状態遷移表では、有限状態マシンへのすべての可能な入力が表の列にわたって列挙され、すべての可能な状態が行にわたって列挙されます。マシンが状態 S ₁ (最初の行) にあり、入力 1 (2 番目の列) を受け取った場合、マシンは状態 S ₁に留まります。マシンが状態 S ₁にあり、入力 0 (最初の列) を受け取った場合、マシンは状態 S ₂に遷移します。状態図では、前者は S _{1から S}₁に
ループする矢印(ラベル 1) で示され、後者は S ₁からS _{2にラベル 0 で示される矢印で示されます。このプロセスは}、マルコフ連鎖を使用して統計的に記述できます。

非決定性有限状態マシンの場合、入力によってマシンが複数の状態になる可能性があり、これが非決定性です。これは、状態遷移表では、すべてのターゲット状態のセットが一対の中括弧 {} で囲まれて示されます。非決定性有限状態マシンの状態遷移表の例と対応する状態図を以下に示します。

マシンが状態 S ₂にあり、入力 0 を受信した場合、マシンは同時に状態 S ₁と S _{2 の}2 つの状態になります。

状態図からの変換/状態図への変換

状態遷移表から状態図を描くことができます。わかりやすい一連の手順を以下に示します。

与えられた状態を表す円を描きます。
各状態について、対応する行をスキャンし、目的の状態への矢印を描きます。有限状態マシンが非決定的である場合、入力文字に対して複数の矢印が存在する可能性があります。
状態を開始状態として指定します。開始状態は有限状態マシンの正式な定義で与えられます。
1 つ以上の状態を受理状態として指定します。これは有限状態マシンの正式な定義にも示されています。

参照

参考文献

^ Breen, Michael (2005)、「商用組み込みシステム製品ラインに軽量形式仕様手法を使用した経験」(PDF)、Requirements Engineering Journal、10 (2): 161–172、CiteSeerX 10.1.1.60.5228、doi :10.1007/s00766-004-0209-1、S2CID 16928695
^ Leveson, Nancy; Heimdahl, Mats Per Erik; Hildreth, Holly; Reese, Jon Damon (1994)、「プロセス制御システムの要件仕様」(PDF)、IEEE Transactions on Software Engineering、20 (9): 684–707、CiteSeerX 10.1.1.72.8657、doi :10.1109/32.317428

さらに読む

マイケル・シプサー：計算理論入門。PWS Publishing Co.、ボストン 1997 ISBN 0-534-94728-X

[Breen2005-1] Breen, Michael (2005)、「商用組み込みシステム製品ラインに軽量形式仕様手法を使用した経験」(PDF)、Requirements Engineering Journal、10 (2): 161–172、CiteSeerX 10.1.1.60.5228、doi :10.1007/s00766-004-0209-1、S2CID 16928695

[LevesonEtAl1994-2] Leveson, Nancy; Heimdahl, Mats Per Erik; Hildreth, Holly; Reese, Jon Damon (1994)、「プロセス制御システムの要件仕様」(PDF)、IEEE Transactions on Software Engineering、20 (9): 684–707、CiteSeerX 10.1.1.72.8657、doi :10.1109/32.317428