Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
Public Types | Public Member Functions
automaton::EpsilonNFA< SymbolTypeT, StateTypeT > Class Template Referencefinal

Epsilon nondeterministic finite automaton. Accepts regular languages. More...

#include <EpsilonNFA.h>

Inheritance diagram for automaton::EpsilonNFA< SymbolTypeT, StateTypeT >:
[legend]
Collaboration diagram for automaton::EpsilonNFA< SymbolTypeT, StateTypeT >:
[legend]

Public Types

typedef SymbolTypeT SymbolType
 
typedef StateTypeT StateType
 

Public Member Functions

const StateTypegetInitialState () const &
 
StateType && getInitialState () &&
 
bool setInitialState (StateType state)
 
const ext::set< StateType > & getStates () const &
 
ext::set< StateType > && getStates () &&
 
bool addState (StateType state)
 
void setStates (ext::set< StateType > states)
 
void removeState (const StateType &state)
 
const ext::set< StateType > & getFinalStates () const &
 
ext::set< StateType > && getFinalStates () &&
 
bool addFinalState (StateType state)
 
void setFinalStates (ext::set< StateType > states)
 
void removeFinalState (const StateType &state)
 
const ext::set< SymbolType > & getInputAlphabet () const &
 
ext::set< SymbolType > && getInputAlphabet () &&
 
bool addInputSymbol (SymbolType symbol)
 
void addInputSymbols (ext::set< SymbolType > symbols)
 
void setInputAlphabet (ext::set< SymbolType > symbols)
 
void removeInputSymbol (const SymbolType &symbol)
 
 EpsilonNFA (StateType initialState)
 Creates a new instance of the automaton with a concrete initial state. More...
 
 EpsilonNFA (ext::set< StateType > states, ext::set< SymbolType > inputAlphabet, StateType initialState, ext::set< StateType > finalStates)
 Creates a new instance of the automaton with a concrete set of states, input alphabet, initial state, and a set of final states. More...
 
 EpsilonNFA (const MultiInitialStateNFA< SymbolType, StateType > &other)
 
 EpsilonNFA (const NFA< SymbolType, StateType > &other)
 
 EpsilonNFA (const DFA< SymbolType, StateType > &other)
 
- Public Member Functions inherited from core::Components< EpsilonNFA< DefaultSymbolType, DefaultStateType >, ext::set< DefaultSymbolType >, component::Set, InputAlphabet, ext::set< DefaultStateType >, component::Set, std::tuple< States, FinalStates >, DefaultStateType, component::Value, InitialState >
void accessComponent ()
 
bool addTransition (StateType from, common::symbol_or_epsilon< SymbolType > input, StateType to)
 Add a transition to the automaton. More...
 
bool addTransition (StateType from, SymbolType input, StateType to)
 Add a transition to the automaton. More...
 
bool addTransition (StateType from, StateType to)
 Add a transition to the automaton. More...
 
bool removeTransition (StateType from, common::symbol_or_epsilon< SymbolType > input, StateType to)
 Removes a transition to the automaton. More...
 
bool removeTransition (const StateType &from, const SymbolType &input, const StateType &to)
 Removes a transition from the automaton. More...
 
bool removeTransition (const StateType &from, const StateType &to)
 Removes a transition from the automaton. More...
 
const ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< SymbolType > >, StateType > & getTransitions () const &
 
ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< SymbolType > >, StateType > && getTransitions () &&
 
ext::multimap< StateType, StateTypegetEpsilonTransitions () const
 
ext::multimap< ext::pair< StateType, SymbolType >, StateTypegetSymbolTransitions () const
 
ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< SymbolType > >, StateTypegetTransitionsFromState (const StateType &from) const
 
ext::multimap< StateType, StateTypegetEpsilonTransitionsFromState (const StateType &from) const
 
ext::multimap< ext::pair< StateType, SymbolType >, StateTypegetSymbolTransitionsFromState (const StateType &from) const
 
ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< SymbolType > >, StateTypegetTransitionsToState (const StateType &to) const
 
ext::multimap< StateType, StateTypegetEpsilonTransitionsToState (const StateType &to) const
 
ext::multimap< ext::pair< StateType, SymbolType >, StateTypegetSymbolTransitionsToState (const StateType &to) const
 
