状態図

状態図は、コンピュータ サイエンスや関連分野でシステムの動作を説明するために使用されます。状態図では、システムが有限の数の状態から構成されている必要があります。これは実際に当てはまる場合もありますが、合理的な抽象化である場合もあります。状態図にはさまざまな形式があり、それぞれがわずかに異なり、意味も異なります。

状態図は、システムの動作の抽象的な説明を提供します。この動作は、1 つ以上の可能な状態で発生する可能性のある一連のイベントによって分析および表現されます。これにより、「各図は通常、単一のクラスのオブジェクトを表し、システムを通じてオブジェクトのさまざまな状態を追跡します」。^[1]

状態図は、有限状態マシン(有限オートマトンとも呼ばれる) をグラフィカルに表現するために使用できます。これは、 1949 年の著書「通信の数学的理論」でClaude ShannonとWarren Weaverによって導入されました。もう 1 つの出典は、1967 年の著書「Sequential Machines and Automata Theory」のTaylor Boothです。もう 1 つの表現方法として、状態遷移表があります。

有限オートマトン（FA）の状態図の典型的な形式は、次の要素（Q、Σ、Z、δ、q ₀、F）を持つ有向グラフである： ^{[2] [3]}

• 頂点Q : 通常は円で表され、固有の指定記号またはその中に書かれた単語でラベル付けされた有限の状態の集合。
• 入力記号 Σ : 入力記号または指定子の有限集合
• 出力シンボルZ : 出力シンボルまたは指定子の有限集合

出力関数 ω は、入力シンボルと状態の順序付けられたペアを出力シンボルにマッピングすることを表し、数学的にはω  : Σ × Q → Zと表されます。

• エッジ δ : 入力によって引き起こされる、ある状態から別の状態への遷移を表します (エッジに描かれたシンボルで識別されます)。エッジは通常、現在の状態から次の状態に向かう矢印として描かれます。このマッピングは、入力によって引き起こされる状態遷移を表します。これは数学的にはδ  : Q × Σ → Qと記述されるため、FA の定義における δ (遷移関数) は、エッジで接続された頂点のペアと、この FA を表す図のエッジ上のシンボルの両方によって与えられます。FAの定義における項目δ(q, a) = p は、入力シンボルaの下でqという名前の状態から、このマシンで状態pへの遷移が発生することを意味します。この FA を表す図では、これはqというラベルの頂点からpというラベルの頂点を指すaというラベルのエッジで表されます。
• 開始状態 q ₀ : (以下の例では示されていません)。開始状態 q ₀ ∈ Q は通常、状態を指す原点のない矢印で表されます。古いテキストでは、^{[2] [4]}開始状態は示されておらず、テキストから推測する必要があります。
• 受理状態 F : 例えば受理オートマトンに使用される場合、 F ∈ Q は受理状態です。通常は二重円で描かれます。受理状態は「最終」（停止、閉じ込め）状態として機能することもあります。 [ ^3]

決定性有限オートマトン(DFA)、非決定性有限オートマトン(NFA)、一般化非決定性有限オートマトン(GNFA)、またはムーア マシンの場合、入力は各辺で示されます。ミーリー マシンの場合、入力と出力は各辺で示され、スラッシュ "/" で区切られます。"1/0" は、シンボル "1" に遭遇すると状態が変化し、シンボル "0" が出力されることを示します。ムーア マシンの場合、状態の出力は通常、状態の​​円の中に記述され、状態指定子からもスラッシュ "/" で区切られます。これら 2 つの表記法を組み合わせたバリエーションもあります。

たとえば、ある状態に複数の出力がある場合 (例: 「a = モーター反時計回り = 1、b = 注意ライト非アクティブ = 0」)、図はこれを反映する必要があります。例: 「q5/1,0」は、出力 a = 1、b = 0 の状態 q5 を示します。この指定子は、状態の円の内側に記述されます。

S ₁とS _{2 は}状態であり、S _{1 は}受け入れ状態または最終状態です。各エッジには入力のラベルが付けられています。この例は、偶数個のゼロを含む 2 進数のアクセプタを示しています。

S ₀、S ₁、およびS _{2 は}状態です。各エッジには「j / k」というラベルが付けられています。ここで、jは入力、kは出力です。

コンピュータ科学者のデイビッド・ハレルによって発明されたハレルステートチャート^{[5]は、その変種が}統一モデリング言語(UML)の一部となって以来、広く使用されるようになっています。 ^{[非一次資料が必要]この図の種類により、}スーパーステート、直交領域、およびアクティビティを状態の一部として モデリングできます。

従来の状態図では、状態を定義するパラメータの有効な組み合わせごとに個別のノードを作成する必要があります。最も単純なシステムを除き、これによりノードとノード間の遷移の数が非常に多くなり (状態と遷移の急増)、状態図の可読性が低下します。Harel ステートチャートを使用すると、ステートチャート内で複数の機能横断型状態図をモデル化できます。これらの機能横断型ステート マシンはそれぞれ、他のステート マシンに影響を与えることなく内部的に遷移できます。機能横断型ステート マシンの現在の状態によって、システムの状態が定義されます。Harel ステートチャートは状態図と同等ですが、可読性が向上しています。

状態図を表現するために利用できるセマンティクスのセットは他にもあります。たとえば、組み込みコントローラのロジックをモデリングおよび設計するためのツールがあります。^[6]これらの図は、Harelのオリジナルの状態マシンと同様に、^[7]階層的にネストされた状態、直交領域、状態アクション、および遷移アクションをサポートします。^[8]

