NFA.hpp

A Non-deterministic Finite Automata simulator.

To build a standard NFA, use NFA. If you want to have more symbols or more stop states, use tNFA<S,T> where S is the number of symbols and T is the type used for stop. (defaults are 128 for ASCII-128 and uint8_t respectively.)

The constructor can take as parameters the number of states and the id of the start state (both default to 0)

Note

Status: BETA

Note

DFA’s use SetTransition(), but NFA’s use AddTransition. This distinction is intentional since in a DFA a second SetTransition with the same start state and symbol will override first, while in an NFA a second AddTransition will always add a new option.

Typedefs

using NFA = tNFA<128, uint8_t>

NFA is the most standard tNFA setup.

using NFA_State = tNFA_State<128, uint8_t>

NFA_State is the most standard tNFA_State setup.

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

#include <NFA.hpp>

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

Public Types

using opts_t = BitSet<NUM_SYMBOLS>

using stop_t = STOP_TYPE

Public Functions

inline tNFA(size_t num_states = 1, size_t start_state = 0)

tNFA(const tNFA<S, STOP_TYPE>&) = default

inline ~tNFA()

tNFA<S, STOP_TYPE> &operator=(const tNFA<S, STOP_TYPE>&) = default

inline size_t GetSize() const

Return the current number of states.

inline const std::set<size_t> &GetStart() const

Return start state and all others reachable through empty transitions.

inline 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.

inline 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.

inline bool HasFreeTransitions(size_t id) const

Does the provided state have free transitions?

inline bool HasSymTransitions(size_t id) const

Does the provided state have symbol-transitions?

inline opts_t GetSymbolOptions(const std::set<size_t> &test_set) const

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

inline void Resize(size_t new_size)

Change the number of available states.

inline size_t AddNewState()

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

inline void AddTransitionSymbol(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.

inline void AddTransition(size_t from, size_t to, const char sym)

Add a transition between states ‘from’ and ‘to’ that can be taken with a char symbol.

inline 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.

inline void AddTransition(size_t from, size_t to, const char *sym_set)

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

inline 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.

inline void AddFreeTransition(size_t from, size_t to)

Create a free transition between ‘from’ and ‘to’.

template<typename T = stop_t>
inline void SetStop(size_t state, T stop_val = 1)

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

inline stop_t GetStop(size_t state) const

Get any stop value associated with the provided state.

inline bool IsStart(size_t state) const

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

inline bool IsStop(size_t state) const

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

inline bool IsEmpty(size_t state) const

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

inline void Merge(const tNFA<NUM_SYMBOLS, STOP_TYPE> &nfa2)

Merge another NFA into this one.

inline void Print() const

Print information about this NFA (for debugging)

inline void PrintFreeMoves()

Identify free moves in NFA (for debugging)

Public Static Attributes

static constexpr const size_t NUM_SYMBOLS = S

Private Members

vector<State> states

Information about available states.

size_t start

Main start state (others might be reached for free.)

vector<STOP_TYPE> is_stop

0=no 1=yes (char instead of bool for speed)

struct State

Public Functions

inline State()

Public Members

std::map<size_t, Transition> trans

What symbol transitions are available?

std::set<size_t> free_to

What other states can you move to for free?

std::set<size_t> free_from

What other states can move here for free?

struct Transition

Public Functions

inline Transition()

Public Members

opts_t symbols

template<size_t NUM_SYMBOLS = 128, typename STOP_TYPE = uint8_t>
class tNFA_State

#include <NFA.hpp>

Information about the current full state (i.e., set of legal states) of an NFA.

Public Functions

inline tNFA_State(const tNFA<NUM_SYMBOLS, STOP_TYPE> &_nfa)

inline ~tNFA_State()

inline const tNFA<NUM_SYMBOLS, STOP_TYPE> &GetNFA() const

Get the NFA associated with this state.

inline const std::set<size_t> &GetStateSet() const

Get a set of states that are currently active.

inline bool IsActive() const

Are there currently any legal NFA states?

inline bool IsStop() const

Can we legally stop in any of the current states?

inline bool HasState(size_t id)

Is a particular NFA state currently included?

inline size_t GetSize()

How many states are currently included?

inline void SetStateSet(const std::set<size_t> &in)

Set the current states.

inline void Reset()

Change current states to start + free transitions from start.

inline void Next(size_t sym)

Update states given a new input symbol.

inline void Next(const std::string &sym_set)

Update states given a new series of input symbols (as a string)

inline void Print()

Print out current information about this NFA State (for debugging)

Private Members

const tNFA<NUM_SYMBOLS, STOP_TYPE> &nfa

Which NFA is this state set associated with?

std::set<size_t> state_set

Which states are currently legal?