Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

Fsm Class Reference

Class representing finite state machines. More...

#include <fsm.h>

List of all members.

Public Types

typedef string State
 Type of state. More...

typedef set< State > STATES
 Type of set of states. More...

typedef string Symbol
 Type of symbol. More...

typedef set< Symbol > SYMBOLS
 Type of set of symbols. More...

typedef map< pair< State,
Symbol >, STATES > 		TRANSITIONS
 Type used to store transitions. More...


Public Methods

virtual ~Fsm ()
 Destructor, probably a noop. More...

Fsm & add_state (const State &s)
 Add state. More...

Fsm & add_symbol (const Symbol &a)
 Add symbol. More...

Fsm & add_final_state (const State &s)
 Add final state, also does add_state(s). More...

Fsm & add_transition (const State &q1, const Symbol &a, const State &q2)
 Add transition. More...

const State & initial_state () const
 Return initial state. More...

const STATES & final_states () const
 Return final states. More...

const STATES & states () const
 Return all states. More...

bool is_final (const State &s) const
 Is this a final state? More...

const STATES & delta (const State &, const Symbol &) const
 Delta function. More...

const State & ddelta (const State &, const Symbol &) const throw (runtime_error)
 Deterministic delta function. More...

bool is_deterministic () const
 Is this a deterministic machine? More...

TRANSITIONS::const_iterator begin () const
 Return iterator pointing to first transition. More...

TRANSITIONS::const_iterator end () const
 Return iterator pointing just after last transition. More...

STATES::const_iterator sbegin () const
 Return iterator pointing to first state. More...

STATES::const_iterator send () const
 Return iterator pointing just after last state. More...

STATES::const_iterator fbegin () const
 Return iterator pointing to first final state. More...

STATES::const_iterator fend () const
 Return iterator pointing just after last final state. More...

SYMBOLS::const_iterator abegin () const
 Return iterator pointing to first symbol in alphabet. More...

SYMBOLS::const_iterator aend () const
 Return iterator pointing just after last symbol in alphabet. More...


Static Public Methods

const Symbol & epsilon ()
 Return special ``epsilon'' symbol. More...

ref< Fsm > create (const State &initial_state)
 Static factory method replacing constructor (which is protected). More...


Protected Methods

 Fsm (const State &initial_state)
 Constructor, parameter is initial state. More...


Private Attributes

State initial_state_
 Initial state. More...

STATES final_states_
 Final states, use set for reasonably fast access. More...

STATES states_
 All states. More...

SYMBOLS alphabet_
 All symbols, i.e. alphabet of fsm. More...

TRANSITIONS transitions_
 Transitions. More...


Friends

ostream & operator<< (ostream &os, const Fsm &fsm)
 Print textual representation of this fsm. More...

Detailed Description

Class representing finite state machines.

A more generic approach would use the types State and Symbol as template parameters, i.e. 

    template<typename State, typename Symbol>
    class Fsm {
    ...
    }

Definition at line 24 of file fsm.h.

Member Typedef Documentation

typedef string Fsm::State
 

Type of state.

This is a simple solution. However, it is probably sufficient. After all: the required operations on a State are few: we shoul be able to print its name, build containers of State's (for this we need e.g. State::operator<), check whether states are equal (State::operator==). All of these (and more) are supported by string.

Definition at line 34 of file fsm.h.

typedef set<State> Fsm::STATES
 

Type of set of states.

E.g. the Fsm::delta function will return a reference to an object of this type.

Definition at line 39 of file fsm.h.

typedef string Fsm::Symbol
 

Type of symbol.

This is a simple solution. However, it is probably sufficient. After all: the required operations on a Symbol are few: we shoul be able to print it, build containers of Symbol's (for this we need e.g. Symbol::operator<), check whether symbols are equal (Symbol::operator==). All of these (and more) are supported by string.

Definition at line 48 of file fsm.h.

typedef set<Symbol> Fsm::SYMBOLS
 

Type of set of symbols.

Definition at line 50 of file fsm.h.

typedef map<pair<State,Symbol>,STATES > Fsm::TRANSITIONS
 

Type used to store transitions.

E.g. if delta(p,a) contains q, then 

      TRANSITIONS       ts;

      ts[make_pair(p,a)].count(q) != 0

The make_pair can be avoided by using Fsm::delta.

A more efficient representation could be devised for deterministic automata.

Definition at line 65 of file fsm.h.

Constructor & Destructor Documentation

Fsm::~Fsm (  )  [virtual]
 

Destructor, probably a noop.

Definition at line 15 of file fsm.C.

00015           {
00016 }

Fsm::Fsm (  const State & s )  [protected]
 

Constructor, parameter is initial state.

