有限状態機械(FSM)をPythonで実装する｜回路が"手順"を進めるしくみ

信号機の「青→黄→赤」、自動販売機の「投入→選択→排出」——こうした順序立った動作を表すのが 有限状態機械（FSM） です。フリップフロップで作る順序回路の設計図にあたります。Pythonで実装して考え方を掴みます。

FSMの3要素

FSMは「状態」「入力による遷移」「各状態での出力」で表せます。今どの状態かを覚え、入力に応じて次の状態へ移る——記憶を持つ回路そのものです。

準備

Python標準機能だけ。

① 信号機のFSM

状態と遷移を辞書で表します。

# 遷移表：現在の状態 → 次の状態
transitions = {"青": "黄", "黄": "赤", "赤": "青"}

state = "青"
for _ in range(6):
    print(state, end=" → ")
    state = transitions[state]
print(state)
# 青 → 黄 → 赤 → 青 → 黄 → 赤 → 青

状態を記憶し、遷移表に従って進むだけ。信号機の制御ロジックそのものです。

② 入力で分岐するFSM：パターン検出器

「1が2回連続したら検出」する回路をFSMで作ります。ビット列を1つずつ食べて状態を進めます。

def detect_11(bits):
    state = "S0"          # S0=まだ / S1=1が1回 / 検出でフラグ
    detected = []
    for b in bits:
        if state == "S0":
            state = "S1" if b == 1 else "S0"
        elif state == "S1":
            if b == 1:
                detected.append(True)      # 11 を検出！
                state = "S1"
            else:
                state = "S0"
    return detected

seq = [0, 1, 1, 0, 1, 1, 1]
print("11の検出回数:", len(detect_11(seq)))   # 3

0,1,1,0,1,1,1 の中に「1が2連続」は3回（位置1-2、4-5、5-6）。入力履歴を状態で覚えることで、単発の値だけでは無理な「連続」の検出ができました。通信のパターン検出やプロトコル解析の基礎です。

まとめ

• FSMは「状態・遷移・出力」で順序立った動作を表す
• 状態を記憶し、入力に応じて次状態へ遷移する
• 信号機やパターン検出など、履歴が必要な処理に使う
• 順序回路（フリップフロップ＋組合せ回路）の設計図

もう少し詳しく（背景と理論）

有限状態機械（FSM）は、有限個の状態と、入力に応じた状態遷移で振る舞いを記述する計算モデルで、オートマトン理論の基礎です¹。ハードウェア設計では2つの型が重要です——出力が現在の状態だけで決まる Moore 機械と、出力が状態と入力の両方で決まる Mealy 機械。Mealy はより少ない状態で書けることがある一方、入力変化が即出力に伝わる違いがあります²。実装では、状態をフリップフロップで保持し、次状態論理と出力論理を組合せ回路で作ります。信号処理・通信プロトコル・制御など「順序のある動作」の設計の中核で、状態数を減らす状態最小化が回路コストの削減につながります³。

次の一歩 🌸

記憶素子はフリップフロップ、選択回路はマルチプレクサとデコーダ、設計の流れはチップ設計の流れへどうぞ。

Footnotes

1. 有限オートマトンは計算理論の基本モデル。正規言語を認識し、字句解析やプロトコル記述に対応する。チューリング機械へ連なる階層の最下層。 ↩

2. Moore 機械は出力＝f(状態)、Mealy 機械は出力＝f(状態,入力)。Mealy は状態数を減らせるが、入力変化が出力に即伝わりグリッチに注意。 ↩

3. 等価な状態を統合する状態最小化で、必要なフリップフロップ数と論理を削減できる。面積・電力・検証コストの低減につながる。 ↩