bool isEpsilonFree () const
 Determines whether the automaton is without epsilon transitions. More...
 
bool isDeterministic () const
 Determines whether the automaton is deterministic. More...
 
bool isTotal () const
 Determines whether the automaton is total deterministic. More...
 
auto operator<=> (const EpsilonNFA &other) const
 
bool operator== (const EpsilonNFA &other) const
 
ext::ostreamoperator<< (ext::ostream &out, const EpsilonNFA &instance)
 

Additional Inherited Members

- Static Public Member Functions inherited from core::Components< EpsilonNFA< DefaultSymbolType, DefaultStateType >, ext::set< DefaultSymbolType >, component::Set, InputAlphabet, ext::set< DefaultStateType >, component::Set, std::tuple< States, FinalStates >, DefaultStateType, component::Value, InitialState >
static void registerComponent ()
 
static void unregisterComponent ()
 

Detailed Description

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
class automaton::EpsilonNFA< SymbolTypeT, StateTypeT >

Epsilon nondeterministic finite automaton. Accepts regular languages.

Definition is classical definition of finite automata. A = (Q, T, I, \delta, F), Q (States) = nonempty finite set of states, T (TerminalAlphabet) = finite set of terminal symbols - having this empty won't let automaton do much though, I (InitialState) = initial state, \delta = transition function of the form A \times a -> P(Q), where A \in Q, a \in T \cup \epsilon\}, and P(Q) is a powerset of states, F (FinalStates) = set of final states

Template Parameters
SymbolTypeTused for the terminal alphabet
StateTypeTused to the states, and the initial state of the automaton.

Member Typedef Documentation

◆ StateType

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
typedef StateTypeT automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::StateType

◆ SymbolType

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
typedef SymbolTypeT automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::SymbolType

Constructor & Destructor Documentation

◆ EpsilonNFA() [1/5]

template<class SymbolType , class StateType >
automaton::EpsilonNFA< SymbolType, StateType >::EpsilonNFA ( StateType  initialState)
explicit

Creates a new instance of the automaton with a concrete initial state.

Parameters
initialStatethe initial state of the automaton

◆ EpsilonNFA() [2/5]

template<class SymbolType , class StateType >
automaton::EpsilonNFA< SymbolType, StateType >::EpsilonNFA ( ext::set< StateType states,
ext::set< SymbolType inputAlphabet,
StateType  initialState,
ext::set< StateType finalStates 
)
explicit

Creates a new instance of the automaton with a concrete set of states, input alphabet, initial state, and a set of final states.

Parameters
statesthe initial set of states of the automaton
inputAlphabetthe initial input alphabet
initialStatethe initial state of the automaton
finalStatesthe initial set of final states of the automaton

◆ EpsilonNFA() [3/5]

template<class SymbolType , class StateType >
automaton::EpsilonNFA< SymbolType, StateType >::EpsilonNFA ( const MultiInitialStateNFA< SymbolType, StateType > &  other)
explicit
Here is the call graph for this function:

◆ EpsilonNFA() [4/5]

template<class SymbolType , class StateType >
automaton::EpsilonNFA< SymbolType, StateType >::EpsilonNFA ( const NFA< SymbolType, StateType > &  other)
explicit
Here is the call graph for this function:

◆ EpsilonNFA() [5/5]

template<class SymbolType , class StateType >
automaton::EpsilonNFA< SymbolType, StateType >::EpsilonNFA ( const DFA< SymbolType, StateType > &  other)
explicit
Here is the call graph for this function:

Member Function Documentation

◆ addFinalState()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
bool automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::addFinalState ( StateType  state)
inline

Adder of a final state.

Parameters
statethe new state to be added to a set of final states
Returns
true if the state was indeed added
Here is the caller graph for this function:

◆ addInputSymbol()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
bool automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::addInputSymbol ( SymbolType  symbol)
inline

Adder of a input symbol.

Parameters
symbolthe new symbol to be added to an input alphabet
Returns
true if the symbol was indeed added

◆ addInputSymbols()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
void automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::addInputSymbols ( ext::set< SymbolType symbols)
inline

Adder of input symbols.

