状態遷移表

状態遷移表（じょうたいせんいひょう、"State Transition Table"）は、状態機械類（の遷移関数 T(scurrent, e) = (a, snext)）を、縦横の表にすることで、状態機械を記述したものである。scurrentはその機械の現在の状態（遷移元の状態）、eはイベント（状態機械への入力）、aはアクション（状態機械からの出力）、snextはその機械の次の状態（遷移先の状態）である。状態遷移図も状態機械の記述であるが、それぞれに利点と欠点とあるので、適宜使い分けられている。
代表的な形式.
状態遷移表は一般に二次元の表である。二種類の代表的な形式が存在する。
例.
例としてマシンMの状態遷移表と状態遷移図を示す。
想定される全ての入力が表のカラムに列挙されている。想定される全ての状態は行に列挙されている。上記の状態遷移表を見れば、マシンが q0（一行目）の状態のとき 1 が入力されると、マシンは q0 状態になる。0 が入力されると q1 状態になることが二番目のカラムを見ればわかる。状態遷移図では、q0 から q1 への矢印に 0 が付記されているのがそれを表している。
非決定性有限オートマトン（NFA）の場合、ある入力によって遷移する先として複数の状態がありうる（そのため非決定性と言う）。これを状態遷移表で表すときは、括弧 { }で囲んで可能性のある全ての状態を列挙する。以下はその例である。
この非決定性マシンでは、S1 状態で 0が入力されたとき、S2 と S3 というふたつの状態を取りうる。最後のカラムは特殊な文字 ε が入力されたときの遷移を示している。これは実は入力がないときの NFA の状態遷移を意味している。このNFAは、S3 状態では入力文字を受け付けることなく S1 に遷移する可能性がある。以上のような場合があるため、この有限オートマトンは非決定性であると言える。
状態遷移図との変換.
状態遷移表から状態遷移図を描くことができる。その簡単な手順は以下のようになる。