状態遷移表（じょうたいせんいひょう、"State Transition Table"）は、有限オートマトンの遷移関数 T を記述した表である。この関数はオートマトンの状態から状態への遷移を制御するもので、マシンへの入力を引数とする。ある有限オートマトンの状態遷移図から状態遷移表を作成することが可能であり、その逆も可能である。状態遷移表は一般に二次元の表である。二種類の代表的な形式が存在する。(S: 状態, E: イベント, A: 動作, -: 不正な遷移)(S: 状態, E: イベント, A: 動作, -: ありえない遷移)例としてマシンMの状態遷移表と状態遷移図を示す。想定される全ての入力が表のカラムに列挙されている。想定される全ての状態は行に列挙されている。上記の状態遷移表を見れば、マシンが q（一行目）の状態のとき 1 が入力されると、マシンは q 状態になる。0 が入力されると q 状態になることが二番目のカラムを見ればわかる。j状態遷移図では、q から q への矢印に 0 が付記されているのがそれを表している。非決定性有限オートマトン（NFA）の場合、ある入力によって遷移する先として複数の状態がありうる（そのため非決定性と言う）。これを状態遷移表で表すときは、括弧 { }で囲んで可能性のある全ての状態を列挙する。以下はその例である。この非決定性マシンでは、S 状態で 0が入力されたとき、S と S というふたつの状態を取りうる。最後のカラムは特殊な文字 ε が入力されたときの遷移を示している。これは実は入力がないときの NFA の状態遷移を意味している。このNFAは、S 状態では入力文字を受け付けることなく S に遷移する可能性がある。以上のような場合があるため、この有限オートマトンは非決定性であると言える。状態遷移表から状態遷移図を描くことができる。その簡単な手順は以下のようになる。

出典:wikipedia