ズンドコキヨシ with DFA(決定性有限オートマトン)

  • 18
    Like
  • 3
    Comment
More than 1 year has passed since last update.

流行のあれを以前会社の同僚と勉強会をしたアンダースタンディング・コンピューテーションで学んだDFA(決定性有限オートマトン)とRubyで実装してみる。ちなみに本の内容はほとんど理解出来てないので、詳しいツッコミには解答できない可能性が高いです!

状態遷移図

たぶんこんな感じ(訂正しました、@kroton さんありがとうございます)

訂正前

2016-03-15 00.54.08.jpg

コード

DFAの部分はアンダースタンディング・コンピューテーションのほぼ写経です

# 有限オートマトンの規則
class FARule < Struct.new(:state, :character, :next_state)
  def applies_to?(state, character)
    self.state == state && self.character == character
  end

  def follow
    next_state
  end
end

# 決定性有限オートマトンの規則集
class DFARulebook < Struct.new(:rules)
  def next_state(state, character)
    rule_for(state, character).follow
  end

  def rule_for(state, character)
    rules.detect { |rule| rule.applies_to?(state, character) }
  end
end

# 決定性有限オートマトン
class DFA < Struct.new(:current_state, :accept_states, :rulebook)
  def accepting?
    accept_states.include?(current_state)
  end

  def read_character(character)
    self.current_state = rulebook.next_state(current_state, character)
  end
end

# ズンドコ節生成器
class ZundokoMachine
  ZUNDOKO = %w(ズン ドコ)

  def initialize
    rulebook = DFARulebook.new([
      FARule.new(1, 'ズン', 2) , FARule.new(1, 'ドコ', 1),
      FARule.new(2, 'ズン', 3) , FARule.new(2, 'ドコ', 1),
      FARule.new(3, 'ズン', 4) , FARule.new(3, 'ドコ', 1),
      FARule.new(4, 'ズン', 5) , FARule.new(4, 'ドコ', 1),
      FARule.new(5, 'ズン', 5) , FARule.new(5, 'ドコ', 6),
      FARule.new(6, 'ズン', 6) , FARule.new(6, 'ドコ', 6),
    ])
    @dfa = DFA.new(1, [6], rulebook)
  end

  def run
    begin
      zundoko = ZUNDOKO.sample
      puts zundoko
    end until read(zundoko).accepting?
    puts '\キ・ヨ・シ!/'
  end

  private
  def read(zundoko)
    @dfa.tap{|dfa| dfa.read_character(zundoko)}
  end
end

# 実行
ZundokoMachine.new.run

実行結果の例

ドコ
ズン
ドコ
ドコ
ズン
ドコ
ズン
ズン
ズン
ズン
ズン
ズン
ズン
ズン
ドコ
\キ・ヨ・シ!/