状態遷移表 状態遷移表の概要

ウィキペディア

状態遷移表

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/09 23:52 UTC 版)

代表的な形式

状態遷移表は一般に二次元の表である。二種類の代表的な形式が存在する。

• 縦軸（または横軸）は現在の状態を示し、横軸（または縦軸）はイベントを示す。交差する箇所の各マスには、そのイベントが起きたときに次に遷移すべき状態を記述する（そして遷移に伴う動作があれば記述する）。

状態遷移表

イベント 状態	E1	E2	...	En
S1	-	Ay/Sj	...	-
S2	-	-	...	Ax/Si
...	...	...	...	...
Sm	Az/Sk	-	...	-

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

• 縦軸（または横軸）は現在の状態を示し、横軸（または縦軸）は次の状態を示す。交差する箇所の各マスは、その遷移を発生させるイベントを記述する。グラフ理論における隣接行列を拡張したものと言える。

状態遷移表

次の状態 現在状態	S1	S2	...	Sm
S1	Ay/Ej	-	...	-
S2	-	-	...	Ax/Ei
...	...	...	...	...
Sm	-	Az/Ek	...	-

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

例

例としてマシンMの状態遷移表と状態遷移図を示す。

状態遷移表   入力 状態 1 0 q0 q0 q1 q1 q1 q0

状態遷移図

想定される全ての入力が表のカラムに列挙されている。想定される全ての状態は行に列挙されている。上記の状態遷移表を見れば、マシンが q₀（一行目）の状態のとき 1 が入力されると、マシンは q₀ 状態になる。0 が入力されると q₁ 状態になることが二番目のカラムを見ればわかる。状態遷移図では、q₀ から q₁ への矢印に 0 が付記されているのがそれを表している。

非決定性有限オートマトン（NFA）の場合、ある入力によって遷移する先として複数の状態がありうる（そのため非決定性と言う）。これを状態遷移表で表すときは、括弧 { }で囲んで可能性のある全ての状態を列挙する。以下はその例である。

NFA の状態遷移表

入力 状態	1	0	ε
S1	S1	{ S2, S3 }	Φ
S2	S2	S1	Φ
S3	S2	S1	S1

この非決定性マシンでは、S₁ 状態で 0が入力されたとき、S₂ と S₃ というふたつの状態を取りうる。最後のカラムは特殊な文字 ε が入力されたときの遷移を示している。これは実は入力がないときの NFA の状態遷移を意味している。このNFAは、S₃ 状態では入力文字を受け付けることなく S₁ に遷移する可能性がある。以上のような場合があるため、この有限オートマトンは非決定性であると言える。

状態遷移図との変換

状態遷移表から状態遷移図を描くことができる。その簡単な手順は以下のようになる。

1. 表に出てくる状態に対応した円を描く。
2. 各状態について、対応する行を見て、遷移先の状態（群）への矢印を描く。そのオートマトンがNFAの場合、一種類の入力で複数の矢印が存在する場合がある。
3. ひとつの状態を開始状態とする。開始状態は正式なオートマトンの定義では必須である。
4. ひとつ以上の状態を受容状態とする。受容状態も正式なオートマトンの定義では必須である。一連の入力が与えられたときに最後にそのオートマトンがたどり着いた状態が受容状態なら、その入力を受容したと判断でき、受容状態でない状態にたどり着いたときはその入力文字列を受容しなかったと判断される。