FSM PROJECT

    Fsm*        fsm;
    ref<Fsm>    dfsm = DfaMaker(fsm).mkdfa();

    if (!dfsm) 
      cerr << "Error making nfa deterministic.";

00009                                                 : fsm_(fsm), debug_(debug) {
00010 }

00070                 {
00071 // Actual algorithm to generate a determinitic dfa out of an nfa.
00072 
00073 // Auxiliary typedef: sequence of sets of (nfa) states.
00074 typedef vector<Fsm::STATES>     CLOSURES;
00075 
00076 //  Each state of the new dfa corresponds to a set of states of the
00077 //  old nfa. We represent these new states as a vector of sets of
00078 //  states. Note that we use a vector, and not a set, because we
00079 //  intend to use the index in the vector to generate the name of the
00080 //  corresponding state in the dfa.
00081 
00082 CLOSURES        closures_;
00083 
00084 // First compute initial state of dfa: simply compute the closure set
00085 // of the nfa's initial state.
00086 
00087 Fsm::STATES initial_state;
00088 initial_state.insert(fsm_.initial_state());
00089 closures_.push_back(closure(initial_state));
00090 
00091 // Now we can construct the dfa.
00092 
00093 ref<Fsm>        dfsm = Fsm::create(mkstate(0));
00094 
00095 Fsm::STATES     R;
00096 
00097 // For each new state Q in closures_, we compute closure(delta(Q,a))
00098 // and add it to closures_ if necessary.
00099 
00100 for (unsigned int i=0; i < closures_.size(); ++i)
00101   // Say Q = closures_[i], the state for which we now will compute
00102   // delta(Q,a), for each a in the alphabet (of the nfa).
00103 
00104   for (Fsm::SYMBOLS::const_iterator a = fsm_.abegin(); a != fsm_.aend(); ++a )
00105     if (*a != Fsm::epsilon()) {
00106       // Compyte delta(Q,a) and take the closure of the result R.
00107       delta(closures_[i], *a, R);
00108       closure(R);
00109 
00110       // Check if R is already known. If not, add it to closures_.
00111       CLOSURES::const_iterator r(find(closures_.begin(), closures_.end(), R));
00112 
00113       int j; // Index of new state R in closures_ sequence.
00114 
00115       if (r == closures_.end()) { // R is new, add it to closures_.
00116         closures_.push_back(R);
00117         j = closures_.size() -1;
00118         }
00119       else // R is known
00120         j = r - closures_.begin();
00121 
00122       // Add a transition corresponding to delta(Q,a) = R.
00123       dfsm->add_transition(mkstate(i), *a, mkstate(j) );
00124       }
00125 
00126 // Add final states to new machine.
00127 for (unsigned int i=0; i < closures_.size(); ++i)
00128   if (is_final(closures_[i]))
00129     dfsm->add_final_state(mkstate(i));
00130 
00131 if (debug_)
00132   for (unsigned int i=0; i < closures_.size(); ++i) 
00133     *debug_ << mkstate(i) << " = " << closures_[i] << "\n";
00134   
00135 return dfsm;
00136 }

00063                        {
00064 // Generate a dummy state ``qi''.
00065 static const string q("q");
00066 return q + ntostr(i);
00067 }

00042                                                                     {
00043 // R will contain all states in delta(q,a) for some q in Q.
00044 R.clear();
00045 for (Fsm::STATES::const_iterator q = Q.begin(); q != Q.end(); ++q ) {
00046   const Fsm::STATES& r(fsm_.delta(*q,a));
00047   R.insert(r.begin(),r.end());
00048   }
00049 return R;
00050 }

00013                                     {
00014 
00015 // Expand s to contain all states that can be reached from s by
00016 // epsilon-transitions only.
00017 
00018 int n_added(0);
00019 
00020 // Fixpoint computation: keep adding states until we can do a complete
00021 // pass of s without having added any state.
00022 do {
00023   // Remember the size of s before we scan it.
00024   unsigned int old_size = s.size();
00025 
00026   for (Fsm::STATES::const_iterator q = s.begin(); q != s.end(); ++q ) {
00027     // Get delta(q,epsilon) and add its elements to s.
00028     const Fsm::STATES& target = fsm_.delta(*q, Fsm::epsilon() );
00029     s.insert(target.begin(), target.end());
00030     }
00031 
00032   // States have been added if the current size of s is larger than
00033   // the old size.
00034   n_added = ( s.size() - old_size );
00035   }
00036 while (n_added);
00037 
00038 return s;
00039 }

00053                                            {
00054 // A state of the dfa (i.e. a set of states of the ``old'' nfa, is
00055 // final iff it contains an ``old'' final state.
00056 for (Fsm::STATES::const_iterator q = Q.begin(); q != Q.end(); ++q )
00057   if (fsm_.is_final(*q))
00058     return true;
00059 return false;
00060 }

Public Methods
	DfaMaker (const Fsm &fsm, ostream *debug=0)
	Constructor, first argument is machine to make deterministic. More...
ref< Fsm >	mkdfa ()
	Return pointer to newly allocated dfa equivalent with fsm_. More...
Static Public Methods
Fsm::State	mkstate (int i)
	Generate name of the form ``q123'' where ``123'' is string rep. of i. More...
Private Methods
Fsm::STATES &	delta (const Fsm::STATES &Q, const Fsm::Symbol &a, Fsm::STATES &R)
	Compute the delta(Q,a) where Q is a set of ``old'' states. More...
Fsm::STATES &	closure (Fsm::STATES &Q) const
	Expand Q so that it is closed under epsilon-transitions. More...
bool	is_final (const Fsm::STATES &Q) const
	Does Q contain a final state from fsm_? More...
Private Attributes
const Fsm &	fsm_
	Machine to make deterministic. More...
ostream *	debug_
	If true, some debug output may be generated. More...

DfaMaker Class Reference

Public Methods

Static Public Methods

Private Methods

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation