状態遷移表
状態遷移表（じょうたいせんいひょう、State Transition Table）は、状態機械類（の遷移関数 T(scurrent, e) = (a, snext)）を、縦横の表にすることで、状態機械を記述したものである。scurrentはその機械の現在の状態（遷移元の状態）、eはイベント（状態機械への入力）、aはアクション（状態機械からの出力）、snextはその機械の次の状態（遷移先の状態）である。状態遷移図も状態機械の記述であるが、それぞれに利点と欠点とあるので、適宜使い分けられている。
代表的な形式
編集状態遷移表は一般に二次元の表である。二種類の代表的な形式が存在する。
- 縦軸（または横軸）は現在の状態を示し、横軸（または縦軸）はイベントを示す。交差する箇所の各マスには、そのイベントが起きたときに次に遷移すべき状態を記述する（そして遷移に伴う動作があれば記述する）。
| イベント 状態 |
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の状態遷移表と状態遷移図を示す。
|
状態遷移図 
|
想定される全ての入力が表のカラムに列挙されている。想定される全ての状態は行に列挙されている。上記の状態遷移表を見れば、マシンが q0（一行目）の状態のとき 1 が入力されると、マシンは q0 状態になる。0 が入力されると q1 状態になることが二番目のカラムを見ればわかる。状態遷移図では、q0 から q1 への矢印に 0 が付記されているのがそれを表している。
非決定性有限オートマトン（NFA）の場合、ある入力によって遷移する先として複数の状態がありうる（そのため非決定性と言う）。これを状態遷移表で表すときは、括弧 { }で囲んで可能性のある全ての状態を列挙する。以下はその例である。
| 入力 状態 |
1 | 0 | ε |
| S1 | S1 | { S2, S3 } | Φ |
| S2 | S2 | S1 | Φ |
| S3 | S2 | S1 | S1 |
この非決定性マシンでは、S1 状態で 0が入力されたとき、S2 と S3 というふたつの状態を取りうる。最後のカラムは特殊な文字 ε が入力されたときの遷移を示している。これは実は入力がないときの NFA の状態遷移を意味している。このNFAは、S3 状態では入力文字を受け付けることなく S1 に遷移する可能性がある。以上のような場合があるため、この有限オートマトンは非決定性であると言える。
状態遷移図との変換
編集状態遷移表から状態遷移図を描くことができる。その簡単な手順は以下のようになる。
- 表に出てくる状態に対応した円を描く。
- 各状態について、対応する行を見て、遷移先の状態（群）への矢印を描く。そのオートマトンがNFAの場合、一種類の入力で複数の矢印が存在する場合がある。
- ひとつの状態を開始状態とする。開始状態は正式なオートマトンの定義では必須である。
- ひとつ以上の状態を受容状態とする。受容状態も正式なオートマトンの定義では必須である。一連の入力が与えられたときに最後にそのオートマトンがたどり着いた状態が受容状態なら、その入力を受容したと判断でき、受容状態でない状態にたどり着いたときはその入力文字列を受容しなかったと判断される。
関連項目
編集- JIS X 0131、ISO/IEC 11411 - 関連規格