状態遷移

ウィキペディア

状態遷移図

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/12/23 01:34 UTC 版)

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

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

有向グラフ

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

• 各辺（エッジ）はふたつの状態の間の遷移を表す。
  • ムーア・マシンでは各エッジに入力を付記する。
  • ミーリ・マシンでは各エッジに入力と出力を付記する。
• 各頂点（ノード）は状態を表す。
  • ムーア・マシンでは各状態に出力を付記する。

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

例

ムーア・マシン

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

ミーリ・マシン

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

ハレルの状態遷移図

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

UML

UML状態機械図の例

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

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

その他の拡張

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

もう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年, [1]
• 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

関連項目

• JIS X 0131、ISO/IEC 11411 - 関連規格

外部リンク

• David Harel's home page
• D. Harel. Statecharts: A visual formalism for complex systems. Science of Computer Programming, 8(3):231--274, June 2002.
• IntelliWizard - UML StateWizard - 状態遷移図からのソフトウェア作成を支援するオープンソースのソフトウェア
• IslayPub - 状態遷移図でゲームを作れるサイト

Weblio日本語例文用例辞書

「状態遷移」の例文・使い方・用例・文例

• 情報科学において,状態遷移が一意的でないオートマトン