Empirical
Classes | Public Types | Public Member Functions | Static Public Attributes | List of all members
emp::tNFA< S, STOP_TYPE > Class Template Reference

A dynamic NFA class, for easily building non-determanistic finite automata. More...

#include <NFA.h>

Public Types

using opts_t = BitSet< NUM_SYMBOLS >
 
using stop_t = STOP_TYPE
 

Public Member Functions

 tNFA (size_t num_states=1, size_t start_state=0)
 
 tNFA (const tNFA< S, STOP_TYPE > &)=default
 
 ~tNFA ()
 
tNFA< S, STOP_TYPE > & operator= (const tNFA< S, STOP_TYPE > &)=default
 
size_t GetSize () const
 Return the current number of states. More...
 
const std::set< size_t > & GetStart () const
 Return start state and all others reachable through empty transitions. More...
 
std::set< size_t > GetNext (size_t sym, size_t from_id=0) const
 Return the states reachable from the current state given the provided symbol. More...
 
std::set< size_t > GetNext (size_t sym, const std::set< size_t > from_set) const
 return the states reachable from the current set of states given the provided symbol. More...
 
bool HasFreeTransitions (size_t id) const
 Does the provided state have free transitions? More...
 
bool HasSymTransitions (size_t id) const
 Does the provided state have symbol-transitions? More...
 
opts_t GetSymbolOptions (const std::set< size_t > &test_set) const
 Return an emp::BitSet indicating the symbols available from the provided set of states. More...
 
void Resize (size_t new_size)
 Change the number of available states. More...
 
size_t AddNewState ()
 Add a new state into the NFA and return its id. More...
 
void AddTransition (size_t from, size_t to, size_t sym)
 Add a transition between states 'from' and 'to' that can be taken with the provided symbol. More...
 
void AddTransition (size_t from, size_t to, const std::string &sym_set)
 Add a transition between states 'from' and 'to' that can be taken with the provided symbols. More...
 
void AddTransition (size_t from, size_t to, const BitSet< NUM_SYMBOLS > &sym_set)
 Add a transition between states 'from' and 'to' that can be taken with the provided symbols. More...
 
void AddFreeTransition (size_t from, size_t to)
 Create a free transition between 'from' and 'to'. More...
 
template<typename T = stop_t>
void SetStop (size_t state, T stop_val=1)
 Set the specified state to be a stop state (with an optional stop value.) More...
 
stop_t GetStop (size_t state) const
 Get any stop value associated with the provided state. More...
 
bool IsStart (size_t state) const
 Test if NFA begins at provided state (may have free transitions to other states) More...
 
bool IsStop (size_t state) const
 Test if this state is a legal endpoint for the NFA. More...
 
bool IsEmpty (size_t state) const
 Test if this state has only empty transitions from it, and not stop state. More...
 
void Merge (const tNFA< NUM_SYMBOLS, STOP_TYPE > &nfa2)
 Merge another NFA into this one. More...
 
void Print () const
 Print information about this NFA (for debugging) More...
 
void PrintFreeMoves ()
 Identify free moves in NFA (for debugging) More...
 

Static Public Attributes

static const constexpr size_t NUM_SYMBOLS = S
 

Detailed Description

template<size_t S = 128, typename STOP_TYPE = uint8_t>
class emp::tNFA< S, STOP_TYPE >

A dynamic NFA class, for easily building non-determanistic finite automata.

Member Typedef Documentation

template<size_t S = 128, typename STOP_TYPE = uint8_t>
using emp::tNFA< S, STOP_TYPE >::opts_t = BitSet<NUM_SYMBOLS>
template<size_t S = 128, typename STOP_TYPE = uint8_t>
using emp::tNFA< S, STOP_TYPE >::stop_t = STOP_TYPE

Constructor & Destructor Documentation

template<size_t S = 128, typename STOP_TYPE = uint8_t>
emp::tNFA< S, STOP_TYPE >::tNFA ( size_t  num_states = 1,
size_t  start_state = 0 
)
inline
template<size_t S = 128, typename STOP_TYPE = uint8_t>
emp::tNFA< S, STOP_TYPE >::tNFA ( const tNFA< S, STOP_TYPE > &  )
default
template<size_t S = 128, typename STOP_TYPE = uint8_t>
emp::tNFA< S, STOP_TYPE >::~tNFA ( )
inline

Member Function Documentation

