Rubyで有限オートマトン

「Rubyによる情報科学入門」（久野靖）に、与えられた文字列がある規則に当てはまるかどうかを判定するという課題を例にした有限オートマトンの使い方というのがある。正規表現ぽい。

演習をやってみた。ちょっと元のコードが好みと違ったので、クラスを使って書き直してみた。

class Automata

  def initialize(atm)
    @atm = atm
  end

  def accept?(str)
    cur = 0
    str.length.times do |i|
      n = @atm[cur][str[i]]
      if n
        cur = n
      else
        return false
      end
    end
    return @atm[cur][:final] == true
  end

end

if __FILE__ == $0
  a = Automata.new([{'a' => 1}, {'b' => 0, :final => true}])
  
  test_case = ["ab", "aba", "abab", "ababa", "ababab", "abababa",
               "b", "ba", "bab", 
               "abaab", "abaaba"]
  
  test_case.each do |pat|
    print pat, "\t: "
    print a.accept?(pat)
    print "\n"
  end
end

「aとbがさまざまに混ざって現れるが、aの連続は最大2個まで」とか「aとbがさまざまに混ざって現れるが、aの個数は偶数個」という文字列を受理するオートマトンを紙に書けと演習にあって、「えっ、そんなことが可能なの？」と一瞬、驚いた。そんなことが可能と思ってなかったけど、なるほど、オートマトンってそういうことかと思って紙に書き出して、実際にハッシュに入れてみたら、確かにちゃんと動いた。面白い。

「aとbがさまざまに混ざって現れるが、aの連続は最大2個まで」「aとbがさまざまに混ざって現れるが、aの個数は偶数個」というのは、次のような状態遷移図で書ける。

で、これらをコードにすると、

a = Automata.new([{'a' => 1, 'b' => 0, :final => true}, 
                  {'a' => 2, 'b' => 0, :final => true},
                  {'b' => 0, :final => true}])

a = Automata.new([{'a' => 1, 'b' => 0, :final => true}, 
                  {'a' => 0, 'b' => 1}])

出力はこんな感じ。

% ruby 6c.rb
ab      : false
aba     : true
abab    : true
ababa   : false
ababab  : false
abababa : true
b       : true
ba      : false
bab     : false
abaab   : false
abaaba  : true
aaaaab  : false
aab     : true
abababbababbabba        : false
abbbbbbabbbbaabbb       : true
abaabbaaabb     : true
%

Wikipediaを見ると、どうもDFAというやつか。NFAという状態遷移が非決定的なモデルもあるけど、NFAはDFAに変換可能で、実装ではそうするもんなんだとか。NFAがDFAに変換可能というのは、直感に反する気がする。