Class: Stamina::Automaton::Minimize::Hopcroft
- Inherits:
-
Object
- Object
- Stamina::Automaton::Minimize::Hopcroft
- Defined in:
- lib/stamina-core/stamina/automaton/minimize/hopcroft.rb
Class Method Summary collapse
-
.execute(automaton, options = {}) ⇒ Object
Execute the minimizer.
Instance Method Summary collapse
-
#compute_minimal_dfa(groups) ⇒ Object
Computes a minimal dfa from the grouping information.
-
#initial_partition ⇒ Object
Computes the initial partition.
-
#initialize(automaton, options) ⇒ Hopcroft
constructor
Creates an algorithm instance.
-
#main ⇒ Object
Main method of the algorithm.
-
#reverse_delta(group) ⇒ Object
Compute a Hash => state_group from a group of states.
Constructor Details
#initialize(automaton, options) ⇒ Hopcroft
Creates an algorithm instance
7 8 9 10 |
# File 'lib/stamina-core/stamina/automaton/minimize/hopcroft.rb', line 7 def initialize(automaton, ) raise ArgumentError, "Deterministic automaton expected", caller unless automaton.deterministic? @automaton = automaton end |
Class Method Details
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 |