ステートマシンとは何か？基本概念・型・設計・検証・実装までを徹底解説
エバープレイ編集部ステートマシンとは何か — 基本概念と定義
ステートマシン（state machine, 状態機械）は、システムが「状態（state）」と「遷移（transition）」によって振る舞いを記述するモデルです。システムはある時点で必ず何らかの状態にあり、イベントや入力が発生すると条件に応じて別の状態へ遷移し、必要に応じて出力や副作用（アクション）を行います。特に有限個の状態で振る舞いを表現するものは有限オートマトン（finite-state machine, FSM）と呼ばれ、理論的にも実用的にも幅広く用いられます。
形式的定義（有限オートマトンの基本5要素）
- 状態集合 S
- 入力アルファベット Σ（イベント集合）
- 遷移関数 δ（遷移ルール）
- 開始状態 s0 ∈ S
- 受理状態（または出力の定義）
この定義は理論計算機科学で用いられるもので、実務では出力やエントリ/エグジット時のアクション、ガード条件、ヒエラルキーなどを付けて拡張されます。
主要な種類：DFA/NFA、Mealy/Moore、ステートチャート
- 決定性オートマトン（DFA）と非決定性オートマトン（NFA）：DFAは任意の状態・入力に対して遷移先が一意、NFAは複数またはゼロの遷移が許されます。理論上NFAはDFAに変換可能（状態爆発の可能性あり）です。
- Mealy機とMoore機：どのタイミングで出力を決めるかの差。Mealyは遷移に紐づく出力、Mooreは状態に紐づく出力を持ちます。
- ステートチャート（HarelのStatecharts）：階層化、並行（直交）領域、ガードやアクションを持ち、複雑なシステムを階層的・構造的に表現するための拡張。UMLのステートマシンはこれを基にしています。
構成要素の詳細：イベント、ガード、アクション、エントリ/エグジット
- イベント：外部入力や内部トリガのこと。遷移を駆動する。
- ガード（条件式）：遷移を発火させるためのブール条件。イベントだけでなく状態やデータの条件にも依存する。
- アクション：遷移時や状態エントリ/エグジット時に実行される処理。副作用や出力生成を担う。
- エントリアクション/エグジットアクション：状態に入るとき・出るときに必ず実行されるコード。状態局所の初期化やクリーンアップに便利。
実装パターンと手法
ステートマシンの実装には複数の一般的手法があります。用途や言語特性により使い分けます。
- switch/case（テーブルドリブン）：小規模でわかりやすいが状態数増大で可読性が低下。
- 遷移テーブル（配列／マップ）：状態×イベントのテーブルで管理。テストや自動生成に向く。
- ステートパターン（GoF）：各状態をクラスとして表現し、振る舞いをオブジェクトに委譲。拡張性が高い。
- 関数ポインタ／クロージャ：組み込み系や高性能要求の場面で高速に切替可能。
- DSL／ツール生成：Yakindu、SCADE、Stateflow、XStateなどのツールでモデルを定義してコード生成。
実際の応用例
- プロトコル実装（TCPの状態遷移図など）：相互作用のある分散プロトコルで特に有用。
- 組み込み制御（家電、自動車、ロボット）：堅牢で予測可能な挙動設計に適合。
- ユーザーインターフェース（UI状態管理）：複雑な画面遷移やモードの管理。
- 正規表現／字句解析器：NFA→DFA変換により高速な文字列マッチ。
- ワークフロー／BPM：業務プロセスの状態遷移を明確に表現。
設計上の注意点と落とし穴
- 状態の粒度設計：状態を「データのスナップショット」として扱うとよい。状態とデータ（変数）をどう切り分けるかで設計が変わる。
- 状態爆発：並列領域や多数の組合せで状態数が指数的に増える。階層化、抽象化、部分オートマトン分割で対処。
- 副作用の管理：アクションが多いとテスト困難になる。可能なら副作用は少なくし、純粋関数で振る舞いを決める設計を検討する。
- 同時性（Concurrency）：並列ステートやイベント競合の設計はデッドロックや競合を生むため、明確な優先順位や排他制御が必要。
検証と解析：安全性・停止性の保証
ステートマシンはモデル検査（model checking）やシミュレーションで検証できます。代表的ツールにはSPIN、NuSMV、UPPAAL（時間制約付き）などがあり、LTL/CTLなどの時相論理で安全性（bad state到達不可）やリバース性（イベントは必ず応答する）をチェックできます。状態爆発問題には抽象化、部分順序削減、BDDなどのシンボリック手法が用いられます。
最適化・簡約化技術
- 状態最小化：同値状態のマージ（DFA最小化アルゴリズム）で状態数を削減。
- モジュール化と並列合成：独立部分を別々に設計して合成（直交領域）することで複雑さを管理。
- シンボリック表現：BDDやSATベースの表現で大規模空間を扱う。
実用的なTips
- ドメイン固有の言語（DSL）や可視化ツールを使うと設計の共有とレビューが容易になる。
- テストは状態カバレッジを意識（各状態・遷移を網羅）する。遷移条件の境界値も重要。
- ログに状態遷移を出力することで問題発見が早くなる。タイムスタンプやイベントソースも記録。
- 大規模システムでは複合状態を避け、単純な単位に分割してインターフェースで連携する。
簡単な例：自販機（概念）
硬貨投入→金額が足りない状態→商品選択→商品排出→お釣り返却。ここで「金額」は状態ではなく状態に関連するデータと考えると設計が楽になります。状態は「待機」「選択中」「排出中」などに限定し、ガードで金額判定を行うのが一般的です。
ツールと実装例（代表的なもの）
- XState（JavaScript/TypeScriptのステートマシンライブラリ）
- Yakindu Statechart Tools（Eclipseベースのモデル駆動ツール）
- SPIN（Promela言語によるモデル検査ツール）
- NuSMV、UPPAAL（形式検証ツール）
- MATLAB/Simulink Stateflow、SCADE（産業用途のモデルベース開発）
まとめ：いつステートマシンを選ぶべきか
ステートマシンは「明確なモード切替がある」「イベント駆動で振る舞いが変わる」「検証や可視化が重要な」システムに有効です。一方で、数値計算や状態が連続的に変化するシステムには不向きな場合があるため、モデルを選ぶ際は要件とスコープを見極めてください。設計では状態とデータの分離、階層化、テスト容易性を重視すると良い結果になります。
参考文献
- 状態機械 - Wikipedia（日本語）
- Finite-state machine - Wikipedia
- Mealy machine - Wikipedia
- Moore machine - Wikipedia
- D. Harel, "Statecharts: A Visual Formalism for Complex Systems", Science, 1987
- UML Specification - Object Management Group (OMG)
- SPIN Model Checker（公式）
- NuSMV（公式）
- XState（公式）
- Yakindu Statechart Tools（公式）
- Model checking - Wikipedia
投稿者プロフィール
