小さな機械、決定性有限オートマトン。そして移りゆく状態

この記事は？

決定性有限オートマトンに関する走り書きです。

• 有限オートマトン (finite automaton) を使用した状態遷移の管理方法について説明する
  • 有限オートマトンは有限状態機械 (FSM: finite state machine) とも呼ぶ
• 有限オートマトンには以下の 2 つがあるが、この記事では DFA について説明する
  • 決定性有限オートマトン (DFA: Deterministic Finite Automaton) 👈 🈁
  • 非決定性有限オートマトン (NFA: Nondeterministic Finite Automaton)

きっかけ

『達人プログラマー ―熟達に向けたあなたの旅― (第 2 版)』の「29 実世界を扱う」で以下の記述を見つけた。

FSM の適用はとても簡単であるものの、多くの開発者らは背を向けています。どうやらこれは難しいものである、あるいはハードウェアを扱っている場合にのみ登場する考え方である、はたまた理解しづらいライブラリーを使用しなければならないものだと考えられているようです。しかし、その考えは間違っています。

残念なことに、有限状態機械はあまり開発では活用されていません。しかし、我々は積極的に活用する場を探してほしいと考えています。

なるほど、これだけイチオシなら使ってみたい。やがて達人へと至るために 💪

オートマトンのもともとの意味は？

オートマタ (英: Automata [ɔːˈtɑmətə] 複数形)、オートマトン (Automaton [ɔːˈtɑməˌtɑn] 単数形) は、主に 12 世紀から 19 世紀にかけてヨーロッパ等で作られた機械人形ないしは自動人形のこと。

日本の伝統的な機械仕掛けの人形をからくりと呼ぶのに倣うと、いわゆる「西洋からくり人形」に該当する。

🔼 オートマタ - Wikipedia より

有限オートマトンとは

🔼 有限オートマトン - Wikipedia より

• コンピュータからさまざまな機能を取り除いて大幅に単純化したモデル。
  • 永続的なストレージも RAM (Random Access Memory) もない。
• いくつかの取り得る状態 (state) と、現在どの状態にいるかを記録する能力を持った小さな機械 🤖
  • 現在の状態という 1 つの値のみ保持する RAM を備えたコンピュータとみなせる。
• 入力に応じてある状態から別の状態への移動方法を決めるルールがあり、その集合がハードコードディングされている。

重要な概念と特徴

概念

• 開始状態 (start state)
  • 左端の矢印
  • オートマトンは開始状態から開始する
• 受理状態 (accept state)
  • 2 重のサークル
  • 手続きが成功裏に完了した状態 🙆✨

決定性有限オートマトンと非決定性有限オートマトン

決定性有限オートマトン (DFA: Deterministic Finite Automaton)

🔼 『アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで』「3.2.1 非決定性」より

• 決定的である (deterministic)
  • 矛盾がない
    • 競合する規則があることによって、次の移動があいまいになるような状態がないこと
      • 同じ入力文字に対して、取り得る状態が複数存在しないこと
  • 省略がない
    • 規則が欠けていることによって次の移動がわからなくなるような状態がないこと
    • 状態はすべて、可能な入力文字に対して少なくとも 1 つの規則を持たなくてはならないこと

非決定性有限オートマトン (NFA: Nondeterministic Finite Automaton)

🔼 『アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで』「3.2.1 非決定性」より

• NFA は確実性ではなく可能性を扱う
  • 何が起こるかではなく、何が起こる可能性があるか

決定性有限オートマトン (DFA) の実装例

実装例

DFA を使用して正規表現などのパーサーを作る例が一般的のようだが、今回は DFA で状態遷移の管理を行いたい。

fa_rule.rb

# 有限オートマトン (FA) のルール
class FARule
  def initialize(state:, event:, next_state:)
    @state = state
    @event = event
    @next_state = next_state
  end

  # 特定の状態で特定のイベントが発生した際にこのルールを適用できるかどうか。
  def apply_to?(state:, event:)
    @state == state && @event == event
  end

  # このルールを適用した後の状態。
  def follow
    @next_state
  end
end

dfa_rules.rb

require 'delegate'

# 決定性有限オートマトン (DFA) のルール集
class DFARules < DelegateClass(Array)
  def initialize(rules)
    super(rules)
  end

  # 特定の状態で特定のイベントが発生した後の状態を取得する。
  def get_next_state(state:, event:)
    rule = find { it.apply_to?(state: state, event: event) }
    rule&.follow
  end
end

dfa.rb

# 決定性有限オートマトン (DFA)
class DFA
  class InvalidEvent < StandardError; end

  attr_reader :current_state

  def initialize(current_state:, accept_states:, rules:)
    @current_state = current_state
    @accept_states = accept_states
    @rules = rules
  end

  # 受理状態かどうか。
  def accepting?
    @accept_states.include?(@current_state)
  end

  # イベントを発生させる。
  def fire(event)
    next_state = @rules.get_next_state(state: @current_state, event: event)
    raise(InvalidEvent) unless next_state

    @current_state = next_state
  end
end

job_state.rb

require_relative './fa_rule'
require_relative './dfa_rules'
require_relative './dfa'

