Loading article…
状態図は、コンピュータサイエンスおよび関連分野において、システムの挙動を記述するために用いられる。状態図では、システムが有限個の状態から構成されていることが前提となる。実際、システムが有限個の状態から構成されている場合もあれば、これは妥当な抽象化である場合もある。状態図には様々な形式が存在し、それぞれに微妙な違いがあり、意味論も異なる。
状態図は、システムの振る舞いを抽象的に記述するものです。この振る舞いは、1つ以上の可能な状態で発生する一連のイベントによって分析され、表現されます。ここで、「各図は通常、単一クラスのオブジェクトを表し、システム全体を通してそのオブジェクトのさまざまな状態を追跡します」。[ 1 ]
状態図は、有限状態機械（有限オートマトンとも呼ばれる）をグラフィカルに表現するために使用できます。これは、クロード・シャノンとウォーレン・ウィーバーが1949年に著した『通信の数学的理論』で紹介されました。テイラー・ブースも1967年に著した『逐次機械とオートマトン理論』でこの概念を取り上げています。状態遷移表も別の表現方法です。
有限オートマトン(FA)の状態図の古典的な形式は、次の要素 (Q、Σ、Z、δ、q 0、F)を持つ有向グラフです。 [ 2 ] [ 3 ]
出力関数ωは、入力シンボルと状態の順序対を出力シンボルにマッピングするもので、数学的にはω : Σ × Q → Zと表されます。
決定性有限オートマトン(DFA)、非決定性有限オートマトン(NFA)、一般化非決定性有限オートマトン(GNFA)、またはムーアマシンでは、入力は各エッジに示されます。ミーリーマシンでは、入力と出力は各エッジに示され、スラッシュ「/」で区切られます。「1/0」は、記号「1」に遭遇したときに状態が変化し、記号「0」が出力されることを示します。ムーアマシンでは、状態の出力は通常、状態の円の中に書かれ、状態指定子とはスラッシュ「/」で区切られます。これら2つの表記法を組み合わせたバリエーションもあります。
例えば、ある状態が複数の出力を持つ場合（例：「a=モーター反時計回り=1、b=警告灯非作動=0」）、図にはそれが反映される必要があります 。例えば、「q5/1,0」は、出力a=1、b=0を持つ状態q5を表します。この指定子は、状態を表す円の中に書き込まれます。
S1とS2は状態であり、S1は受理状態または最終状態です。各エッジには入力がラベル付けされています。この例は、偶数個のゼロを含む2進数に対する受理器を示しています。
S 0、S 1、S 2は状態を表します。各エッジには「j / k」というラベルが付けられており、 jは入力、kは出力を表します。
コンピュータ科学者のデイビッド・ハレルによって考案されたハレル状態図[ 5 ]は、その派生形が統一モデリング言語（UML）の一部となったことで広く使用されるようになっている。この図式タイプでは、状態の一部としてスーパーステート、直交領域、アクティビティをモデル化することができる。
従来のステート図では、状態を定義するパラメータの有効な組み合わせごとに個別のノードを作成する必要があります。最も単純なシステムを除いて、これはノードとノード間の遷移の数が非常に多くなること（状態と遷移の爆発）につながり、ステート図の可読性を低下させます。Harelステートチャートを使用すると、ステートチャート内で複数のクロスファンクショナルステート図をモデル化できます。これらのクロスファンクショナルステートマシンはそれぞれ、他のステートマシンに影響を与えることなく内部的に遷移できます。各クロスファンクショナルステートマシンの現在の状態が、システムの状態を定義します。Harelステートチャートはステート図と同等ですが、可読性が向上しています。
状態図を表現するために利用できるセマンティクスは他にもあります。たとえば、組み込みコントローラのロジックをモデル化および設計するためのツールがあります。[ 6 ]これらの図は、Harel のオリジナルの状態機械と同様に、[ 7 ]階層的にネストされた状態、直交領域、状態アクション、および遷移アクションをサポートしています。[ 8 ]
状態機械の形式体系を初めて学ぶ人は、状態図とフローチャートを混同しがちです。下の図は、状態図とフローチャートの比較を示しています。状態機械（パネル（a））は、明示的なイベントに応じて動作を実行します。一方、フローチャート（パネル（b））は、アクティビティの完了時にノードからノードへ自動的に遷移します。[ 9 ]
フローチャートのノードは、誘導された状態グラフにおけるエッジです。これは、フローチャートの各ノードがプログラムコマンドを表すためです。プログラムコマンドとは、実行されるアクションのことです。コマンドは状態ではありませんが、プログラムの状態に適用されると、別の状態への遷移を引き起こします。
より詳しく説明すると、ソースコードのリストはプログラムグラフを表します。プログラムグラフを実行（解析および解釈）すると、状態グラフが生成されます。つまり、各プログラムグラフは状態グラフを生成します。プログラムグラフをそれに対応する状態グラフに変換することを、プログラムグラフの「展開」と呼びます。
プログラムグラフは一連のコマンドで構成されます。変数が存在しない場合、状態はプログラムカウンタのみで構成され、実行中のプログラムの位置（次に適用されるコマンド）を追跡します。
コマンドを実行する前、プログラムカウンタはある位置（コマンド実行前の状態）にあります。コマンドを実行すると、プログラムカウンタは次のコマンドに移動します。プログラムカウンタは全体の状態を表しているため、コマンドを実行することで状態が変化します。したがって、コマンド自体は2つの状態間の遷移に対応します。
次に、変数が存在し、実行されるプログラムコマンドによって影響を受ける場合を考えてみましょう。プログラムカウンタが異なる場所間で変化するだけでなく、実行されたコマンドによって変数の値も変化する可能性があります。したがって、ループなどで特定のプログラムコマンドを再度実行したとしても、プログラムの状態が同じであるとは限りません。
前述のケースでは、プログラムの状態全体がプログラムカウンタであるため、プログラムは同じ状態になります。したがって、プログラムカウンタが同じ位置（次のコマンド）を指している場合は、同じ状態にあることを指定すれば十分です。しかし、状態に値が変化する変数が含まれている場合、同じプログラム位置でも変数の値が異なることがあり、つまりプログラムの状態空間では異なる状態にあることになります。「展開」という用語は、プログラムグラフから状態グラフを生成する際に、このように位置が複数になることに由来しています。
自己遷移とは、初期状態と最終状態が同じである遷移のことである。
代表的な例として、カウンタがオーバーフローして再び0になるまで、カウンタをインクリメントするdoループが挙げられます。doループは同じインクリメントコマンドを繰り返し実行しますが、その状態空間はサイクルではなく直線になります。これは、状態がプログラムの位置（ここでは循環）と、厳密に増加するカウンタ値（オーバーフローするまで）の組み合わせであることに起因します。したがって、オーバーフローが発生するまで、異なる状態が順番に訪れます。オーバーフロー後、カウンタは再び0になるため、状態空間では初期状態が再び訪れられ、状態空間のサイクルが閉じられます（カウンタが0に初期化されていたと仮定した場合）。
上の図は、状態図の弧をフローチャートの処理段階に合わせることで、役割の逆転を示そうとしている。
フローチャートは、製造業における組立ラインに例えることができます。フローチャートは、あるタスクの開始から終了までの進行状況（例えば、ソースコード入力をコンパイラがオブジェクトコード出力に変換する過程）を記述するからです。一方、ステートマシンは一般的に、このような進行状況の概念を持ちません。上記のドアのステートマシンの例では、「閉じた」状態は「開いた」状態よりも進行段階が進んでいるわけではありません。単に、開閉イベントに対する反応が異なるだけです。ステートマシンにおける状態は、処理の段階ではなく、動作を効率的に指定する方法なのです。
興味深い拡張として、任意の数の状態から任意の数の状態へアークが流れるようにすることが挙げられます。これは、システムが同時に複数の状態をとることが許される場合にのみ意味を持ちます。つまり、個々の状態は、全体的なグローバル状態の条件やその他の部分的な側面のみを記述するということです。結果として得られる形式は、ペトリネットとして知られています。
別の拡張機能では、フローチャートをHarelステートチャートに統合できます。この拡張機能は、イベント駆動型とワークフロー駆動型の両方のソフトウェア開発をサポートします。