状態遷移図
出典: フリー百科事典『ウィキペディア（Wikipedia）』
状態遷移図（じょうたいせんいず、State Diagram）は、有限オートマトンをグラフィカルに表現するのに使われる図である。他の表現手法として状態遷移表がある。
状態遷移図には微妙に異なる形式のものが存在し、意味的にも相違がある。
目次 |
[編集] 有向グラフ
有限オートマトンの状態遷移図の古典的な形式は有向グラフであり、以下のような形式である。
- 各エッジはふたつの状態の間の遷移を表す。
- 決定性有限オートマトン（DFA）、非決定性有限オートマトン（NFA）、ムーア・マシンでは各エッジに入力を付記する。
- ミーリ・マシンでは各エッジに入力と出力を付記する。
- 各頂点（ノード）は状態を表す。
- ムーア・マシンでは各状態に出力を付記する。
一般には、頂点（ノード）は円で描かれ、必要ならば受容状態は二重円を使用する。
[編集] 例
[編集] DFA, NFA, ムーア・マシン
q0 と q1 は状態であり、q0は受容状態である。各エッジには入力が付記されている。
[編集] ミーリ・マシン
S0, S1, S2 は状態である。各エッジに付記されているラベルを "j / k" とすると、 jは入力を表し k は出力を表す。
[編集] ハレルの状態遷移図
ハレルの状態遷移図（デビッド・ハレル氏が1987年に開発）はハレルチャートとも呼ばれ、広く使われている。例えば、UMLの一部となっている状態遷移図はハレルチャートからの派生である。この図は上位状態を表現したり、並列状態を表現することができ、状態の内部の活動をモデル化できる。
古典的な状態遷移図は、マシンがどれかひとつの状態をとることしか表せない。これに対してハレルの状態遷移図は、マシンが同時に複数の状態になることを表すことができる。これは上位状態というものを導入しているためである。
[編集] UML 状態遷移図
UMLの状態遷移図はコンピュータプログラムからビジネスプロセスまで様々な事象を記述できるよう標準化されたものである。以下のような要素を使って図を作成できる。
- 塗りつぶされた円が START（開始）を意味する。必須ではない。
- 中抜きの円は STOP（停止）を意味する。必須ではない。
- 四角形で状態を表す。四角形の上部には状態名を記述する。中ほどに水平な線を引いて、その下に当該状態下で行われる活動を記述する。
- 矢印が遷移を表す。括弧（ [] ）付きで書かれた式を付記し、その式が真のときに遷移が発生することを表す。
- 太い水平線で複数の線（遷移を表す矢印線）をひとつの線にまとめたり、その逆をする。これは join/fork と呼ばれ、並列状態の終了と開始を意味する。
[編集] その他の拡張
興味深い拡張として、矢印線が複数の状態から複数の状態へと接続することを許すものがある。これはシステムが同時並行する複数の状態を許す場合に意味があり、各状態はひとつの条件か過渡的な状態を表していて、それらが複合して全体の状態を表す。これを形式化したものがペトリネットである。
