Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Octocat-spinner-32-eaf2f5

Cannot retrieve contributors at this time

file 163 lines (130 sloc) 3.272 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162


class FSM
  attr_reader :transitions

  def initialize(transitions, beginning_state, accepting_states)
    @transitions = transitions
    @begin = beginning_state
    @accept = accepting_states
    start
  end

  def start
    @state = @begin
    self
  end

  def read(*chars)
    chars.each { |c|
      @state = @transitions[[@state, c]]
    }
    accepts?
  end

  def accepts?
    @accept.include?(@state)
  end

  def clone
    FSM.new(@transitions, @beginning_state, @accepting_states)
  end

  def inspect
    super
  end

end

# example state machine, format is [state, symbol] => new_state
machine = FSM.new({
    [0, 0] => 0,
    [0, 1] => 1,
    [1, 0] => 1,
    [1, 1] => 1,
  }, 0, [0])

# example usage
puts machine.start.read(0,0,0,1)
puts machine.start.read(0,0,0)




class Creator

  def initialize(alphabet)
    @knowledge = {}
    @tree = []
    @leaves = []
    @results = []
    @alphabet = alphabet
  end

  def knowledge(i)
    @knowledge[i] ||= (@knowledge_block.call(i).tap { |o|
     #p o
    })
  end

  def learn(max_states, &block)
    @knowledge_block = block
    (2..max_states).each { |i|
      states = (0..i)
      ((i**i)**@alphabet.length).times { |n|
        transitions = {}
        connections = n.to_s(i).rjust(i*2,"0").split("").map(&:to_i)
        #p connections
        (i).times { |from_state|
          @alphabet.length.times { |s|
            to_state = connections[from_state*@alphabet.length+s]
            transitions[[from_state, s]] = to_state
          }
        }
        #transitions.keys.sort.each { |k| puts " "+{k=>transitions[k]}.inspect }
        #puts ""
        i.times { |s|
          found = true
          machine = FSM.new(transitions, 0, [s])
          #if transitions == {[0,0] => 0, [0,1] => 1, [1,0] => 1, [1,1] => 1}
          # p machine
          #end
          30.times { |k|
            sequence, result = knowledge(k)
            if machine.start.read(*sequence) != result
              found = false
              break
            end
          }
          if found
            @results << machine
            return
          end
        }
      }
    }
  end

  def results
    @results
  end

  private

end

c = Creator.new([0,1])


# match sequences that have no "1"
specification = lambda { |i|
  sequence = []
  i.times { |step| sequence << (step % 2) }
  if i % 2
    r = [[1]+sequence, true]
  else
    r = [[0]+sequence, false]
  end
  r
}

# match sequences that have at least one "1" in them
specification = lambda { |i|
  if i % 2 == 0
    [(("0"*(rand(i)+2))+("1"*(rand(i)+1))+("0"*(rand(i)+2))).split("").map(&:to_i), true]
  else
    [("0"*(rand(i*2)+2)).split("").map(&:to_i), false]
  end
}

# match numbers that can be divided by three
specification = lambda { |i|
  [i.to_s(2).split("").map(&:to_i), (i % 4) == 0]
}

#learn a state machine that only accepts the sequence "1,0"
# arguments: max_states, specification block
c.learn(3, &specification)

c.results.each { |machine|
  p machine
  sequence, result = specification.call(rand(50))
  # print out the tesing sequence with the expected result
  puts "testing sequence:"
  p sequence
  puts "expected result: "
  p result
  puts ((machine.start.read(*sequence) == result) ? "works fine" : "doesn't work")
}




Something went wrong with that request. Please try again.