有限状態機械（FSM）

有限状態機械とは？

有限状態機械（FSM：Finite State Machine）は、限定された数の状態、それらの間の遷移規則、入力に基づいて状態を変化させるロジックで構成される計算モデルです。 システムがいかなるタイミングでも正確に一つの状態に存在し、入力イベントに応じて別の状態に遷移します。その後の動作は新しい状態によって完全に決定されます。

ひとことで言うと： 「信号機のロジック」です。赤の状態では『待て』、青では『進め』と、状態が動作を規定します。入力（時間経過）により状態が遷移します。

ポイントまとめ：

• 何をするものか： 複雑なシステムの動作を、限定された状態と遷移ルールで明確に記述します
• なぜ必要か： 予測可能で確実な動作を保証し、バグやエッジケースを事前に検出できます
• 誰が使うか： ゲーム開発（キャラクターAI）、コンパイラ設計、プロトコル実装、チャットボット、自動化システムなど広範に応用されています

なぜ重要か

FSMは、複雑なシステムの動作を簡潔かつ確実に記述できる強力なツールです。特にシステムが「複数の異なる状態を持つ」場合に威力を発揮します。例えば、チャットボットが「ユーザー入力待機」「処理実行」「応答生成」「終了」といった異なる状態を遷移するなら、FSMで正確に記述できます。

セキュリティ、安定性、デバッグ効率の観点から、FSMの設計は不可欠です。状態とその遷移ルールを明確に定義することで、「想定外の状態に陥った」というバグを事前に防げます。自動運転車が「検知」「判断」「加速」「制動」といった状態を正確に遷移させる、医療機器が「待機」「測定」「分析」「警告」という状態を順序正しく進める、こうした堅牢性が生死に関わるシステムではFSMが不可欠です。

仕組みをわかりやすく解説

FSMは四つの要素で構成されます。

状態集合は、システムがあり得るすべての状態を定義します。信号機なら「赤」「黄」「青」、ドアなら「施錠」「解錠」です。

入力アルファベットは、システムが受け取る可能性のあるすべての入力イベントを定義します。信号機なら「時間経過」、ドアなら「正しい鍵」「間違った鍵」です。

遷移関数は、現在の状態と入力が与えられた時、次にどの状態に遷移するかを定義するルールです。遷移関数が「完全に定義されている」（すべての状態と入力の組み合わせに対して遷移が定義されている）場合を決定性FSMと呼び、「複数の遷移の可能性がある」場合を非決定性FSMと呼びます。

開始状態と受理状態は、FSMが開始される状態と、「成功」を示す終了状態を定義します。FSMは状態遷移図で視覚化されます。円が状態を、矢印がイベントに基づいた遷移を示すことで、複雑なロジックが一目で理解できます。

実際の活用シーン

ゲーム開発でのキャラクターAI

敵キャラクターが「待機」「巡回」「警戒」「攻撃」「撤退」といった状態を持ちます。プレイヤーを検知すると「警戒」状態に遷移し、距離が近いと「攻撃」状態に遷移します。各状態で異なる行動ロジックが実行されます。FSMを使うことで、複雑なキャラクター行動を管理可能にしています。

オンライン決済プロセス

決済が「商品選択」「支払情報入力」「認証」「決済処理」「確認」「完了」といった状態を遷移します。各段階で正確な入力検証を行い、不正な状態遷移を防ぎます。FSMを使わずにこの複雑性を管理しようとすると、多くのバグが生じます。

信号機の制御システム

信号機が「赤（車両停止、歩行者通行）」「黄（注意）」「青（車両通行、歩行者停止）」という状態を遷移します。時間計時、ボタン入力、センサー信号に基づいて状態遷移が決定されます。FSMの厳密さがあるからこそ、複数交差点の調整が可能になります。

メリットと注意点

FSMのメリットは、複雑な動作を明確かつ管理可能な形で記述できることです。すべての状態と遷移が明示的に定義されるため、バグやエッジケースの事前検出が容易です。さらに、形式検証手法により、理論的な正確性を証明することも可能です。これは医療機器や航空機制御など、安全性が最重要なシステムで価値があります。

一方、注意点もあります。状態の数が多いと、状態遷移図が複雑になり、管理困難になります。「組み合わせ爆発」と呼ばれる現象で、状態数がNなら遷移数はN²に近づきます。また、FSMは「予め定義された状態」のみを扱うため、予測不可能な入力や学習が必要なシステムには向きません。そこで、より高度な「階層型FSM」や「ファジィFSM」といった拡張モデルが考案されています。

関連用語

• フローチャート — FSMの視覚化方法です
• コンパイラ — プログラミング言語解析にFSMが多用されます
• ゲーム開発 — キャラクターAI制御でFSMが活用されます
• 自動化 — ワークフローステップをFSMで管理します
• 検証 — FSMは形式検証を通じて理論的正確性を証明できます

よくある質問

Q: FSMと従来の制御フローの違いは何ですか？

A: 従来の制御フローはプログラムの線形実行に焦点を当てます。一方、FSMはシステムの「状態」に焦点を当て、各状態でどの動作をするかを定義します。FSMは特に「複数の異なる動作モード」を持つシステムに適しています。

Q: 状態の数が膨大な場合、FSMは使用できますか？

A: はい、使用できますが、複雑さが管理困難になります。その場合、「階層型FSM」（ステートマシンの中にステートマシンをネストさせる）を使用したり、状態を論理的にグループ化することが有効です。

Q: すべてのソフトウェアシステムがFSMで記述できますか？

A: いいえ。FSMは「状態空間が限定的」で「予測可能な動作」に向いています。複雑な意思決定、学習、非決定的動作が必要なシステムには、より高度なモデルが必要です。ただし、システムの重要な部分をFSMで形式化することはしばしば有益です。