class JobState
  INITIAL_STATE = :working
  EVENTS = %i(succeed fail retry cancel).freeze
  STATES = %i(working succeeded failed canceled).freeze
  RULES = [
    FARule.new(state: :working, event: :succeed, next_state: :succeeded),
    FARule.new(state: :working, event: :fail, next_state: :failed),
    FARule.new(state: :failed, event: :retry, next_state: :working),
    FARule.new(state: :failed, event: :cancel, next_state: :canceled)
  ].freeze

  def initialize(current_state: INITIAL_STATE)
    @dfa = DFA.new(
      current_state: current_state,
      accept_states: %i(succeeded canceled),
      rules: DFARules.new(RULES)
    )
  end

  # ジョブの現在の状態。
  def current_state
    @dfa.current_state
  end

  EVENTS.each do |event|
    define_method(event) { @dfa.fire(event) }
  end

  STATES.each do |state|
    define_method(:"#{state}?") { @dfa.current_state == state }
  end

  # ジョブが完了したかどうか (= DFA が受理状態か) 。
  def finished?
    @dfa.accepting?
  end
end

if __FILE__ == $PROGRAM_NAME
  require 'minitest'
  require 'minitest/autorun'

  class JobStateTest < Minitest::Test
    def test_dfa
      job_state = JobState.new

      assert_equal(true, job_state.working?)
      assert_equal(false, job_state.finished?)
      job_state.fail
      assert_equal(false, job_state.working?)
      assert_equal(true, job_state.failed?)
      job_state.retry
      assert_equal(true, job_state.working?)
      job_state.succeed
      assert_equal(true, job_state.succeeded?)
      assert_equal(true, job_state.finished?)
    end
  end
end

Gem を使った例

• aasm/aasm: AASM - State machines for Ruby classes (plain Ruby, ActiveRecord, Mongoid, NoBrainer, Dynamoid)
• state-machines/state_machines: Adds support for creating state machines for attributes on any Ruby class

job_state_with_aasm.rb

require 'aasm'
require_relative './fa_rule'
require_relative './dfa_rules'
require_relative './dfa'

class JobStateWithAasm
  include AASM

  aasm do
    state :working, initial: true
    state :succeeded, :failed, :canceled

    event :succeed do
      transitions from: :working, to: :succeeded
    end

    event :fail do
      transitions from: :working, to: :failed
    end

    event :retry do
      transitions from: :failed, to: :working
    end

    event :cancel do
      transitions from: :failed, to: :canceled
    end
  end

  def finished?
    succeeded?
  end
end

if __FILE__ == $PROGRAM_NAME
  require 'minitest'
  require 'minitest/autorun'

  class JobStateWithAasmTest < Minitest::Test
    def test_dfa
      job_state = JobStateWithAasm.new

      assert_equal(true, job_state.working?)
      assert_equal(false, job_state.finished?)
      job_state.fail
      assert_equal(false, job_state.working?)
      assert_equal(true, job_state.failed?)
      job_state.retry
      assert_equal(true, job_state.working?)
      job_state.succeed
      assert_equal(true, job_state.succeeded?)
      assert_equal(true, job_state.finished?)
    end
  end
end

補足

AASM のパフォーマンスが悪いという話を聞いた。実際に比較してみよう。

benchmarks.rb

require 'benchmark/ips'
require_relative './job_state'
require_relative './job_state_with_aasm'

Benchmark.ips do |x|
  x.config(time: 5, warmup: 2)

  x.report('JobState') do
    job_state = JobState.new
    job_state.working?
    job_state.fail
    job_state.failed?
    job_state.retry
    job_state.working?
    job_state.succeed
    job_state.succeeded?
  end
  x.report('JobStateWithAasm') do
    job_state = JobStateWithAasm.new
    job_state.working?
    job_state.fail
    job_state.failed?
    job_state.retry
    job_state.working?
    job_state.succeed
    job_state.succeeded?
  end

  x.compare!
end

ruby 3.4.6 (2025-09-16 revision dbd83256b1) +PRISM [arm64-darwin24]
Warming up --------------------------------------
            JobState    30.071k i/100ms
    JobStateWithAasm   538.000 i/100ms
Calculating -------------------------------------
            JobState    300.024k (± 1.5%) i/s    (3.33 μs/i) -      1.504M in   5.012500s
    JobStateWithAasm      5.840k (± 5.5%) i/s  (171.22 μs/i) -     29.590k in   5.082342s

Comparison:
            JobState:   300024.1 i/s
    JobStateWithAasm:     5840.4 i/s - 51.37x  slower

51.37x slower

確かに遅かった 🐢🐢🐢

まとめ

• 有限オートマトン (FA) はいくつかの取り得る状態と、現在どの状態にいるかを記録する能力を持った小さな機械
• 決定性有限オートマトン (DFA) を使用すると状態遷移を安全に管理できる 🥰
  • なぜならば DFA は決定的であいまいさがないため
  • DFA はシンプルに実装できる 💪

バージョンを情報

$ ruby -v
ruby 3.4.6 (2025-09-16 revision dbd83256b1) +PRISM [arm64-darwin24]

$ gem list | grep -e aasm -e benchmark-ips
aasm (5.5.1)
benchmark-ips (2.14.0)

参考

書籍

• 達人プログラマー ―熟達に向けたあなたの旅― 第2版 | David Thomas, Andrew Hunt, 村上雅章 | 工学 | Kindleストア | Amazon
• アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで | Tom Stuart, 笹田 耕一, 笹井 崇司 |本 | 通販 | Amazon

記事

• 有限オートマトン - Wikipedia
• State Machines in Ruby: An Introduction | AppSignal Blog

Gem

• minitest/minitest: minitest provides a complete suite of testing facilities supporting TDD, BDD, mocking, and benchmarking.
• evanphx/benchmark-ips: Provides iteration per second benchmarking for Ruby