Parameters
symbolsnew symbols to be added to an input alphabet

◆ addState()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
bool automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::addState ( StateType  state)
inline

Adder of a state.

Parameters
statethe new state to be added to a set of states
Returns
true if the state was indeed added
Here is the caller graph for this function:

◆ addTransition() [1/3]

template<class SymbolType , class StateType >
bool automaton::EpsilonNFA< SymbolType, StateType >::addTransition ( StateType  from,
common::symbol_or_epsilon< SymbolType input,
StateType  to 
)

Add a transition to the automaton.

The transition is in a form A \times a -> B, where A, B \in Q and a \in T \cup \epsilon\}

Parameters
currentthe source state (A)
inputthe input symbol or epsilon (a)
nextthe target state (B)
Exceptions
AutomatonExceptionwhen transition contains state or symbol not present in the automaton components
Returns
true if the transition was indeed added
Here is the call graph for this function:
Here is the caller graph for this function:

◆ addTransition() [2/3]

template<class SymbolType , class StateType >
bool automaton::EpsilonNFA< SymbolType, StateType >::addTransition ( StateType  from,
StateType  to 
)

Add a transition to the automaton.

The transition is in a form A \times \epsilon -> B, where A, B \in Q

Parameters
currentthe source state (A)
nextthe target state (B)
Exceptions
AutomatonExceptionwhen transition contains state or symbol not present in the automaton components
Returns
true if the transition was indeed added

◆ addTransition() [3/3]

template<class SymbolType , class StateType >
bool automaton::EpsilonNFA< SymbolType, StateType >::addTransition ( StateType  from,
SymbolType  input,
StateType  to 
)

Add a transition to the automaton.

The transition is in a form A \times a -> B, where A, B \in Q and a \in T

Parameters
currentthe source state (A)
inputthe input symbol (a)
nextthe target state (B)
Exceptions
AutomatonExceptionwhen transition contains state or symbol not present in the automaton components
Returns
true if the transition was indeed added

◆ getEpsilonTransitions()

template<class SymbolType , class StateType >
ext::multimap< StateType, StateType > automaton::EpsilonNFA< SymbolType, StateType >::getEpsilonTransitions

Get the epsilon transitions of the automaton

Returns
epsilon transitions of the automaton
Here is the caller graph for this function:

◆ getEpsilonTransitionsFromState()

template<class SymbolType , class StateType >
ext::multimap< StateType, StateType > automaton::EpsilonNFA< SymbolType, StateType >::getEpsilonTransitionsFromState ( const StateType from) const

Get a subset of epsilon transitions of the automaton, with the source state fixed in the transitions natural representation.

Parameters
fromfilter the transition function based on this state as a source state
Returns
a subset of epsilon transitions of the automaton with the source state fixed
Here is the call graph for this function:

◆ getEpsilonTransitionsToState()

template<class SymbolType , class StateType >
ext::multimap< StateType, StateType > automaton::EpsilonNFA< SymbolType, StateType >::getEpsilonTransitionsToState ( const StateType to) const

Get a subset of epsilon transitions of the automaton, with the target state fixed in the transitions natural representation.

Parameters
tofilter the transition function based on this state as a source state
Returns
a subset of epsilon transitions of the automaton with the target state fixed
Here is the call graph for this function:

◆ getFinalStates() [1/2]

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
ext::set< StateType > && automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::getFinalStates ( ) &&
inline

Getter of final states.

Returns
the final states of the automaton
Here is the call graph for this function:

◆ getFinalStates() [2/2]

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
const ext::set< StateType > & automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::getFinalStates ( ) const &
inline

Getter of final states.

Returns
the final states of the automaton
Here is the caller graph for this function:

◆ getInitialState() [1/2]

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
StateType && automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::getInitialState ( ) &&
inline

Getter of the initial state.

Returns
the initial state of the automaton
Here is the call graph for this function:

◆ getInitialState() [2/2]

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
const StateType & automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::getInitialState ( ) const &
inline

Getter of the initial state.

Returns
the initial state of the automaton
Here is the caller graph for this function:

◆ getInputAlphabet() [1/2]

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
ext::set< SymbolType > && automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::getInputAlphabet ( ) &&
inline

