Class: Stamina::Automaton::Compose

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

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(automata) ⇒ Compose

Returns a new instance of Compose.



8
9
10
11
12
 
# File 'lib/stamina-core/stamina/automaton/compose.rb', line 8

def initialize(automata)
  @automata = automata.collect{|a|
    a.deterministic? ? a : a.determinize
  }
end

Instance Attribute Details

#automata ⇒ Object (readonly)

Automata under composition



6
7
8
 
# File 'lib/stamina-core/stamina/automaton/compose.rb', line 6

def automata
  @automata
end

Class Method Details

.execute(automata) ⇒ Object 



70
71
72
 
# File 'lib/stamina-core/stamina/automaton/compose.rb', line 70

def self.execute(automata)
  Compose.new(automata).main
end

Instance Method Details

#main ⇒ Object 



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

def main
  # Map every symbol to concerned automata
  symbols = Hash.new{|h,k| h[k] = []}

  # The compound initial state
  init = []

  # Build the symbol table and prepare the initial state
  automata.each_with_index do |fa,i|
    fa.alphabet.each{|l| symbols[l][i] = fa}
    init << fa.initial_state
  end

  # Compound automaton and states already seen
  compound_fa = Automaton.new
  map = {init => compound_fa.add_state(marks(init, true))}

  # States to be visited
  to_visit = [init]

  until to_visit.empty?
    source = to_visit.pop
    symbols.each_pair do |symbol, automata|
      catch(:avoid) do
        # build the target state
        target = source.zip(automata).collect{|ss,a|
          if a.nil?
            # this automaton does no synchronize on symbol
            ss
          elsif tt = ss.dfa_delta(symbol)
            # it synchronizes and target has been found
            tt
          else
            # it synchronizes but target has not been found
            throw :avoid
          end
        }
        unless map.has_key?(target)
          map[target] = compound_fa.add_state(marks(target))
          to_visit << target
        end
        compound_fa.connect(map[source],map[target],symbol)
      end
    end
  end # to_visit.empty?

  compound_fa
end

#marks(compound, initial = false) ⇒ Object 



14
15
16
17
18
19
 
# File 'lib/stamina-core/stamina/automaton/compose.rb', line 14

def marks(compound, initial = false)
  {:initial   => initial,
   :accepting => compound.all?{|s| s.accepting?},
   :error     => compound.any?{|s| s.error?}
  }
end