読者です 読者をやめる 読者になる 読者になる

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