状態遷移図

状態遷移図

状態遷移図（じょうたいせんいず、”State Diagram”）は、有限オートマトンをグラフィカルに表現するのに使われる図である。他の表現手法として状態遷移表がある。
状態遷移図には微妙に異なる形式のものが存在し、意味的にも相違がある。
有限オートマトンの状態遷移図の古典的な形式はグラフ理論 有向グラフであり、以下のような形式である。
各エッジはふたつの状態の間の遷移を表す。
決定性有限オートマトン（DFA）、非決定性有限オートマトン（NFA）、ムーア・マシンでは各エッジに入力を付記する。
ミーリ・マシンでは各エッジに入力と出力を付記する。
各頂点（ノード）は状態を表す。

『フリー百科事典ウィキペディア日本語版』 2006/09/09/08/06、URL: http://ja.wikipedia.org/