状態遷移図

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

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

有向グラフ

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

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

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

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

ハレルの状態遷移図（デビッド・ハレルが1987年に開発）はハレルチャートとも呼ばれ、広く使われている。「上位状態」を表現したり、並列状態を表現することができ、状態の内部の活動をモデル化できる。

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

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

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

Introduction to UML 2 State Machine Diagrams by Scott W. Ambler
UML 2 State Machine Diagram Guidelines by Scott W. Ambler
Modelling and verification using UML statecharts, Drusinsky, D., エルゼビア, 2006年,
Michael Sipser (2006), Introduction to the Theory of Computation, Second Edition, Thomson Course Technology, Boston. ISBN 978-0-534-95097-2.
John Hopcroft and Jeffrey Ullman (2002) Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Company, Reading Mass, ISBN 0-201-02988-X.
Taylor Booth (2002) Sequential Machines and Automata Theory, John Wiley and Sons, New York. Library of Congress Catalog Card Number: 67-25924.
Practical Statecharts in C/C++ by Miro Samek

ウィキメディア・コモンズには、状態遷移図に関連するカテゴリがあります。