---

fsm.h

Go to the documentation of this file.

#ifndef FSM_H
#define FSM_H
// $Id: fsm.h,v 1.8 2001/08/08 12:33:32 dvermeir Exp $

#include <iostream>
#include <string>
#include <set>
#include <map>
#include <stdexcept>

#include "ref.h" // reference-counted pointers



class Fsm {
public:

  typedef string State;

  typedef set<State> STATES;

  typedef string Symbol;
  typedef set<Symbol> SYMBOLS;

  typedef map<pair<State,Symbol>,STATES > TRANSITIONS;


  static const Symbol& epsilon();


  static ref<Fsm> create(const State& initial_state);
  virtual ~Fsm();


  Fsm& add_state(const State& s);

  Fsm& add_symbol(const Symbol& a);

  Fsm& add_final_state(const State& s);

  Fsm& add_transition(const State& q1,const Symbol& a, const State& q2);

  const State& initial_state() const { return initial_state_; }
  const STATES& final_states() const { return final_states_; }
  const STATES& states() const { return states_; }

  bool is_final(const State& s) const;


  const STATES&     delta(const State&, const Symbol&) const;

  const State&      ddelta(const State&, const Symbol&) const
                                                        throw(runtime_error);


  bool is_deterministic() const;

  TRANSITIONS::const_iterator   begin() const { return transitions_.begin(); }
  TRANSITIONS::const_iterator   end() const { return transitions_.end(); }

  STATES::const_iterator    sbegin() const { return states_.begin(); }
  STATES::const_iterator    send() const { return states_.end(); }

  STATES::const_iterator    fbegin() const { return final_states_.begin(); }
  STATES::const_iterator    fend() const { return final_states_.end(); }

  SYMBOLS::const_iterator    abegin() const { return alphabet_.begin(); }
  SYMBOLS::const_iterator    aend() const { return alphabet_.end(); }

  friend ostream& operator<<(ostream& os, const Fsm& fsm);

protected:

  Fsm(const State& initial_state);

private:
  State         initial_state_;
  STATES        final_states_;
  STATES        states_;
  SYMBOLS       alphabet_;


  TRANSITIONS   transitions_;

};

ostream&
operator<<(ostream&, const Fsm::STATES& Q);
#endif

---

FSM [ August, 2001]