有限状態機械(FSM)

有限状態機械とは何か?

有限状態機械(FSM)は、有限個の状態、それらの状態間の遷移、および入力に基づいて状態変化を決定する規則から構成される計算モデルです。FSMは、イベントシーケンスや特定の条件に依存する動作を持つシステムにおいて、順序論理をモデル化するための数学的フレームワークを提供します。

基本原則:

• システムは任意の時点で正確に1つの状態に存在する
• 入力が状態間の遷移をトリガーする
• 規則が有効な状態変化を定義する
• 出力は状態および/または入力に依存する場合がある

類推:
ドアの錠は、施錠と解錠の2つの状態を持つシンプルなFSMとして動作します。正しい鍵は錠を施錠から解錠へ遷移させ、間違った鍵は現在の状態を維持します。錠の動作は、現在の状態と受け取った入力に基づいて完全に予測可能です。

主要コンポーネント

状態

定義: システムが存在できる明確な構成またはモード。

特性:

• システムは任意の瞬間に正確に1つの状態を占める
• 状態は意味のある動作モードを表す
• 各状態には関連する出力または動作がある場合がある
• 状態の数は有限で事前に決定されている

例:

• 自動販売機の状態: アイドル、選択待ち、商品払い出し中、サービス停止中
• ネットワーク接続の状態: 切断、接続中、接続済み、エラー
• ゲームキャラクターの状態: アイドル、歩行、走行、ジャンプ、攻撃

遷移

定義: 入力条件に基づいて、ある状態から別の状態への移動を管理する規則。

主要特性:

• 特定の入力またはイベントによってトリガーされる
• 瞬時(中間状態なし)
• ガード条件を含む場合がある
• 実行中にアクションをトリガーできる

遷移表記:

現在の状態 + 入力 → 次の状態 [/ アクション]

例:

アイドル + "コイン投入" → 選択待ち / "メニュー表示"

入力と出力

出力タイプ:

• ミーリーマシン: 出力は現在の状態AND入力に依存
• ムーアマシン: 出力は現在の状態のみに依存

状態図

状態図は、FSMの構造と動作を視覚的に表現します。

視覚要素:

• 円/ノード: 状態を表す
• 矢印/エッジ: 遷移を表す
• ラベル: トリガーとなる入力と出力を示す
• 初期状態: どこからも来ない矢印が開始状態を指す
• 最終状態: 二重円(受理オートマトンの場合)

状態図要素の例:

[状態A] --入力/出力--> [状態B]
    |                           |
    +--入力/出力-------------+

有限状態機械の種類

1. 決定性有限状態機械(DFSM/DFA)

定義: 各状態/入力の組み合わせが正確に1つの次の状態につながるFSM—曖昧さが存在しない。

特性:

• 予測可能な動作が保証される
• 状態/入力ペアごとに単一の遷移
• 実装とデバッグが容易
• 計算複雑度が低い

応用:

• デジタル回路設計
• コンパイラの字句解析器
• プロトコル実装
• パスワード検証システム

例 - 2進数文字列検証器:

状態: {q0, q1}
入力アルファベット: {0, 1}
遷移:
  q0 + 0 → q0
  q0 + 1 → q1
  q1 + 0 → q0
  q1 + 1 → q1
受理: q0 (1の数が偶数の文字列)

2. 非決定性有限状態機械(NDFSM/NFA)

定義: 同じ状態/入力の組み合わせに対して複数の可能な次の状態を許容するFSM。

主要機能:

• 状態/入力ごとに複数の遷移オプション
• イプシロン(ε)遷移が可能(入力なしの状態変化)
• パターンマッチングに有用
• 等価なDFAに変換可能

利点:

• よりコンパクトな表現
• 複雑なパターンの初期設計が容易
• 特定の問題タイプに自然

応用:

• 正規表現エンジン
• パターンマッチングアルゴリズム
• 並列状態探索
• 曖昧な言語認識

3. ミーリーマシン

出力生成: 現在の状態AND入力に基づく。

特性:

例 - 改札機コントローラー:

状態: 施錠
入力: コイン → 出力: 解錠 → 次の状態: 解錠済み

状態: 解錠済み  
入力: 押す → 出力: 施錠 → 次の状態: 施錠

使用例:

• 即座の応答が必要なシステム
• 通信プロトコル
• フィードバック付き制御システム
• イベント駆動アプリケーション

4. ムーアマシン

出力生成: 現在の状態のみに基づく。

特性:

例 - 信号機コントローラー:

状態: 赤 → 出力: 停止(一定)
状態: 黄 → 出力: 注意(一定)
状態: 緑 → 出力: 進行(一定)

使用例:

• 順序システム
• 安全性が重要なアプリケーション
• タイミングに敏感な回路
• 出力安定性を優先するシステム

ミーリー対ムーアの比較