Requiring the initial state as a parameter for the constructor saves a lot of checking. Now we can be sure that every Fsm object has an initial state.

Note that the other member data of Fsm, namely the final states and the transitions, are sets which could be empty without complicating the code.

Definition at line 10 of file fsm.C.

Referenced by create(). 

00010                       : initial_state_(s) {
00011 // The initial state is also a state.
00012 add_state(s);
00013 }

Member Function Documentation

const Fsm::Symbol & Fsm::epsilon (  )  [static]
 

Return special ``epsilon'' symbol.

Technically, epsilon() is not a symbol but a string.

Definition at line 19 of file fsm.C.

Referenced by DfaMaker::mkdfa(). 

00019              {
00020 // Return symbol used to represent empty string (for epsilon
00021 // transitions).
00022 static const string EPSILON("-");
00023 return EPSILON;
00024 }

ref< Fsm > Fsm::create (  const State & s )  [static]
 

Static factory method replacing constructor (which is protected).

We return a ref<Fsm> because this is convenient to use for parser & optimizer classes and it saves the bother of managing real pointers.

Definition at line 6 of file fsm.C.

Referenced by DfaMaker::mkdfa(), and Parser::parse(). 

00006                           {
00007 return ref<Fsm>(new Fsm(s));
00008 }

Fsm & Fsm::add_state (  const State & s ) 
 

Add state.

This function is automatically called e.g. by add_transition. Note that adding the same state twice has no effect.

Definition at line 27 of file fsm.C.

Referenced by Fsm(), add_final_state(), and add_transition(). 

00027                              {
00028 states_.insert(s);
00029 return *this;
00030 }

Fsm & Fsm::add_symbol (  const Symbol & a ) 
 

Add symbol.

This function is automatically called e.g. by add_transition. Note that adding the same symbol twice has no effect.

Definition at line 45 of file fsm.C.

Referenced by add_transition(). 

00045                                {
00046 alphabet_.insert(a);
00047 return *this;
00048 }

Fsm & Fsm::add_final_state (  const State & s ) 
 

Add final state, also does add_state(s).

Note that adding the same state twice has no effect.

Definition at line 33 of file fsm.C.

00033                                    {
00034 final_states_.insert(s);
00035 // A final state is also a state.
00036 return add_state(s);
00037 }

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

Add transition.

Also calls add_state(q1), add_state(q2), and add_symbol(a).

Note that adding the same transition twice has no effect.

Definition at line 51 of file fsm.C.

00051                                                                     {
00052 add_state(q1);
00053 add_state(q2);
00054 transitions_[make_pair(q1,a)].insert(q2);
00055 return add_symbol(a);
00056 }

const State& Fsm::initial_state (  )  const [inline]
 

Return initial state.

Definition at line 106 of file fsm.h.

Referenced by DfaMaker::mkdfa(), operator<<(), and Optimizer::optimize(). 

00106 { return initial_state_; }

const STATES& Fsm::final_states (  )  const [inline]
 

Return final states.

Definition at line 108 of file fsm.h.

Referenced by is_final(), and operator<<(). 

00108 { return final_states_; }

const STATES& Fsm::states (  )  const [inline]
 

Return all states.

Definition at line 110 of file fsm.h.

00110 { return states_; }

bool Fsm::is_final (  const State & q )  const
 

Is this a final state?

Definition at line 40 of file fsm.C.

Referenced by DfaMaker::is_final(), and Optimizer::optimize(). 

00040                                   {
00041 return final_states().count(q) > 0;
00042 }

const Fsm::STATES & Fsm::delta (  const State & q,
const Symbol & a
)  const
 

Delta function. 

      delta(s,a)
returns set of states that the machine may be in after receiving input a from state s.

Warning:
The return reference is probably not valid after a subsequent update of the transitions_ data member.

Definition at line 59 of file fsm.C.

Referenced by DfaMaker::closure(), DfaMaker::delta(), and is_deterministic(). 

00059                                                 {
00060 static const STATES EMPTY_SET;
00061 
00062 // Try to find a transition for (q,a).
00063 TRANSITIONS::const_iterator     i(transitions_.find(make_pair(q,a)));
00064 
00065 if (i == end()) // no transition, return empty set
00066   return EMPTY_SET;
00067 else
00068   return (*i).second;
00069 }

const Fsm::State & Fsm::ddelta (  const State & q,
const Symbol & a
)  const throw (runtime_error)
 

Deterministic delta function.

Only useful if the machine is deterministic.

The function will throw a runtime_error for undefined transitions or non-deterministic transitions.

Definition at line 72 of file fsm.C.

Referenced by Optimizer::optimize(). 

