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

Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages. More...

#include <NFTA.h>

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

Public Types

typedef SymbolTypeT SymbolType
 
typedef StateTypeT StateType
 

Public Member Functions

 NFTA ()
 Creates a new instance of the automaton. More...
 
 NFTA (ext::set< StateType > states, ext::set< common::ranked_symbol< SymbolType > > inputAlphabet, ext::set< StateType > finalStates)
 Creates a new instance of the automaton with a concrete set of states, input alphabet, and a set of final states. More...
 
 NFTA (const DFTA< SymbolType, StateType > &other)
 
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< common::ranked_symbol< SymbolType > > & getInputAlphabet () const &
 
ext::set< common::ranked_symbol< SymbolType > > && getInputAlphabet () &&
 
bool addInputSymbol (common::ranked_symbol< SymbolType > symbol)
 
void addInputSymbols (ext::set< common::ranked_symbol< SymbolType > > symbols)
 
void setInputAlphabet (ext::set< common::ranked_symbol< SymbolType > > symbols)
 
void removeInputSymbol (const common::ranked_symbol< SymbolType > &symbol)
 
bool addTransition (common::ranked_symbol< SymbolType > symbol, ext::vector< StateType > prevStates, StateType next)
 Add a transition to the automaton. More...
 
bool removeTransition (const common::ranked_symbol< SymbolType > &symbol, const ext::vector< StateType > &states, const StateType &next)
 Removes a transition from the automaton. More...
 
const ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > & getTransitions () const &
 
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > && getTransitions () &&
 
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateTypegetTransitionsToState (const StateType &q) const
 
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateTypegetTransitionsFromState (const StateType &q) const
 
bool isDeterministic () const
 Determines whether the automaton is deterministic. More...
 
auto operator<=> (const NFTA &other) const
 
bool operator== (const NFTA &other) const
 
- Public Member Functions inherited from core::Components< NFTA< DefaultSymbolType, DefaultStateType >, ext::set< common::ranked_symbol< DefaultSymbolType > >, component::Set, InputAlphabet, ext::set< DefaultStateType >, component::Set, std::tuple< States, FinalStates > >
void accessComponent ()
 

Friends

ext::ostreamoperator<< (ext::ostream &out, const NFTA &instance)
 

Additional Inherited Members

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

Detailed Description

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

Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.

Definition is classical definition of finite automata. A = (Q, \Sigma, \delta, F), Q (States) = nonempty finite set of states, \Sigma (TerminalAlphabet) = finite set of terminal ranked symbols - having this empty won't let automaton do much though,

Elements of the \delta multimapping must meet following criteria. The size of the state list must equal the rank of the ranked symbol.

Template Parameters
SymbolTypeTused for the symbol part of the ranked symbol
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::NFTA< SymbolTypeT, StateTypeT >::StateType

◆ SymbolType

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

Constructor & Destructor Documentation

◆ NFTA() [1/3]

template<class SymbolType , class StateType >
automaton::NFTA< SymbolType, StateType >::NFTA
explicit

Creates a new instance of the automaton.

◆ NFTA() [2/3]

template<class SymbolType , class StateType >
automaton::NFTA< SymbolType, StateType >::NFTA ( ext::set< StateType states,
ext::set< common::ranked_symbol< SymbolType > >  inputAlphabet,
ext::set< StateType finalStates 
)
explicit

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

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

◆ NFTA() [3/3]

template<class SymbolType , class StateType >
automaton::NFTA< SymbolType, StateType >::NFTA ( const DFTA< SymbolType, StateType > &  other)
explicit

Member Function Documentation

◆ addFinalState()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
bool automaton::NFTA< 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::NFTA< SymbolTypeT, StateTypeT >::addInputSymbol ( common::ranked_symbol< 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
Here is the caller graph for this function:

◆ addInputSymbols()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
void automaton::NFTA< SymbolTypeT, StateTypeT >::addInputSymbols ( ext::set< common::ranked_symbol< 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::NFTA< 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()

template<class SymbolType , class StateType >
bool automaton::NFTA< SymbolType, StateType >::addTransition ( common::ranked_symbol< SymbolType symbol,
ext::vector< StateType prevStates,
StateType  next 
)

Add a transition to the automaton.

The transition is in a form (Q^n \times \Sigma_n) \mapsto Q,

Parameters
childrenthe source states in Q^n
currentthe input symbol in \Sigma_n
nextthe target state in Q
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:

◆ getFinalStates() [1/2]

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
ext::set< StateType > && automaton::NFTA< 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::NFTA< SymbolTypeT, StateTypeT >::getFinalStates ( ) const &
inline

Getter of final states.

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

◆ getInputAlphabet() [1/2]

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
ext::set< common::ranked_symbol< SymbolType > > && automaton::NFTA< 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< common::ranked_symbol< SymbolType > > & automaton::NFTA< 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::NFTA< 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::NFTA< SymbolTypeT, StateTypeT >::getStates ( ) const &
inline

Getter of states.

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

◆ getTransitions() [1/2]

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > && automaton::NFTA< SymbolTypeT, StateTypeT >::getTransitions ( ) &&
inline

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< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > & automaton::NFTA< SymbolTypeT, StateTypeT >::getTransitions ( ) const &
inline

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 SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > automaton::NFTA< SymbolTypeT, StateTypeT >::getTransitionsFromState ( const StateType q) const
inline
Returns
transitions from state q
Here is the call graph for this function:

◆ getTransitionsToState()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > automaton::NFTA< SymbolTypeT, StateTypeT >::getTransitionsToState ( const StateType q) const
inline
Returns
transitions to state q
Here is the call graph for this function:
Here is the caller graph for this function:

◆ isDeterministic()

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

Determines whether the automaton is deterministic.

the automaton is deterministic if and only if:

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

◆ operator<=>()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
auto automaton::NFTA< SymbolTypeT, StateTypeT >::operator<=> ( const NFTA< 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::NFTA< SymbolTypeT, StateTypeT >::operator== ( const NFTA< 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::NFTA< 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::NFTA< SymbolTypeT, StateTypeT >::removeInputSymbol ( const common::ranked_symbol< 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::NFTA< 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()

template<class SymbolType , class StateType >
bool automaton::NFTA< SymbolType, StateType >::removeTransition ( const common::ranked_symbol< SymbolType > &  symbol,
const ext::vector< StateType > &  states,
const StateType next 
)

Removes a transition from the automaton.

The transition is in a form (Q^n \times \Sigma_n) \mapsto Q,

Parameters
childrenthe source states in Q^n
currentthe input symbol in \Sigma_n
nextthe target state in Q
Returns
true if the transition was indeed removed
Here is the call graph for this function:

◆ setFinalStates()

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

Setter of final states.

Parameters
statescompletely new set of final states

◆ setInputAlphabet()

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

Setter of input alphabet.

Parameters
symbolscompletely new input alphabet

◆ setStates()

template<class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType>
void automaton::NFTA< 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 NFTA< 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: