Back to index

scribus-ng  1.3.4.dfsg+svn20071115
Public Types | Public Member Functions | Protected Attributes
automata::NFA< STATE, INPUT > Class Template Reference

#include <automata.h>

Inheritance diagram for automata::NFA< STATE, INPUT >:
Inheritance graph
[legend]
Collaboration diagram for automata::NFA< STATE, INPUT >:
Collaboration graph
[legend]

List of all members.

Public Types

typedef std::map< INPUT,
std::set< STATE > > 
Transitions

Public Member Functions

 NFA (STATE s, std::set< STATE > d)
 NFA (std::set< STATE > &states, std::set< INPUT > &inputs, STATE start, std::set< STATE > deflt)
void addTransition (STATE from, INPUT input, STATE to)
template<class NSTATE , class XXX >
DFA< NSTATE, INPUT > * constructDFA (XXX createState)
const std::set< STATE > & states () const
const std::set< INPUT > & inputs () const
const Transitionstransitions (STATE s) const
const STATE start () const
const std::set< STATE > deflt () const
const std::set< STATE > next (STATE from, INPUT input) const
void addState (STATE newState)
void addInput (INPUT newInput)
void setTransition (STATE from, INPUT input, std::set< STATE >to)

Protected Attributes

std::set< STATE > states_
std::set< INPUT > inputs_
std::map< STATE, Transitionstransitions_
const Transitions noTransitions
STATE start_
std::set< STATE > default_

Detailed Description

template<class STATE, class INPUT>
class automata::NFA< STATE, INPUT >

Definition at line 96 of file automata.h.


Member Typedef Documentation

typedef std::map<INPUT, std::set< STATE > > automata::FA_base< STATE, INPUT, std::set< STATE > >::Transitions [inherited]

Definition at line 27 of file automata.h.


Constructor & Destructor Documentation

template<class STATE, class INPUT>
automata::NFA< STATE, INPUT >::NFA ( STATE  s,
std::set< STATE >  d 
) [inline]

Definition at line 98 of file automata.h.

: FA_base<STATE, INPUT, std::set<STATE> >(s, d)  { }
template<class STATE, class INPUT>
automata::NFA< STATE, INPUT >::NFA ( std::set< STATE > &  states,
std::set< INPUT > &  inputs,
STATE  start,
std::set< STATE >  deflt 
) [inline]

Definition at line 99 of file automata.h.

       : FA_base<STATE, INPUT, STATE>(states, inputs, start, deflt) { }

Member Function Documentation

void automata::FA_base< STATE, INPUT, std::set< STATE > >::addInput ( INPUT  newInput) [inherited]
void automata::FA_base< STATE, INPUT, std::set< STATE > >::addState ( STATE  newState) [inherited]
template<class STATE , class INPUT >
void automata::NFA< STATE, INPUT >::addTransition ( STATE  from,
INPUT  input,
STATE  to 
)

Definition at line 239 of file automata.h.

{
       typename FA_base<STATE,INPUT,std::set<STATE> >::Transitions & 
              trans(FA_base<STATE,INPUT,std::set<STATE> >::transitions_[from]);
       trans[input].insert(to);
}
template<class STATE, class INPUT>
template<class NSTATE , class XXX >
DFA<NSTATE,INPUT>* automata::NFA< STATE, INPUT >::constructDFA ( XXX  createState) [inline]

Definition at line 124 of file automata.h.

       {
              std::map<std::set<STATE>, NSTATE> newStates;
       
              std::set<STATE> startSet;
              startSet.insert(FA_base<STATE,INPUT,std::set<STATE> >::start_);
              NSTATE nstart = createState(startSet);
              newStates[startSet] = nstart;

              NSTATE deflt = createState(FA_base<STATE,INPUT,std::set<STATE> >::default_);
              newStates[FA_base<STATE,INPUT,std::set<STATE> >::default_] = deflt;
              
              DFA<NSTATE,INPUT>* result = new DFA<NSTATE,INPUT>(nstart, deflt);
              result->addState(deflt);
              
              std::deque<std::set<STATE> > todo;
              todo.push_back(startSet);
              
              while (todo.size() > 0)
              {
                     const std::set<STATE> from = todo.front();
                     todo.pop_front();
                     std::map<INPUT,std::set<STATE> > ntrans;
                     // for all states in from
                     typename std::set<STATE>::const_iterator s_it;
                     typename std::map<INPUT, std::set<STATE> >::iterator tr_it;
                     for (s_it=from.begin(); s_it != from.end(); ++s_it)
                     {
                            // for all transitions
                            typename FA_base<STATE,INPUT,std::set<STATE> >::Transitions& 
                                   trans(FA_base<STATE,INPUT,std::set<STATE> >::transitions_[*s_it]);
                            for (tr_it = trans.begin(); tr_it != trans.end(); ++tr_it)
                            {
                                   ntrans[tr_it->first].insert(tr_it->second.begin(), tr_it->second.end());
                            }
                     }
                     // construct new transitions
                     const NSTATE nfrom = newStates[from];
                     for (tr_it = ntrans.begin(); tr_it != ntrans.end(); ++tr_it)
                     {
                            std::set<STATE> & state(tr_it->second);
                            // create follow state
                            NSTATE nstate;
                            if ( newStates.find(state) == newStates.end() ) {
                                   nstate = createState(state);
                                   result->addState(nstate);
                                   newStates[state] = nstate;
                                   // remember follow state in todo if new
                                   todo.push_back(state);
                            }
                            else {
                                   nstate = newStates[state];
                            }
                            result->setTransition(nfrom, tr_it->first, nstate);
                     }
              }
              const std::set<INPUT>& inp(FA_base<STATE, INPUT, std::set<STATE> >::inputs());
              typename std::set<INPUT>::const_iterator i;
              for (i=inp.begin(); i != inp.end(); ++i)
                     result->addInput(*i);
              return result;
       }

Here is the call graph for this function:

Here is the caller graph for this function:

const std::set< STATE > automata::FA_base< STATE, INPUT, std::set< STATE > >::deflt ( ) const [inherited]

Here is the caller graph for this function:

const std::set<INPUT>& automata::FA_base< STATE, INPUT, std::set< STATE > >::inputs ( ) const [inherited]

Here is the caller graph for this function:

const std::set< STATE > automata::FA_base< STATE, INPUT, std::set< STATE > >::next ( STATE  from,
INPUT  input 
) const [inherited]
void automata::FA_base< STATE, INPUT, std::set< STATE > >::setTransition ( STATE  from,
INPUT  input,
std::set< STATE >  to 
) [inherited]
const STATE automata::FA_base< STATE, INPUT, std::set< STATE > >::start ( ) const [inherited]
const std::set<STATE>& automata::FA_base< STATE, INPUT, std::set< STATE > >::states ( ) const [inherited]
const Transitions& automata::FA_base< STATE, INPUT, std::set< STATE > >::transitions ( STATE  s) const [inherited]

Member Data Documentation

std::set< STATE > automata::FA_base< STATE, INPUT, std::set< STATE > >::default_ [protected, inherited]

Definition at line 46 of file automata.h.

std::set<INPUT> automata::FA_base< STATE, INPUT, std::set< STATE > >::inputs_ [protected, inherited]

Definition at line 42 of file automata.h.

const Transitions automata::FA_base< STATE, INPUT, std::set< STATE > >::noTransitions [protected, inherited]

Definition at line 44 of file automata.h.

STATE automata::FA_base< STATE, INPUT, std::set< STATE > >::start_ [protected, inherited]

Definition at line 45 of file automata.h.

std::set<STATE> automata::FA_base< STATE, INPUT, std::set< STATE > >::states_ [protected, inherited]

Definition at line 41 of file automata.h.

std::map<STATE, Transitions> automata::FA_base< STATE, INPUT, std::set< STATE > >::transitions_ [protected, inherited]

Definition at line 43 of file automata.h.


The documentation for this class was generated from the following file: