FSM PROJECT

00001 // $Id: optimizer.C,v 1.5 2001/08/08 12:33:33 dvermeir Exp $
00002 
00003 #include "fsm.h"
00004 #include "optimizer.h"
00005 
00006 
00007 Optimizer::Optimizer(const Fsm& fsm, ostream* debug): fsm_(fsm), debug_(debug) {
00008 }
00009 
00010 bool&
00011 Optimizer::distinct(const Fsm::State& q1, const Fsm::State& q2) {
00012 // The distinct_ matrix is symmetric, we only store distinct_[q1,q2]
00013 // if q1 > q2.
00014 if (q1 < q2)
00015   return distinct_[make_pair(q2,q1)];
00016 else
00017   return distinct_[make_pair(q1,q2)];
00018 }
00019 
00020 ref<Fsm>
00021 Optimizer::optimize() {
00022 // Optimization algorithm.
00023 
00024 if (!fsm_.is_deterministic())
00025   return ref<Fsm>();
00026 
00027 // Initialization of distinct_: any final state is distinct from any
00028 // non-final state.
00029 
00030 for (Fsm::STATES::const_iterator i= fsm_.sbegin(); i != fsm_.send(); ++i)
00031   for (Fsm::STATES::const_iterator j = fsm_.sbegin(); j!=i; ++j)
00032     distinct(*i,*j) = ( fsm_.is_final(*i) != fsm_.is_final(*j) );
00033 
00034 // Fixpoint computation of distinct_: i is distinct from j if
00035 // delta(i,a) is distinct from delta(j,a) for some a.
00036 
00037 bool change(true);
00038 
00039 while (change) {
00040   change = false;
00041   for (Fsm::STATES::const_iterator i = fsm_.sbegin(); i != fsm_.send(); ++i)
00042     for (Fsm::STATES::const_iterator j = fsm_.sbegin(); j!=i; ++j)
00043       if (distinct(*i,*j))
00044         ;
00045       else { 
00046         // Check if distinct(delta(*i,a),delta(*j,a)) for some a.
00047         for (Fsm::SYMBOLS::const_iterator a = fsm_.abegin(); a!= fsm_.aend(); ++a) {
00048           Fsm::State     qi(fsm_.ddelta(*i,*a));
00049           Fsm::State     qj(fsm_.ddelta(*j,*a));
00050           if (distinct(qi,qj)) {
00051             distinct(*i,*j) = change = true;
00052             break; // out of for loop through alphabet
00053             }
00054           }
00055         }
00056         
00057   }
00058 
00059 if (debug_) {
00060   for (Fsm::STATES::const_iterator i = fsm_.sbegin(); i != fsm_.send(); ++i)
00061     for (Fsm::STATES::const_iterator j = fsm_.sbegin(); j!=i; ++j) 
00062       *debug_ << "distinct(" << *i << "," << *j << ") = "
00063               << ( distinct(*i,*j) ? "true" : "false" ) << "\n";
00064   }
00065 
00066 // Create new dfa: it suffices to select a single representative q for
00067 // each class Q of undistinguishable states and define the transitions
00068 // new_delta(q,a) = p where p is a representative of the class of
00069 // delta(q,a).
00070 
00071 ref<Fsm> ofsm(Fsm::create(eq_class(fsm_.initial_state())));
00072 
00073 // Define final states: just add a representative of the class of each
00074 // origvinal final state. Duplicates will automatically be refused by
00075 // Fsm::add_final_state functions.
00076 for (Fsm::STATES::const_iterator i = fsm_.fbegin(); i != fsm_.fend(); ++i) 
00077   ofsm->add_final_state(eq_class(*i));
00078 
00079 // Define transitions: just translate delta(q,a) = p to delta(q',a) =
00080 // p' where q' is the representative of the class of q and p' is the
00081 // representative of the class of p.
00082 
00083 for (Fsm::STATES::const_iterator i = fsm_.sbegin(); i != fsm_.send(); ++i) 
00084   for (Fsm::SYMBOLS::const_iterator a = fsm_.abegin(); a!= fsm_.aend(); ++a) 
00085     ofsm->add_transition(eq_class(*i), *a, eq_class(fsm_.ddelta(*i,*a)));
00086 
00087 return ofsm;
00088 }
00089 
00090 Fsm::State
00091 Optimizer::eq_class(const Fsm::State& q) {
00092 // Compute the equivalence class of q and return its representative,
00093 // i.e. the minimal one in the order defined on states.
00094 Fsm::STATES     e;
00095 e.insert(q);
00096 
00097 for (Fsm::STATES::const_iterator i = fsm_.sbegin(); i != fsm_.send(); ++i)
00098   if ( (*i!=q) && (!distinct(*i,q)) )
00099     e.insert(*i);
00100 
00101 if (debug_)
00102   *debug_ << "eq_class(" << q << ") = " << e << "\n";
00103 
00104 return *e.begin();
00105 }