00072                                                                       {
00073 // Deterministic version of delta(q,a). Works only for deterministic
00074 // automata.
00075 
00076 // First get the delta(q,a) set.
00077 const STATES& states(delta(q,a));
00078 
00079 // It must be a singleton.
00080 if (states.size() != 1) {
00081   // 2 things can go wrong: not a dfa or a not in alphabet.
00082   const string error_msg(string("Fsm::ddelta(") + q + ", " + a + ")");
00083 
00084   if (alphabet_.count(a) == 0) 
00085     throw runtime_error(error_msg + ": unknown symbol");
00086   else
00087     throw runtime_error(error_msg + ": not a dfa");
00088   }
00089 
00090 // Now, we are sure that there is a single elementg in states.
00091 return *(states.begin());
00092 }

bool Fsm::is_deterministic (  )  const
 

Is this a deterministic machine?

Returns true iff there are no epsilon transitions and the size of delta(q,a) is exactly 1 for each known transition.

Definition at line 95 of file fsm.C.

Referenced by Optimizer::optimize(). 

00095                             {
00096 for (Fsm::STATES::const_iterator i = sbegin(); i != send(); ++i) 
00097   for (Fsm::SYMBOLS::const_iterator a = abegin(); a!= aend(); ++a) 
00098     if (delta(*i,*a).size() != 1)
00099       return false;
00100 return true;
00101 }

TRANSITIONS::const_iterator Fsm::begin (  )  const [inline]
 

Return iterator pointing to first transition.

Definition at line 142 of file fsm.h.

Referenced by operator<<(). 

00142 { return transitions_.begin(); }

TRANSITIONS::const_iterator Fsm::end (  )  const [inline]
 

Return iterator pointing just after last transition.

Definition at line 144 of file fsm.h.

Referenced by delta(), and operator<<(). 

00144 { return transitions_.end(); }

STATES::const_iterator Fsm::sbegin (  )  const [inline]
 

Return iterator pointing to first state.

Definition at line 147 of file fsm.h.

Referenced by Optimizer::eq_class(), is_deterministic(), and Optimizer::optimize(). 

00147 { return states_.begin(); }

STATES::const_iterator Fsm::send (  )  const [inline]
 

Return iterator pointing just after last state.

Definition at line 149 of file fsm.h.

Referenced by Optimizer::eq_class(), is_deterministic(), and Optimizer::optimize(). 

00149 { return states_.end(); }

STATES::const_iterator Fsm::fbegin (  )  const [inline]
 

Return iterator pointing to first final state.

Definition at line 152 of file fsm.h.

Referenced by Optimizer::optimize(). 

00152 { return final_states_.begin(); }

STATES::const_iterator Fsm::fend (  )  const [inline]
 

Return iterator pointing just after last final state.

Definition at line 154 of file fsm.h.

Referenced by Optimizer::optimize(). 

00154 { return final_states_.end(); }

SYMBOLS::const_iterator Fsm::abegin (  )  const [inline]
 

Return iterator pointing to first symbol in alphabet.

Definition at line 157 of file fsm.h.

Referenced by is_deterministic(), DfaMaker::mkdfa(), and Optimizer::optimize(). 

00157 { return alphabet_.begin(); }

SYMBOLS::const_iterator Fsm::aend (  )  const [inline]
 

Return iterator pointing just after last symbol in alphabet.

Definition at line 159 of file fsm.h.

Referenced by is_deterministic(), DfaMaker::mkdfa(), and Optimizer::optimize(). 

00159 { return alphabet_.end(); }

Friends And Related Function Documentation

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

Print textual representation of this fsm.

Definition at line 104 of file fsm.C.

00104                                         {
00105 os << fsm.initial_state() << "\n";
00106 
00107 os << fsm.final_states() << "\n";
00108 
00109 for (Fsm::TRANSITIONS::const_iterator i=fsm.begin(); i!=fsm.end(); ++i) 
00110   os << (*i).first.first << " " 
00111      << (*i).first.second << " " 
00112      << (*i).second
00113      << "\n";
00114 return os;
00115 }

Member Data Documentation

State Fsm::initial_state_ [private]
 

Initial state.

Definition at line 178 of file fsm.h.

STATES Fsm::final_states_ [private]
 

Final states, use set for reasonably fast access.

Definition at line 180 of file fsm.h.

STATES Fsm::states_ [private]
 

All states.

Definition at line 182 of file fsm.h.

SYMBOLS Fsm::alphabet_ [private]
 

All symbols, i.e. alphabet of fsm.

Definition at line 184 of file fsm.h.

TRANSITIONS Fsm::transitions_ [private]
 

Transitions.

E.g. if q' in delta(q,a) then 

      transitions_[make_pair(q,a)].count(q') = 1.

Definition at line 192 of file fsm.h.

The documentation for this class was generated from the following files:
FSM [ August, 2001]