---

mkdfa.C

Go to the documentation of this file.

// $Id: mkdfa.C,v 1.5 2001/08/08 12:33:33 dvermeir Exp $
#include <algorithm>

#include "fsm.h"
#include "ntostr.h"

#include "mkdfa.h"

DfaMaker::DfaMaker(const Fsm& fsm, ostream* debug): fsm_(fsm), debug_(debug) {
}

Fsm::STATES&
DfaMaker::closure(Fsm::STATES& s) const {

// Expand s to contain all states that can be reached from s by
// epsilon-transitions only.

int n_added(0);

// Fixpoint computation: keep adding states until we can do a complete
// pass of s without having added any state.
do {
  // Remember the size of s before we scan it.
  unsigned int old_size = s.size();

  for (Fsm::STATES::const_iterator q = s.begin(); q != s.end(); ++q ) {
    // Get delta(q,epsilon) and add its elements to s.
    const Fsm::STATES& target = fsm_.delta(*q, Fsm::epsilon() );
    s.insert(target.begin(), target.end());
    }

  // States have been added if the current size of s is larger than
  // the old size.
  n_added = ( s.size() - old_size );
  }
while (n_added);

return s;
}

Fsm::STATES&
DfaMaker::delta(const Fsm::STATES& Q, const Fsm::Symbol& a, Fsm::STATES& R) {
// R will contain all states in delta(q,a) for some q in Q.
R.clear();
for (Fsm::STATES::const_iterator q = Q.begin(); q != Q.end(); ++q ) {
  const Fsm::STATES& r(fsm_.delta(*q,a));
  R.insert(r.begin(),r.end());
  }
return R;
}

bool
DfaMaker::is_final(const Fsm::STATES& Q) const {
// A state of the dfa (i.e. a set of states of the ``old'' nfa, is
// final iff it contains an ``old'' final state.
for (Fsm::STATES::const_iterator q = Q.begin(); q != Q.end(); ++q )
  if (fsm_.is_final(*q))
    return true;
return false;
}

Fsm::State
DfaMaker::mkstate(int i) {
// Generate a dummy state ``qi''.
static const string q("q");
return q + ntostr(i);
}

ref<Fsm>
DfaMaker::mkdfa() {
// Actual algorithm to generate a determinitic dfa out of an nfa.

// Auxiliary typedef: sequence of sets of (nfa) states.
typedef vector<Fsm::STATES>     CLOSURES;

//  Each state of the new dfa corresponds to a set of states of the
//  old nfa. We represent these new states as a vector of sets of
//  states. Note that we use a vector, and not a set, because we
//  intend to use the index in the vector to generate the name of the
//  corresponding state in the dfa.

CLOSURES        closures_;

// First compute initial state of dfa: simply compute the closure set
// of the nfa's initial state.

Fsm::STATES initial_state;
initial_state.insert(fsm_.initial_state());
closures_.push_back(closure(initial_state));

// Now we can construct the dfa.

ref<Fsm>        dfsm = Fsm::create(mkstate(0));

Fsm::STATES     R;

// For each new state Q in closures_, we compute closure(delta(Q,a))
// and add it to closures_ if necessary.

for (unsigned int i=0; i < closures_.size(); ++i)
  // Say Q = closures_[i], the state for which we now will compute
  // delta(Q,a), for each a in the alphabet (of the nfa).

  for (Fsm::SYMBOLS::const_iterator a = fsm_.abegin(); a != fsm_.aend(); ++a )
    if (*a != Fsm::epsilon()) {
      // Compyte delta(Q,a) and take the closure of the result R.
      delta(closures_[i], *a, R);
      closure(R);

      // Check if R is already known. If not, add it to closures_.
      CLOSURES::const_iterator r(find(closures_.begin(), closures_.end(), R));

      int j; // Index of new state R in closures_ sequence.

      if (r == closures_.end()) { // R is new, add it to closures_.
        closures_.push_back(R);
        j = closures_.size() -1;
        }
      else // R is known
        j = r - closures_.begin();

      // Add a transition corresponding to delta(Q,a) = R.
      dfsm->add_transition(mkstate(i), *a, mkstate(j) );
      }

// Add final states to new machine.
for (unsigned int i=0; i < closures_.size(); ++i)
  if (is_final(closures_[i]))
    dfsm->add_final_state(mkstate(i));

if (debug_)
  for (unsigned int i=0; i < closures_.size(); ++i) 
    *debug_ << mkstate(i) << " = " << closures_[i] << "\n";
  
return dfsm;
}

---

FSM [ August, 2001]