#include <optimizer.h>
Collaboration diagram for Optimizer:
Public Methods | |
| Optimizer (const Fsm &fsm, ostream *trace=0) | |
| Constructor, if trace is not 0, debug info will be written on it,. More... | |
| ref< Fsm > | optimize () |
Private Types | |
| typedef map< pair< Fsm::State, Fsm::State >, bool > | DISTINCT_T |
| Type of distinct_ data member. More... | |
Private Methods | |
| bool & | distinct (const Fsm::State &, const Fsm::State &) |
| Convenient access to Optimizer::dictinct_ data member. More... | |
| Fsm::State | eq_class (const Fsm::State &q) |
| Return representative of set of states that are equivalent to q. More... | |
Private Attributes | |
| DISTINCT_T | distinct_ |
| Matrix representing equivalence of states. More... | |
| const Fsm & | fsm_ |
| Automaton that will be optimized. More... | |
| ostream * | debug_ |
| Stream for debug output. More... | |
It relies on the Fsm interface to query the input dfa and to build the new optimal dfa.
Definition at line 13 of file optimizer.h.
|
|
Type of distinct_ data member. A ``triangular'' boolean matrix representing a symmetric relation between states. Definition at line 24 of file optimizer.h. |
|
|||||||||||||||
|
Constructor, if trace is not 0, debug info will be written on it,.
Definition at line 7 of file optimizer.C. |
|
|
Definition at line 21 of file optimizer.C. 00021 {
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 }
|
|
|||||||||||||||
|
Convenient access to Optimizer::dictinct_ data member. The arguments will be switched to match the implementation of the ``triangular'' matrix. Definition at line 11 of file optimizer.C. Referenced by eq_class(), and optimize().
00011 {
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 }
|
|
|
Return representative of set of states that are equivalent to q.
Definition at line 91 of file optimizer.C. Referenced by optimize().
00091 {
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 }
|
|
|
Matrix representing equivalence of states. If q1 and q2 are not equivalent, then distinct_[q1,q2] = true. Do not access directly, use the Optimizer::distinct function instead. Definition at line 32 of file optimizer.h. |
|
|
Automaton that will be optimized.
Definition at line 44 of file optimizer.h. |
|
|
Stream for debug output.
Definition at line 46 of file optimizer.h. |