FSMの動作:ステップバイステッププロセス

FSM構築ワークフロー

1. 状態の識別

• すべての明確な動作モードをリストアップ
• 意味のある状態名を定義
• 初期状態と最終状態を識別(該当する場合)
• 状態が相互排他的であることを確認

2. 入力の定義

• すべての可能な入力/イベントを列挙
• 入力アルファベットまたはイベントタイプを定義
• エッジケースと無効な入力を考慮
• 入力形式と範囲を文書化

3. 遷移マッピング

各状態について:
  各可能な入力について:
    次の状態を定義
    アクションを定義(ある場合)
    ガード条件を追加(必要な場合)

4. 状態テーブルの作成

5. 実装

• 表現を選択(テーブル、switch-case、状態パターン)
• 開始状態に初期化
• 遷移ロジックを実装
• 出力生成を追加
• エッジケースとエラーを処理

6. 実行サイクル

ループ:
  1. 入力を待つ
  2. 遷移を検索: 現在の状態 + 入力
  3. 遷移アクションを実行(ある場合)
  4. 現在の状態を次の状態に更新
  5. 出力を生成(ムーア:状態ベース、ミーリー:状態+入力)
  6. 繰り返し

実装例

例1: 信号機コントローラー(Python)

状態: 緑、黄、赤
トリガー: タイマー満了

class TrafficLight:
    def __init__(self):
        self.state = 'Green'
        self.state_durations = {
            'Green': 30,
            'Yellow': 5,
            'Red': 25
        }
    
    def transition_table(self):
        return {
            'Green': 'Yellow',
            'Yellow': 'Red',
            'Red': 'Green'
        }
    
    def on_timer(self):
        transitions = self.transition_table()
        self.state = transitions[self.state]
        print(f'Light: {self.state}')
        return self.state_durations[self.state]

# 使用法
light = TrafficLight()
for _ in range(6):
    duration = light.on_timer()
    print(f'Duration: {duration} seconds\n')

例2: 文字列パーサー(JavaScript)

タスク: “01"で終わる文字列を検証

class StringParser {
  constructor() {
    this.state = 'start';
  }
  
  transition(input) {
    const table = {
      'start': {'0': 'got_0', '1': 'start'},
      'got_0': {'0': 'got_0', '1': 'got_01'},
      'got_01': {'0': 'got_0', '1': 'start'}
    };
    
    if (table[this.state] && table[this.state][input]) {
      this.state = table[this.state][input];
      return true;
    }
    return false;
  }
  
  isValid() {
    return this.state === 'got_01';
  }
  
  reset() {
    this.state = 'start';
  }
}

// テスト
const parser = new StringParser();
'10101'.split('').forEach(bit => parser.transition(bit));
console.log(parser.isValid()); // true

例3: ゲームキャラクターFSM(C++)

enum State {
    STATE_STANDING,
    STATE_JUMPING,
    STATE_DUCKING,
    STATE_DIVING
};

enum Input {
    PRESS_B,
    PRESS_DOWN,
    RELEASE_DOWN
};

class Character {
private:
    State state_;
    
public:
    Character() : state_(STATE_STANDING) {}
    
    void handleInput(Input input) {
        switch (state_) {
            case STATE_STANDING:
                if (input == PRESS_B) {
                    state_ = STATE_JUMPING;
                    yVelocity_ = JUMP_VELOCITY;
                } else if (input == PRESS_DOWN) {
                    state_ = STATE_DUCKING;
                }
                break;
                
            case STATE_JUMPING:
                if (input == PRESS_DOWN) {
                    state_ = STATE_DIVING;
                    yVelocity_ *= 2;
                }
                break;
                
            case STATE_DUCKING:
                if (input == RELEASE_DOWN) {
                    state_ = STATE_STANDING;
                }
                break;
                
            case STATE_DIVING:
                // 着地時のみ遷移可能
                break;
        }
    }
    
    void update() {
        switch (state_) {
            case STATE_JUMPING:
            case STATE_DIVING:
                yVelocity_ += GRAVITY;
                yPosition_ += yVelocity_;
                if (yPosition_ <= 0) {
                    state_ = STATE_STANDING;
                    yPosition_ = 0;
                }
                break;
        }
    }
};

実世界での応用

ソフトウェアエンジニアリング

UIイベント処理

• ウィジェット状態: アイドル、ホバー、フォーカス、押下、ドラッグ
• マウス/タッチイベントに基づく遷移
• 出力: 視覚的フィードバック、コールバック

ネットワークプロトコル

• TCP接続状態: CLOSED、LISTEN、SYN_SENT、ESTABLISHED、FIN_WAIT
• パケット受信時の遷移
• 信頼性の高い通信を保証

コンパイラ字句解析

• 状態遷移によるトークン認識
• 各文字入力が遷移をトリガー
• 受理状態が有効なトークンを示す

