Class: Stamina::Automaton::Determinize

Inherits:
Object
  • Object
show all
Defined in:
lib/stamina-core/stamina/automaton/determinize.rb

Defined Under Namespace

Classes: CompoundState

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(fa, options) ⇒ Determinize

Returns a new instance of Determinize.



51
52
53
54
 
# File 'lib/stamina-core/stamina/automaton/determinize.rb', line 51

def initialize(fa, options)
  @fa = fa
  @options = options
end

Instance Attribute Details

#fa ⇒ Object (readonly)

class CompoundState



48
49
50
 
# File 'lib/stamina-core/stamina/automaton/determinize.rb', line 48

def fa
  @fa
end

#options ⇒ Object (readonly)

Returns the value of attribute options.



49
50
51
 
# File 'lib/stamina-core/stamina/automaton/determinize.rb', line 49

def options
  @options
end

Class Method Details

.execute(fa, options = {}) ⇒ Object 



89
90
91
 
# File 'lib/stamina-core/stamina/automaton/determinize.rb', line 89

def self.execute(fa, options = {})
  Determinize.new(fa, options).main
end

Instance Method Details

#main ⇒ Object 



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
 
# File 'lib/stamina-core/stamina/automaton/determinize.rb', line 56

def main
  # the alphabet
  alph = fa.alphabet

  # the minimized automaton
  minimized = Automaton.new

  # - map between compound states and minimized states
  # - states to visit
  map = {}
  to_visit = []

  # initial state and mark as to visit
  init = CompoundState.new(fa, fa.initial_states, true)
  map[init] = minimized.add_state(init.marks)
  to_visit  = [init]

  until to_visit.empty?
    current = to_visit.pop
    alph.each do |symbol|
      found = current.delta(symbol)
      next if found.empty?
      unless map.has_key?(found)
        map[found] = minimized.add_state(found.marks)
        to_visit << found
      end
      minimized.connect(map[current], map[found], symbol)
    end
  end

  minimized
end