流行のあれを以前会社の同僚と勉強会をしたアンダースタンディング・コンピューテーションで学んだDFA(決定性有限オートマトン)とRubyで実装してみる。ちなみに本の内容はほとんど理解出来てないので、詳しいツッコミには解答できない可能性が高いです！
状態遷移図
たぶんこんな感じ(訂正しました、@kroton さんありがとうございます)
コード
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
実行結果の例
ドコ
ズン
ドコ
ドコ
ズン
ドコ
ズン
ズン
ズン
ズン
ズン
ズン
ズン
ズン
ドコ
＼キ・ヨ・シ！／