Sha256: e71fa6e01cfd2b00b2bfd1f9f194f49a51a94b9b8771f2f6b40a7428a55e589a
Contents?: true
Size: 1.86 KB
Versions: 5
Compression:
Stored size: 1.86 KB
Contents
module Stamina
class Automaton
#
# Checks if this automaton is equivalent to another one.
#
# Automata must be both minimal and complete to guarantee that this method
# works.
#
def equivalent?(other, equiv = nil, key = :equiv_state)
equiv ||= Proc.new{|s1,s2| (s1 && s2) &&
(s1.accepting? == s2.accepting?) &&
(s1.error? == s2.error?) &&
(s1.initial? == s2.initial?) }
# Both must already have basic attributes in common
return false unless state_count==other.state_count
return false unless edge_count==other.edge_count
return false unless alphabet==other.alphabet
return false unless equiv[initial_state, other.initial_state]
# We instantiate the decoration algorithm for checking equivalence on this
# automaton:
# * decoration is the index of the equivalent state in other automaton
# * d0 is thus 'other.initial_state.index'
# * suppremum is identity and fails when the equivalent state is not unique
# * propagation checks transition function delta
#
algo = Stamina::Utils::Decorate.new(key)
algo.set_suppremum do |d0, d1|
if (d0.nil? or d1.nil?)
(d0 || d1)
elsif d0==d1
d0
else
raise Stamina::Abord
end
end
algo.set_propagate do |d,e|
reached = other.ith_state(d).dfa_step(e.symbol)
raise Stamina::Abord if reached.nil?
raise Stamina::Abord unless equiv[e.target, reached]
reached.index
end
# Run the algorithm now
begin
algo.execute(self, nil, other.initial_state.index)
return true
rescue Stamina::Abord
return false
end
end
alias :<=> :equivalent?
end # class Automaton
end # module Stamina
Version data entries
5 entries across 5 versions & 1 rubygems