ハードウェアとデジタルシステム

応用分野:

例 - エレベーターコントローラー:

状態: アイドル、上昇中、下降中、ドア開放
入力: 呼び出しボタン、フロアセンサー、ドアセンサー、タイマー
出力: モーター制御、ドア制御、ディスプレイ

AI、チャットボット、自動化

会話型AIの状態:

• 挨拶 → 情報収集 → 処理 → 応答 → フォローアップ → 終了
• ユーザー入力と意図認識に基づく遷移
• 状態間でのコンテキスト保持

スマートホーム自動化:

セキュリティシステムFSM:
状態: 解除、在宅警戒、外出警戒、警報作動
入力: ユーザーコマンド、センサーイベント、タイマー
出力: ステータス表示、警報音、通知

プロセス自動化:

• プロセス段階を表すワークフロー状態
• タスク完了または承認時の遷移
• ビジネスシステムとの統合

ゲーム開発

キャラクターAIの動作:

ゲームフロー管理:

メニュー → ロード中 → プレイ中 ⇄ 一時停止 → ゲームオーバー → メニュー

高度なFSMの概念

階層状態機械(HSM)

概念: 状態がネストされたサブFSMを含み、複雑な動作の構成を可能にする。

利点:

• 状態爆発の削減
• 複雑なシステムのより良い組織化
• 再利用可能なサブ動作
• より明確な論理構造

構造例:

[戦闘モード]
  ├─ [攻撃中]
  │    ├─ 近接攻撃
  │    └─ 遠距離攻撃
  └─ [防御中]
       ├─ ブロック
       └─ 回避

並列状態機械

概念: 複数の独立したFSMが同時に実行される。

使用例:

• 関心事の分離(例:移動FSM + アニメーションFSM)
• 独立したサブシステム制御
• 並行動作のモデリング

例 - ゲームキャラクター:

移動_FSM: 立ち、歩行、走行、ジャンプ
アニメーション_FSM: アイドルアニメ、歩行アニメ、走行アニメ、ジャンプアニメ
戦闘_FSM: 非武装、武装、攻撃中、リロード中

状態爆発問題

課題: システムの複雑さに伴い状態数が指数関数的に増加する。

緩和戦略:

状態パターン(OOP)

概念: 状態固有の動作を別々のクラスにカプセル化する。

構造:

class State:
    def handle(self, context): pass

class ConcreteStateA(State):
    def handle(self, context):
        # 状態Aの動作
        context.state = ConcreteStateB()

class Context:
    def __init__(self):
        self.state = ConcreteStateA()
    
    def request(self):
        self.state.handle(self)

利点:

• オープン/クローズド原則への準拠
• 新しい状態の追加が容易
• 関心事の明確な分離
• 複雑な条件文を排除

利点と制限

利点

制限

不適切な用途:

• 無制限のメモリを必要とする問題(例:ネストされた括弧のマッチング)
• 連続状態空間を持つシステム
• 高度に適応的または学習するシステム
• 正規言語クラス外の問題

ベストプラクティス

設計ガイドライン

状態設計:

• 状態を意味があり明確に保つ
• 明確性を維持しながら状態数を最小化
• 状態を説明的に命名(動詞-名詞または形容詞-名詞)
• 相互排他性を確保

遷移設計:

• 遷移を明示的かつ明確に定義
• すべての状態のすべての入力を処理(またはエラー状態を定義)
• 進行のない循環依存を避ける
• ガード条件を明確に文書化

実装:

• 適切な表現を選択(テーブル、switch、パターン)
• 処理前に入力を検証
• デバッグのために状態遷移をログ記録
• 必要に応じてタイムアウトメカニズムを実装

テスト戦略

カバレッジタイプ:

主要用語

• 有限状態機械(FSM): 有限の状態と定義された遷移を持つ計算モデル
• 状態: 明確な構成または動作モード
• 遷移: 入力に基づくある状態から別の状態への移動
• 入力アルファベット: すべての可能な入力の集合
• 出力: FSMによって生成されるアクションまたは信号
• 決定性FSM: 各状態/入力ペアが正確に1つの次の状態を持つ
• 非決定性FSM: 状態/入力ペアが複数の次の状態を持つ可能性がある
• ミーリーマシン: 出力が状態と入力に依存
• ムーアマシン: 出力が状態のみに依存
• 状態図: FSMのグラフィカル表現
• 遷移テーブル: すべての遷移の表形式表現
• 受理状態: 有効な入力シーケンスを示す状態(オートマトンの場合)

参考文献

• BLT Inc: A Guide to Finite State Machines
• SiliconVeda: FSM Comprehensive Guide
• Game Programming Patterns: State
• Software Engineering Stack Exchange: FSM Examples
• Quora: Real-world FSM Examples and Code