状態遷移表

状態遷移表は、状態機械の振る舞いを記述するための表形式の表現方法です。具体的には、機械の現在の状態、入力イベント、それによって引き起こされるアクション、そして遷移先の状態を明確に示します。この表は、状態機械の動作を理解し、設計する上で非常に役立ちます。

状態遷移表の構造

状態遷移表は、一般的に二次元の表として構成されます。主な形式は二つあり、それぞれに特徴があります。

1. 状態とイベントに基づく形式
縦軸（または横軸）に現在の状態、横軸（または縦軸）に入力イベントを配置します。
各マスには、特定のイベントが発生した場合に遷移すべき次の状態と、必要に応じて実行されるアクションを記述します。

例: `(S: 状態, E: イベント, A: 動作, -: 不正な遷移)`

2. 状態と次の状態に基づく形式
縦軸（または横軸）に現在の状態、横軸（または縦軸）に遷移先の状態を配置します。
各マスには、特定の状態遷移を引き起こすイベントを記述します。
この形式は、グラフ理論における隣接行列を拡張したものと考えることができます。

例: `(S: 状態, E: イベント, A: 動作, -: ありえない遷移)`

状態遷移表の例

以下に、簡単な例を示します。この例では、マシンMが二つの状態（q0とq1）を持ち、二つの入力（0と1）を受け付けると仮定します。

現在の状態	入力0	入力1
-	-	---
q0	q1	q0
q1	q1	q0

この表から、マシンがq0の状態の時に0が入力されるとq1状態に遷移し、1が入力されるとq0状態を維持することがわかります。同様に、マシンがq1状態の時に0が入力されるとq1状態を維持し、1が入力されるとq0状態に遷移します。

状態遷移図と比較すると、状態遷移表は全ての状態と入力に対する遷移を網羅的に記述するのに優れています。状態遷移図は視覚的に分かりやすいですが、複雑な状態機械になると図が煩雑になる可能性があります。

非決定性有限オートマトン（NFA）

非決定性有限オートマトン（NFA）の場合、一つの入力に対して複数の遷移先が存在する可能性があります。状態遷移表では、これを中括弧`{ }`を用いて複数の状態を列挙することで表現します。

現在の状態	入力0	入力1	ε
-	-	-	-
S1	{S2, S3}	{S1}	-
S2	{S1}	-	-
S3	-	-	{S1}

この例では、状態S1で入力0が与えられた場合、S2とS3の両方に遷移する可能性があります。また、状態S3では、ε（入力がない状態）によってS1に遷移する可能性があります。このように、NFAは非決定的な動作を表現できます。

状態遷移表から状態遷移図への変換

状態遷移表から状態遷移図を作成する手順は以下の通りです。

1. 状態に対応する円を描く：状態遷移表に現れる各状態を、状態遷移図上の円で表現します。
2. 状態遷移を表す矢印を描く：各状態に対して、状態遷移表の対応する行を見て、遷移先の状態への矢印を描きます。NFAの場合は、複数の遷移先があることを表現します。
3. 開始状態を定める：状態遷移図上で、オートマトンの開始状態を特定します。
4. 受容状態を定める：オートマトンの受容状態（または終状態）を一つ以上特定します。受容状態は二重円で表されることが一般的です。

これらの手順に従うことで、状態遷移表から視覚的に理解しやすい状態遷移図を作成することができます。

まとめ

状態遷移表は、状態機械の設計と分析において非常に重要なツールです。状態と入力に基づいて次の状態を明確に定義することで、システムの振る舞いを正確に記述し、理解を深めることができます。また、状態遷移表から状態遷移図を生成することで、システムの構造をより視覚的に把握することができます。

状態遷移表は、ソフトウェア開発、ハードウェア設計、さらにはモデルベース開発など、多くの分野で応用されています。これらの分野では、システムの複雑さが増すにつれて、状態遷移表の有用性がますます高まっています。

関連規格

JIS X 0131、ISO/IEC 11411 - 関連規格

もう一度検索