Getter of the input alphabet.

Returns
the input alphabet of the automaton
Here is the call graph for this function:

◆ getInputAlphabet() [2/2]

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
const ext::set< SymbolType > & automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::getInputAlphabet ( ) const &
inline

Getter of the input alphabet.

Returns
the input alphabet of the automaton
Here is the caller graph for this function:

◆ getStates() [1/2]

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
ext::set< StateType > && automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::getStates ( ) &&
inline

Getter of states.

Returns
the states of the automaton
Here is the call graph for this function:

◆ getStates() [2/2]

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
const ext::set< StateType > & automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::getStates ( ) const &
inline

Getter of states.

Returns
the states of the automaton
Here is the caller graph for this function:

◆ getSymbolTransitions()

Get the non-epsilon transitions of the automaton

Returns
non-epsilon transitions of the automaton
Here is the call graph for this function:
Here is the caller graph for this function:

◆ getSymbolTransitionsFromState()

template<class SymbolType , class StateType >
ext::multimap< ext::pair< StateType, SymbolType >, StateType > automaton::EpsilonNFA< SymbolType, StateType >::getSymbolTransitionsFromState ( const StateType from) const

Get a subset of non-epsilon transitions of the automaton, with the source state fixed in the transitions natural representation.

Parameters
fromfilter the transition function based on this state as a source state
Returns
a subset of non-epsilon transitions of the automaton with the source state fixed
Here is the call graph for this function:

◆ getSymbolTransitionsToState()

template<class SymbolType , class StateType >
ext::multimap< ext::pair< StateType, SymbolType >, StateType > automaton::EpsilonNFA< SymbolType, StateType >::getSymbolTransitionsToState ( const StateType to) const

Get a subset of non-epsilon transitions of the automaton, with the target state fixed in the transitions natural representation.

Parameters
tofilter the transition function based on this state as a source state
Returns
a subset of non-epsilon transitions of the automaton with the target state fixed
Here is the call graph for this function:

◆ getTransitions() [1/2]

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< SymbolType > >, StateType > && automaton::EpsilonNFA< SymbolType, StateType >::getTransitions ( ) &&

Get the transition function of the automaton in its natural form.

Returns
transition function of the automaton

◆ getTransitions() [2/2]

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
const ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< SymbolType > >, StateType > & automaton::EpsilonNFA< SymbolType, StateType >::getTransitions ( ) const &

Get the transition function of the automaton in its natural form.

Returns
transition function of the automaton
Here is the caller graph for this function:

◆ getTransitionsFromState()

template<class SymbolType , class StateType >
ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< SymbolType > >, StateType > automaton::EpsilonNFA< SymbolType, StateType >::getTransitionsFromState ( const StateType from) const

Get a subset of the transition function of the automaton, with the source state fixed in the transitions natural representation.

Parameters
fromfilter the transition function based on this state as a source state
Returns
a subset of the transition function of the automaton with the source state fixed
Here is the call graph for this function:
Here is the caller graph for this function:

◆ getTransitionsToState()

template<class SymbolType , class StateType >
ext::multimap< ext::pair< StateType, common::symbol_or_epsilon< SymbolType > >, StateType > automaton::EpsilonNFA< SymbolType, StateType >::getTransitionsToState ( const StateType to) const

Get a subset of the transition function of the automaton, with the target state fixed in the transitions natural representation.

Parameters
tofilter the transition function based on this state as a source state
Returns
a subset of the transition function of the automaton with the target state fixed
Here is the call graph for this function:

◆ isDeterministic()

template<class SymbolType , class StateType >
bool automaton::EpsilonNFA< SymbolType, StateType >::isDeterministic

Determines whether the automaton is deterministic.

The automaton is deterministic if and only if:

  • is epsilon free.
  • size of transition function \delta (from state, input symbol) \leq 1
Returns
true if the automaton is deterministic, false otherwise

◆ isEpsilonFree()

template<class SymbolType , class StateType >
bool automaton::EpsilonNFA< SymbolType, StateType >::isEpsilonFree

Determines whether the automaton is without epsilon transitions.

Returns
true when automaton doesn't contain epsilon transitions, false otherwise