template<size_t S = 128, typename STOP_TYPE = uint8_t>
void emp::tNFA< S, STOP_TYPE >::AddFreeTransition ( size_t  from,
size_t  to 
)
inline

Create a free transition between 'from' and 'to'.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
size_t emp::tNFA< S, STOP_TYPE >::AddNewState ( )
inline

Add a new state into the NFA and return its id.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
void emp::tNFA< S, STOP_TYPE >::AddTransition ( size_t  from,
size_t  to,
size_t  sym 
)
inline

Add a transition between states 'from' and 'to' that can be taken with the provided symbol.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
void emp::tNFA< S, STOP_TYPE >::AddTransition ( size_t  from,
size_t  to,
const std::string &  sym_set 
)
inline

Add a transition between states 'from' and 'to' that can be taken with the provided symbols.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
void emp::tNFA< S, STOP_TYPE >::AddTransition ( size_t  from,
size_t  to,
const BitSet< NUM_SYMBOLS > &  sym_set 
)
inline

Add a transition between states 'from' and 'to' that can be taken with the provided symbols.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
std::set<size_t> emp::tNFA< S, STOP_TYPE >::GetNext ( size_t  sym,
size_t  from_id = 0 
) const
inline

Return the states reachable from the current state given the provided symbol.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
std::set<size_t> emp::tNFA< S, STOP_TYPE >::GetNext ( size_t  sym,
const std::set< size_t >  from_set 
) const
inline

return the states reachable from the current set of states given the provided symbol.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
size_t emp::tNFA< S, STOP_TYPE >::GetSize ( ) const
inline

Return the current number of states.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
const std::set<size_t>& emp::tNFA< S, STOP_TYPE >::GetStart ( ) const
inline

Return start state and all others reachable through empty transitions.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
stop_t emp::tNFA< S, STOP_TYPE >::GetStop ( size_t  state) const
inline

Get any stop value associated with the provided state.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
opts_t emp::tNFA< S, STOP_TYPE >::GetSymbolOptions ( const std::set< size_t > &  test_set) const
inline

Return an emp::BitSet indicating the symbols available from the provided set of states.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
bool emp::tNFA< S, STOP_TYPE >::HasFreeTransitions ( size_t  id) const
inline

Does the provided state have free transitions?

template<size_t S = 128, typename STOP_TYPE = uint8_t>
bool emp::tNFA< S, STOP_TYPE >::HasSymTransitions ( size_t  id) const
inline

Does the provided state have symbol-transitions?

template<size_t S = 128, typename STOP_TYPE = uint8_t>
bool emp::tNFA< S, STOP_TYPE >::IsEmpty ( size_t  state) const
inline

Test if this state has only empty transitions from it, and not stop state.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
bool emp::tNFA< S, STOP_TYPE >::IsStart ( size_t  state) const
inline

Test if NFA begins at provided state (may have free transitions to other states)

template<size_t S = 128, typename STOP_TYPE = uint8_t>
bool emp::tNFA< S, STOP_TYPE >::IsStop ( size_t  state) const
inline

Test if this state is a legal endpoint for the NFA.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
void emp::tNFA< S, STOP_TYPE >::Merge ( const tNFA< NUM_SYMBOLS, STOP_TYPE > &  nfa2)
inline

Merge another NFA into this one.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
tNFA<S,STOP_TYPE>& emp::tNFA< S, STOP_TYPE >::operator= ( const tNFA< S, STOP_TYPE > &  )
default
template<size_t S = 128, typename STOP_TYPE = uint8_t>
void emp::tNFA< S, STOP_TYPE >::Print ( ) const
inline

Print information about this NFA (for debugging)

template<size_t S = 128, typename STOP_TYPE = uint8_t>
void emp::tNFA< S, STOP_TYPE >::PrintFreeMoves ( )
inline

Identify free moves in NFA (for debugging)

template<size_t S = 128, typename STOP_TYPE = uint8_t>
void emp::tNFA< S, STOP_TYPE >::Resize ( size_t  new_size)
inline

Change the number of available states.

template<size_t S = 128, typename STOP_TYPE = uint8_t>
template<typename T = stop_t>
void emp::tNFA< S, STOP_TYPE >::SetStop ( size_t  state,
stop_val = 1 
)
inline

Set the specified state to be a stop state (with an optional stop value.)

Member Data Documentation

template<size_t S = 128, typename STOP_TYPE = uint8_t>
const constexpr size_t emp::tNFA< S, STOP_TYPE >::NUM_SYMBOLS = S
static

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