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.

Defines

INCLUDE_EMP_COMPILER_NFA_HPP_GUARD

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-deterministic finite automata.

Public Types

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

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

inline ~tNFA()

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

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

inline size_t GetSize() const: Return the current number of states.

inline size_t GetStartID() const

inline const DynamicBits &GetStart() const: Return start state and all others reachable through empty transitions.

inline DynamicBits GetNext(size_t sym, size_t from_id = 0) const: Return the states reachable from the current state given the provided symbol.

inline DynamicBits GetNext(size_t sym, const DynamicBits 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 BitSet<NUM_SYMBOLS> GetSymbolOptions(const DynamicBits &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 String &sym_set): Add a transition between states ‘from’ and ‘to’ that can be taken with all 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 all 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 all 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 DynamicBits GetEmptyStates() const: Return a vector of all empty states.

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

State() = default

Public Members

std::map<size_t, Transition> trans: What symbol transitions are available?

DynamicBits free_to: What other states can you move to for free?

DynamicBits free_from: What other states can move here for free?

struct Transition

Public Members

BitSet<NUM_SYMBOLS> 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 DynamicBits &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 BitVector &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 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 Types

using this_t = tNFA_State<NUM_SYMBOLS, STOP_TYPE>

Private Members

const tNFA<NUM_SYMBOLS, STOP_TYPE> &nfa: Which NFA is this state set associated with?

DynamicBits state_set: Which states are currently legal?