---

fsm.C

Go to the documentation of this file.

// $Id: fsm.C,v 1.9 2001/08/20 05:23:40 dvermeir Exp $

#include "fsm.h"

ref<Fsm>
Fsm::create(const State& s) {
return ref<Fsm>(new Fsm(s));
}

Fsm::Fsm(const State& s): initial_state_(s) {
// The initial state is also a state.
add_state(s);
}

Fsm::~Fsm() {
}

const Fsm::Symbol&
Fsm::epsilon() {
// Return symbol used to represent empty string (for epsilon
// transitions).
static const string EPSILON("-");
return EPSILON;
}

Fsm&
Fsm::add_state(const State& s) {
states_.insert(s);
return *this;
}

Fsm&
Fsm::add_final_state(const State& s) {
final_states_.insert(s);
// A final state is also a state.
return add_state(s);
}

bool
Fsm::is_final(const State& q) const {
return final_states().count(q) > 0;
}

Fsm&
Fsm::add_symbol(const Symbol& a) {
alphabet_.insert(a);
return *this;
}

Fsm&
Fsm::add_transition(const State& q1,const Symbol& a, const State& q2) {
add_state(q1);
add_state(q2);
transitions_[make_pair(q1,a)].insert(q2);
return add_symbol(a);
}

const Fsm::STATES&          
Fsm::delta(const State& q, const Symbol& a) const {
static const STATES EMPTY_SET;

// Try to find a transition for (q,a).
TRANSITIONS::const_iterator     i(transitions_.find(make_pair(q,a)));

if (i == end()) // no transition, return empty set
  return EMPTY_SET;
else
  return (*i).second;
}

const Fsm::State&           
Fsm::ddelta(const State& q, const Symbol& a) const throw(runtime_error) {
// Deterministic version of delta(q,a). Works only for deterministic
// automata.

// First get the delta(q,a) set.
const STATES& states(delta(q,a));

// It must be a singleton.
if (states.size() != 1) {
  // 2 things can go wrong: not a dfa or a not in alphabet.
  const string error_msg(string("Fsm::ddelta(") + q + ", " + a + ")");

  if (alphabet_.count(a) == 0) 
    throw runtime_error(error_msg + ": unknown symbol");
  else
    throw runtime_error(error_msg + ": not a dfa");
  }

// Now, we are sure that there is a single elementg in states.
return *(states.begin());
}

bool
Fsm::is_deterministic() const {
for (Fsm::STATES::const_iterator i = sbegin(); i != send(); ++i) 
  for (Fsm::SYMBOLS::const_iterator a = abegin(); a!= aend(); ++a) 
    if (delta(*i,*a).size() != 1)
      return false;
return true;
}

ostream&
operator<<(ostream& os, const Fsm& fsm) {
os << fsm.initial_state() << "\n";

os << fsm.final_states() << "\n";

for (Fsm::TRANSITIONS::const_iterator i=fsm.begin(); i!=fsm.end(); ++i) 
  os << (*i).first.first << " " 
     << (*i).first.second << " " 
     << (*i).second
     << "\n";
return os;
}

ostream&
operator<<(ostream& os, const Fsm::STATES& Q) {
os << "{ ";
for (Fsm::STATES::const_iterator q = Q.begin(); q != Q.end(); ++q)
  os << (*q)<< " "; 
os << "}";
return os;
}

---

FSM [ August, 2001]