Class: Stamina::Automaton::Minimize::Hopcroft

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

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(automaton, options) ⇒ Hopcroft

Creates an algorithm instance

Raises:

  • (ArgumentError) 


7
8
9
10
 
# File 'lib/stamina-core/stamina/automaton/minimize/hopcroft.rb', line 7

def initialize(automaton, options)
  raise ArgumentError, "Deterministic automaton expected", caller unless automaton.deterministic?
  @automaton = automaton
end

Class Method Details

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

Execute the minimizer



111
112
113
 
# File 'lib/stamina-core/stamina/automaton/minimize/hopcroft.rb', line 111

def self.execute(automaton, options={})
  Hopcroft.new(automaton.strip.complete!, options).main
end

Instance Method Details

#compute_minimal_dfa(groups) ⇒ Object

Computes a minimal dfa from the grouping information



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

def compute_minimal_dfa(groups)
  indexes = []
  fa = Automaton.new do |fa|

    # create one state for each group
    groups.each_with_index do |group,index|
      group.each{|s| indexes[s.index] = index}
      data = group.inject(nil) do |memo,s|
        if memo.nil?
          s.data
        else
          {:initial   => memo[:initial]   || s.initial?,
           :accepting => memo[:accepting] || s.accepting?,
           :error     => memo[:error]     || s.error?}
        end
      end
      fa.add_state(data)
    end

    # connect transitions now
    groups.each_with_index do |group,index|
      group.each do |s|
        s_index = indexes[s.index]
        s.out_edges.each do |edge|
          symbol, t_index = edge.symbol, indexes[edge.target.index]
          unless fa.ith_state(s_index).dfa_step(symbol)
            fa.connect(s_index, t_index, symbol)
          end
        end
      end
    end

  end
  fa.drop_states *fa.states.select{|s| s.sink?}
  fa.state_count == 0 ? Automaton::DUM : fa
end

#initial_partition ⇒ Object

Computes the initial partition



62
63
64
65
66
67
68
 
# File 'lib/stamina-core/stamina/automaton/minimize/hopcroft.rb', line 62

def initial_partition
  p = [Set.new, Set.new]
  @automaton.states.each do |s|
    (s.accepting? ? p[0] : p[1]) << s
  end
  p.reject{|g| g.empty?}
end

#main ⇒ Object

Main method of the algorithm



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

def main
  # Partition states a first time according to accepting/non accepting
  @partition = initial_partition # P in pseudo code
  @worklist = @partition.dup     # W in pseudo code

  # Until a block needs to be refined
  until @worklist.empty?
    refined = @worklist.pop

    # We compute the reverse delta on the group and look at the groups
    rdelta = reverse_delta(refined)
    rdelta.each_pair do |symbol, sources| # sources is la in pseudo code

      # Find blocks to be refined
      @partition.dup.each_with_index do |block, index| # block is R in pseudo code
        next if block.subset?(sources)
        intersection = block & sources    # R1 in pseudo code
        next if intersection.empty?
        difference = block - intersection # R2 in pseudo code

        # replace R in P with R1 and R2
        @partition[index] = intersection
        @partition << difference

        # Adds the new blocks as to be refined
        if @worklist.include?(block)
          @worklist.delete(block)
          @worklist << intersection << difference
        else
          @worklist << (intersection.size <= difference.size ? intersection : difference)
        end
      end # @partition.each

    end # rdelta.each_pair
  end # until @worklist.empty?

  compute_minimal_dfa(@partition)
end

#reverse_delta(group) ⇒ Object

Compute a Hash => state_group from a group of states



13
14
15
16
17
18
19
20
21
 
# File 'lib/stamina-core/stamina/automaton/minimize/hopcroft.rb', line 13

def reverse_delta(group)
  h = Hash.new{|h,k| h[k]=Set.new}
  group.each do |state|
    state.in_edges.each do |edge|
      h[edge.symbol] << edge.source
    end
  end
  h
end