ステートマシン形式を初めて学ぶ人は、状態図とフローチャートを混同することが多い。下の図は、状態図とフローチャートの比較を示している。ステートマシン（パネル（a））は、明示的なイベントに応じてアクションを実行する。対照的に、フローチャート（パネル（b））は、アクティビティが完了するとノードからノードへと自動的に遷移する。^[9]

フローチャートのノードは、状態の誘導グラフ内のエッジです。これは、フローチャート内の各ノードがプログラム コマンドを表すためです。プログラム コマンドは、実行されるアクションです。コマンドは状態ではありませんが、プログラムの状態に適用されると、別の状態への遷移を引き起こします。

詳しく言うと、ソース コード リストはプログラム グラフを表します。プログラム グラフ (解析と解釈) を実行すると、状態グラフが生成されます。したがって、各プログラム グラフは状態グラフを誘導します。プログラム グラフを関連する状態グラフに変換することを、プログラム グラフの「展開」と呼びます。

プログラム グラフはコマンドのシーケンスです。変数が存在しない場合は、状態はプログラム カウンターのみで構成され、実行中にプログラムの位置 (次に適用されるコマンド) を追跡します。

コマンドを実行する前、プログラム カウンターはある位置 (コマンドを実行する前の状態) にあります。コマンドを実行すると、プログラム カウンターは次のコマンドに移動します。プログラム カウンターは状態全体であるため、コマンドを実行すると状態が変わります。したがって、コマンド自体は 2 つの状態間の遷移に対応します。

ここで、変数が存在し、実行中のプログラム コマンドによって影響を受ける完全なケースを考えてみましょう。プログラム カウンターは異なるプログラム カウンターの場所間で変化するだけでなく、実行されたコマンドによって変数の値も変化する可能性があります。その結果、あるプログラム コマンド (たとえばループ内) を再度実行しても、プログラムが同じ状態にあるとは限りません。

前のケースでは、状態全体がプログラム カウンターだけなので、プログラムは同じ状態になります。したがって、プログラム カウンターが同じ位置 (次のコマンド) を指している場合は、同じ状態にあると指定するだけで十分です。ただし、状態に値が変化する変数が含まれている場合は、変数値が異なっていても同じプログラム位置にある可能性があります。つまり、プログラムの状態空間内の状態が異なります。「展開」という用語は、プログラム グラフから状態グラフを生成するときに位置が倍増することから来ています。

自己遷移とは、初期状態と最終状態が同じである遷移です。

代表的な例としては、カウンタがオーバーフローして再び 0 になるまでカウンタを増分する do ループがあります。do ループは同じ増分コマンドを繰り返し実行しますが、その状態空間はサイクルではなく行です。これは、状態がプログラムの場所 (ここでは循環) とカウンタ値 (オーバーフローするまで厳密に増加) を組み合わせた結果です。したがって、オーバーフローが発生するまで、異なる状態が順番に訪れられます。オーバーフロー後、カウンタは再び 0 になるため、状態空間で初期状態が再び訪れられ、状態空間のサイクルが閉じます (カウンタが 0 に初期化されていると仮定)。

上の図は、状態図の弧をフローチャートの処理段階に合わせることで、役割の逆転を表現しようとしています。

フローチャートは、あるタスクの最初から最後までの進行 (たとえば、コンパイラによるソース コード入力のオブジェクト コード出力への変換) を記述するため、製造業の組立ラインに例えることができます。通常、ステート マシンにはこのような進行の概念はありません。上記のドア ステート マシンの例は、「閉じた」状態が「開いた」状態よりも進んだ段階にあるわけではありません。むしろ、単に開閉イベントに対して異なる反応を示すだけです。ステート マシンの状態は、処理の段階ではなく、動作を指定するための効率的な方法です。

興味深い拡張として、アークが任意の数の状態から任意の数の状態へ流れるようにすることができます。これは、システムが同時に複数の状態になることが許可されている場合にのみ意味を持ちます。つまり、個々の状態は、全体的なグローバル状態の状態またはその他の部分的な側面のみを記述します。結果として得られる形式は、ペトリ ネットとして知られています。

別の拡張機能により、Harel ステートチャート内にフローチャートを統合できます。この拡張機能は、イベント駆動型とワークフロー駆動型の両方のソフトウェアの開発をサポートします。

• デビッド・ハレル
• ドラコン
• SCXML は、 Harel ステートチャートに基づく汎用ステートマシン ベースの実行環境を提供する XML 言語です。
• UML ステートマシン
• YAKINDU Statechart Toolsは、状態図 (Harel 状態図、Mealy マシン、Moore マシン) のモデリング、シミュレーション、およびソース コード生成を行うソフトウェアです。

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

• Scott W. Ambler著 UML 2 ステートマシン図入門
• UML 2 ステートマシン図ガイドライン (Scott W. Ambler 著)
• Intelliwizard - UML StateWizard - オープンソース ライセンスの下で一般的な IDE で実行されていた、廃止されたラウンドトリップ UML 動的モデリング/開発フレームワークおよびツール。
• YAKINDU ステートチャート ツール -ステート マシンの助けを借りて、リアクティブでイベント駆動型のシステムの仕様を定義および開発するためのオープン ソース ツール。
• ステートマシンの理解と使用 ステートマシンに関する MATLAB 技術講演
• FSM: Alexander Sakharov による Java でのオープンソースの有限状態マシン生成 FSM
• scxmlcc C++ コンパイラーへの効率的な scxml ステート マシン。
• SMC: C、Python、Lua、Scala、PHP、Java、VB などの多くの言語の FSM を生成するオープンソースのステートマシンコンパイラ。SMC