Class: Stamina::Automaton::Minimize::Pitchies

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

Overview

Straightforward and simple to understand minimization algorithm.

The principle of the algorithm is to successively refine a partition of the DFA states. This partition is represented by an array of integers, one for each state, that uniquely identifies the partition block to which the state belongs. As usual, the initial partition separates accepting from non accepting states:

P0 = [0, 1, 0, 0, ..., 1]  # N integers, 1 (resp. 0) for accepting (resp
                           # non accepting) states.

A refinement step of the algorithm consists in refining this partition by looking forward in the DFA for each symbol in the alphabet. Consider a given symbol, say ‘a’, and the transition function given by a (complete) DFA. We can represent the restriction of this function over a given symbol, say ‘a’ by a simple array, containing the target state reached through ‘a’ for each state of the DFA:

DELTA('a') = [5, 7, 1, ..., 0] # N integers, containing the unique identifier
                               # of the target state reached through 'a' from
                               # each state of the DFA, in order

Now, given a partition of the DFA states Pi, one can simply look which block of the partition is reached through a given letter, say ‘a’ by combining it with DELTA(‘a’)

REACHED(Pi, 'a') = [ Pi[DELTA('a')[j]] | foreach 0 <= j < N-1 ]

Given a partition Pi, if two states in the same block reach different blocks along the same symbol, they must be separated, by definition. Interrestingly, this information is contained in pairs of integers given by Pi and REACHED(Pi, ‘a’). In other words, consider the pairs

PAIRS(Pi, 'a') = [ (Pi[j], REACHED(Pi, 'a')[j]) | foreach 0 <= j < N-1 ]

Now, without loss of generality, one can simply give a unique number to each different pair in such an array of pairs (a naïve way of doing so is to define a total order relation over pairs, sorting them, and taking the smallest index of each pair in the sorted array). This leads to a partition refinement:

REFINEMENT(Pi, 'a') = [ unique-number-of(PAIRS(Pi, 'a')[j]) | foreach 0 <= j < N-1 ]

A step of the algorithm consists in applying such a refinement for each symbol in the alphabet:

foreach symbol in Sigma
  Pi = REFINEMENT(Pi, symbol)

The algorithm applies such refinements until a fix point is reached:

# Trivial partition with all states in same block
Pi = [ 0 | foreach 0 <= j < N-1 ]

# initial non trivial partition separating accepting for non accepting
# states
Pj = [...]

# fixpoint loop until Pi == Pj, i.e. no change has been made
while Pj != Pi   # warning here, we compare the real partitions...
  Pi = Pj
  foreach symbol in Sigma
    Pj = REFINEMENT(Pj, symbol)
end

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(automaton, options) ⇒ Pitchies

Creates an algorithm instance

Raises:

  • (ArgumentError) 


72
73
74
75
 
# File 'lib/stamina-core/stamina/automaton/minimize/pitchies.rb', line 72

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



123
124
125
 
# File 'lib/stamina-core/stamina/automaton/minimize/pitchies.rb', line 123

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

Instance Method Details

#main ⇒ Object 



107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
# File 'lib/stamina-core/stamina/automaton/minimize/pitchies.rb', line 107

def main
  alph, states = @automaton.alphabet, @automaton.states
  old_nb_states = -1
  partition = states.map{|s| s.accepting? ? 1 : 0}
  until (nb_states = partition.uniq.size) == old_nb_states
    old_nb_states = nb_states
    alph.each do |symbol|
      reached = states.map{|s| partition[s.dfa_step(symbol).index]}
      rehash = Hash.new{|h,k| h[k] = h.size}
      partition = partition.zip(reached).map{|pair| rehash[pair]}
    end
  end
  minimized_dfa(@automaton, nb_states, partition)
end

#minimized_dfa(oldfa, nb_states, partition) ⇒ Object 



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

def minimized_dfa(oldfa, nb_states, partition)
  fa = Automaton.new(false) do |newfa|
    # Add the number of states, with default marks
    newfa.add_n_states(nb_states, {:initial => false, :accepting => false, :error => false})

    # Refine the marks using the source dfa as reference
    partition.each_with_index do |block, state_index|
      source = oldfa.ith_state(state_index)
      target = newfa.ith_state(block)
      target.initial!   if source.initial?
      target.accepting! if source.accepting?
      target.error!     if source.error?
    end

    # Now, create the transitions
    partition.each_with_index do |block, state_index|
      source = oldfa.ith_state(state_index)
      target = newfa.ith_state(block)
      source.out_edges.each do |edge|
        where = partition[edge.target.index]
        if target.dfa_step(edge.symbol) == nil
          newfa.connect(target, where, edge.symbol)
        end
      end
    end
  end
  fa.drop_states *fa.states.select{|s| s.sink?}
  fa.state_count == 0 ? Automaton::DUM : fa
end