◆ isTotal()

template<class SymbolType , class StateType >
bool automaton::EpsilonNFA< SymbolType, StateType >::isTotal

Determines whether the automaton is total deterministic.

The automaton is deterministic if and only if:

  • it is deterministic
  • size of transition function \forall states and \forall input symbols \delta (from state, input symbol) = 1
Returns
true if the automaton is total deterministic, false otherwise

◆ operator<=>()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
auto automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::operator<=> ( const EpsilonNFA< SymbolTypeT, StateTypeT > &  other) const
inline

The three way comparison implementation

Parameters
otherthe other instance
Returns
the ordering between this object and the other.
Here is the call graph for this function:

◆ operator==()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
bool automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::operator== ( const EpsilonNFA< SymbolTypeT, StateTypeT > &  other) const
inline

The equality comparison implementation.

Parameters
otherthe other object to compare with.
Returns
true if this and other objects are equal, false othervise
Here is the call graph for this function:

◆ removeFinalState()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
void automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::removeFinalState ( const StateType state)
inline

Remover of a final state.

Parameters
statea state to be removed from a set of final states
Returns
true if the state was indeed removed

◆ removeInputSymbol()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
void automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::removeInputSymbol ( const SymbolType symbol)
inline

Remover of an input symbol.

Parameters
symbola symbol to be removed from an input alphabet
Returns
true if the symbol was indeed removed

◆ removeState()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
void automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::removeState ( const StateType state)
inline

Remover of a state.

Parameters
statea state to be removed from a set of states
Returns
true if the state was indeed removed

◆ removeTransition() [1/3]

template<class SymbolType , class StateType >
bool automaton::EpsilonNFA< SymbolType, StateType >::removeTransition ( const StateType from,
const StateType to 
)

Removes a transition from the automaton.

The transition is in a form A \times \epsilon -> B, where A, B \in Q

Parameters
currentthe source state (A)
nextthe target state (B)
Returns
true if the transition was indeed removed

◆ removeTransition() [2/3]

template<class SymbolType , class StateType >
bool automaton::EpsilonNFA< SymbolType, StateType >::removeTransition ( const StateType from,
const SymbolType input,
const StateType to 
)

Removes a transition from the automaton.

The transition is in a form A \times a -> B, where A, B \in Q and a \in T

Parameters
currentthe source state (A)
inputthe input symbol (a)
nextthe target state (B)
Returns
true if the transition was indeed removed

◆ removeTransition() [3/3]

template<class SymbolType , class StateType >
bool automaton::EpsilonNFA< SymbolType, StateType >::removeTransition ( StateType  from,
common::symbol_or_epsilon< SymbolType input,
StateType  to 
)

Removes a transition to the automaton.

The transition is in a form A \times a -> B, where A, B \in Q and a \in T \cup \epsilon\}

Parameters
currentthe source state (A)
inputthe input symbol or epsilon (a)
nextthe target state (B)
Exceptions
AutomatonExceptionwhen transition contains state or symbol not present in the automaton components
Returns
true if the transition was indeed added
Here is the call graph for this function:

◆ setFinalStates()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
void automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::setFinalStates ( ext::set< StateType states)
inline

Setter of final states.

Parameters
statescompletely new set of final states

◆ setInitialState()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
bool automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::setInitialState ( StateType  state)
inline

Setter of the initial state.

Parameters
statenew initial state of the automaton
Returns
true if the initial state was indeed changed

◆ setInputAlphabet()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
void automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::setInputAlphabet ( ext::set< SymbolType symbols)
inline

Setter of input alphabet.

Parameters
symbolscompletely new input alphabet
Here is the caller graph for this function:

◆ setStates()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
void automaton::EpsilonNFA< SymbolTypeT, StateTypeT >::setStates ( ext::set< StateType states)
inline

Setter of states.

Parameters
statescompletely new set of states

Friends And Related Function Documentation

◆ operator<<

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
ext::ostream & operator<< ( ext::ostream out,
const EpsilonNFA< SymbolTypeT, StateTypeT > &  instance 
)
friend

Print this object as raw representation to ostream.

Parameters
outostream where to print
instanceobject to print
Returns
modified output stream

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