compiler/minimize.lua

   1 --[[--------------------------------------------------------------------
   2
   3   minimize.lua
   4
   5   Algorithm to transform a DFA into an equivalent DFA with the
   6   minimal number of states.  Uses Hopcroft's algorithm, which is
   7   O(n lg n) in the number of states, as explained by both Hopcroft
   8   and Gries (see BIBLIOGRAPHY for details).
   9
  10   Copyright (c) 2007 Joshua Haberman.  See LICENSE for details.
  11
  12 --------------------------------------------------------------------]]--
  13
  14 require "data_structures"
  15
  16 function hopcroft_minimize(dfa)
  17   -- First create the alphabet and an inverse transition table.
  18   local alphabet = dfa:get_outgoing_edge_values(dfa:states())
  19   local inverse_transitions = {}
  20
  21   for state in each(dfa:states()) do
  22     for symbol, dest_state, properties in state:transitions() do
  23       inverse_transitions[dest_state] = inverse_transitions[dest_state] or dfa:new_state()
  24       inverse_transitions[dest_state]:add_transition(symbol, state, properties)
  25     end
  26   end
  27
  28   -- Create initial blocks, grouped by finality.
  29   local initial_blocks = {}
  30   for state in each(dfa:states()) do
  31     local finality = state.final or "NONE"
  32     initial_blocks[finality] = initial_blocks[finality] or {}
  33     table.insert(initial_blocks[finality], state)
  34   end
  35
  36   local blocks = Set:new()
  37   local work_queue = Queue:new()
  38   local work_queue_set = Set:new()
  39   for finality, states in pairs(initial_blocks) do
  40     local block = Set:new(states)
  41     blocks:add(block)
  42     for state in each(states) do
  43       state.block = block
  44     end
  45     for symbol_tuple in each(alphabet) do
  46       local symbol, properties = unpack(symbol_tuple)
  47       work_queue:enqueue({block, symbol, properties})
  48       work_queue_set:add(tostring(block) .. tostring(symbol) .. tostring(properties))
  49     end
  50   end
  51
  52   while (not work_queue:isempty()) do
  53     local block, symbol, properties = unpack(work_queue:dequeue())
  54     work_queue_set:remove(tostring(block) .. tostring(symbol) .. tostring(properties))
  55
  56     -- determine what blocks need to be split
  57     local states_to_split = Set:new()
  58     for state in each(block) do
  59       if inverse_transitions[state] then
  60         states_to_split:add_collection(inverse_transitions[state]:transitions_for(symbol, properties))
  61       end
  62     end
  63
  64     -- split blocks
  65     local new_twins = {}
  66     for state_to_split in each(states_to_split) do
  67       for state in each(state_to_split.block) do
  68         local dest_state = state:transitions_for(symbol, properties):to_array()[1]
  69         if not (dest_state and dest_state.block == block) then
  70           if not new_twins[state.block] then
  71             local new_twin = Set:new()
  72             blocks:add(new_twin)
  73             new_twins[state.block] = new_twin
  74           end
  75           new_twins[state.block]:add(state)
  76         end
  77       end
  78     end
  79
  80     -- fix work queue according to splits
  81     for old_block, new_twin in pairs(new_twins) do
  82       for state in each(new_twin) do
  83         state.block:remove(state)
  84         state.block = new_twin
  85       end
  86
  87       local smaller_block
  88       if old_block:count() < new_twin:count() then
  89         smaller_block = old_block
  90       else
  91         smaller_block = new_twin
  92       end
  93
  94       for alphabet_symbol_tuple in each(alphabet) do
  95         local alphabet_symbol, alphabet_properties = unpack(alphabet_symbol_tuple)
  96         if work_queue_set:contains(tostring(old_block) .. tostring(alphabet_symbol) .. tostring(alphabet_properties)) then
  97           work_queue:enqueue({new_twin, alphabet_symbol, alphabet_properties})
  98           work_queue_set:add(tostring(new_twin) .. tostring(alphabet_symbol) .. tostring(alphabet_properties))
  99         else
 100           work_queue:enqueue({smaller_block, alphabet_symbol, alphabet_properties})
 101           work_queue_set:add(tostring(smaller_block) .. tostring(alphabet_symbol) .. tostring(alphabet_properties))
 102         end
 103       end
 104     end
 105   end
 106
 107   -- the blocks are the new states
 108   local states = {}
 109   for block in blocks:each() do
 110     states[block] = dfa:new_state()
 111     for state in each(block) do
 112       if state.final then
 113         states[block].final = state.final
 114       end
 115     end
 116   end
 117
 118   local minimal_dfa = dfa:new_graph()
 119   minimal_dfa.start = states[dfa.start.block]
 120   for block in blocks:each() do
 121     for state in each(block) do
 122       for symbol, dest_state, properties in state:transitions() do
 123         states[block]:add_transition(symbol, states[dest_state.block], properties)
 124       end
 125     end
 126   end
 127
 128   return minimal_dfa
 129 end
 130