NFAを使って足し算の関数を作りました
『精霊の箱 上: チューリングマシンをめぐる冒険』の足し算する関数を書きました。requireで呼び出しているファイルはここに置いてます。本に登場する塔文字のようなものをコンパイルして使います。「文字列比較」と「富者の像と貧者の像」も同様にして、作成できることを確認しています。
#!/usr/bin/env ruby require './parser.rb' require './reg2post.rb' require './nfa.rb' require 'minitest/autorun' class MainTest < MiniTest::Test def test_1 p = Parser.new src = <<-SRC 1,00->,1 1,11->,1 1,++->,1 1, <-,2 2,II<-,2 2,OO<-,2 2,0O<-,3 2,1I<-,4 2,++<-,14 3,00<-,3 3,11<-,3 3,++<-,5 4,00<-,4 4,11<-,4 4,++<-,6 5,OO<-,5 5,II<-,5 5,0O->,7 5,1I->,7 6,II<-,6 6,OO<-,6 6,0I->,7 6,1O->,13 7,00->,7 7,11->,7 7,OO->,7 7,II->,7 7,++->,7 7, <-,2 8,OO<-,8 8,II<-,8 8,0O<-,9 8,1I<-,10 8,++<-,15 9,00<-,9 9,11<-,9 9,++<-,11 10,00<-,10 10,11<-,10 10,++<-,12 11,II<-,11 11,OO<-,11 11,1O->,13 11,0I->,7 12,OO<-,12 12,II<-,12 12,0O->,13 12,1I->,13 13,00->,13 13,11->,13 13,OO->,13 13,II->,13 13,++->,13 13, <-,8 14,O0<-,14 14,I1<-,14 14, <-,16 15,O0<-,15 15,I1<-,15 15, 1<-,16 SRC s = compile(reg2post(p.parse(src))) m = Machine.new(s) (0..10).each do|a| (0..10).each do|b| n = [a.to_s(2).length, b.to_s(2).length].max src = " #{("0" * n + a.to_s(2))[-n..-1]}+#{("0" * n + b.to_s(2))[-n..-1]} " assert_equal "#{(a+b).to_s(2)}", m.exec(src, 1).scan(/\w+/)[0] end end end end