状態遷移図

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

状態遷移図(じょうたいせんいず、State Transition Diagram)は、有限オートマトンなどの状態機械について、その各状態を頂点とし、状態から状態への各遷移を辺としたグラフ構造に注目して、グラフィカルに表現した図である。他の表現手法として状態遷移表などがある。

状態遷移図にはいくつかの異なる形式のものがある。対象の性質や用途などによって使い分けることもある。

有向グラフ[編集]

有限オートマトン状態遷移図の古典的な形式は有向グラフであり、以下のような形式である。

一般には、頂点(ノード)は円で描かれ、必要ならば受容状態は二重円を使用する。

[編集]

DFA, NFA, ムーア・マシン[編集]

q0q1 は状態であり、q0は受容状態である。各エッジには入力が付記されている。

Even Number of Zeros DFA.png

ミーリ・マシン[編集]

S0, S1, S2 は状態である。各エッジに付記されているラベルを "j / k" とすると、 jは入力を表し k は出力を表す。

Mealy automaton.png

ハレルの状態遷移図[編集]

ハレルの状態遷移図(デビッド・ハレルが1987年に開発)はハレルチャートとも呼ばれ、広く使われている。例えば、UMLの一部となっている状態遷移図はハレルチャートからの派生である。この図は上位状態を表現したり、並列状態を表現することができ、状態の内部の活動をモデル化できる。

古典的な状態遷移図は、マシンがどれかひとつの状態をとることしか表せない。これに対してハレルの状態遷移図は、マシンが同時に複数の状態になることを表すことができる。これは上位状態というものを導入しているためである。

UML[編集]

UML状態機械図の例

UMLではstate machine diagram(状態機械図)という。次のように標準化した。

  • 塗りつぶされた円が START(開始)を意味する。必須ではない。
  • 中抜きの円は STOP(停止)を意味する。必須ではない。
  • 四角形で状態を表す。四角形の上部には状態名を記述する。中ほどに水平な線を引いて、その下に当該状態下で行われる活動を記述する。
  • 矢印が遷移を表す。括弧( [ ] )付きで書かれた式を付記し、その式が真のときに遷移が発生することを表す。
  • 太い水平線で複数の線(遷移を表す矢印線)をひとつの線にまとめたり、その逆をする。これは join/fork と呼ばれ、並列状態の終了と開始を意味する。

その他の拡張[編集]

興味深い拡張として、矢印線が複数の状態から複数の状態へと接続することを許すものがある。これはシステムが同時並行する複数の状態を許す場合に意味があり、各状態はひとつの条件か過渡的な状態を表していて、それらが複合して全体の状態を表す。これを形式化したものがペトリネットである。

もう1つの拡張として、フローチャートとハレルの状態遷移図を統合したものがある。この拡張はイベント駆動型とワークフロー駆動型の両方のソフトウェアの開発をサポートする。

参考文献[編集]

外部リンク[編集]