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

#include <ExtendedNFTA.h>

Inheritance diagram for automaton::ExtendedNFTA< SymbolType, StateType >:

Collaboration diagram for automaton::ExtendedNFTA< SymbolType, StateType >:

Public Member Functions
	ExtendedNFTA ()
	Creates a new instance of the automaton. More...

	ExtendedNFTA (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...

	ExtendedNFTA (const DFTA< SymbolType, StateType > &other)

	ExtendedNFTA (const NFTA< 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 (rte::FormalRTEStructure< ext::variant< SymbolType, StateType > > rte, ext::vector< StateType >, StateType next)
	Add a transition to the automaton. More...

void	addTransitions (rte::FormalRTEStructure< ext::variant< SymbolType, StateType > > rte, ext::vector< StateType >, ext::set< StateType > next)
	Add a transition to the automaton. More...

bool	removeTransition (const rte::FormalRTEStructure< ext::variant< SymbolType, StateType > > &rte, const ext::vector< StateType > &prevStates, const StateType &next)
	Removes a transition from the automaton. More...

const ext::map< ext::pair< rte::FormalRTEStructure< ext::variant< SymbolType, StateType > >, ext::vector< StateType > >, ext::set< StateType > > &	getTransitions () const &

ext::map< ext::pair< rte::FormalRTEStructure< ext::variant< SymbolType, StateType > >, ext::vector< StateType > >, ext::set< StateType > > &&	getTransitions () &&

ext::map< ext::pair< rte::FormalRTEStructure< ext::variant< SymbolType, StateType > >, ext::vector< StateType > >, StateType >	getTransitionsToState (const StateType &to) const

ext::map< ext::pair< rte::FormalRTEStructure< ext::variant< SymbolType, StateType > >, ext::vector< StateType > >, ext::set< StateType > >	getTransitionsFromState (const StateType &from) const

bool	isDeterministic () const
	Determines whether the automaton is deterministic. More...

unsigned	transitionsSize () const
	Computes number of transitions in the automaton. More...

auto	operator<=> (const ExtendedNFTA &other) const

bool	operator== (const ExtendedNFTA &other) const

Public Member Functions inherited from core::Components< ExtendedNFTA< DefaultSymbolType, DefaultStateType >, ext::set< common::ranked_symbol< DefaultSymbolType > >, component::Set, InputAlphabet, ext::set< DefaultStateType >, component::Set, std::tuple< States, FinalStates > >
void	accessComponent ()

Friends
ext::ostream &	operator<< (ext::ostream &out, const ExtendedNFTA &instance)

Additional Inherited Members
Static Public Member Functions inherited from core::Components< ExtendedNFTA< 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 SymbolType = DefaultSymbolType, class StateType = DefaultStateType>
class automaton::ExtendedNFTA< SymbolType, StateType >

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

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

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

Template Parameters

SymbolType	used for the symbol part of the ranked symbol
StateType	used to the states, and the initial state of the automaton.

Constructor & Destructor Documentation

◆ ExtendedNFTA() [1/4]

template<class SymbolType , class StateType >

automaton::ExtendedNFTA< SymbolType, StateType >::ExtendedNFTA

explicit

Creates a new instance of the automaton.

◆ ExtendedNFTA() [2/4]

template<class SymbolType , class StateType >

automaton::ExtendedNFTA< SymbolType, StateType >::ExtendedNFTA	(	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

states	the initial set of states of the automaton
inputAlphabet	the initial input alphabet
finalStates	the initial set of final states of the automaton

◆ ExtendedNFTA() [3/4]

template<class SymbolType , class StateType >

automaton::ExtendedNFTA< SymbolType, StateType >::ExtendedNFTA ( const DFTA< SymbolType, StateType > & other )

explicit

Here is the call graph for this function:

◆ ExtendedNFTA() [4/4]

template<class SymbolType , class StateType >

automaton::ExtendedNFTA< SymbolType, StateType >::ExtendedNFTA ( const NFTA< SymbolType, StateType > & other )

explicit

Here is the call graph for this function:

Member Function Documentation

◆ addFinalState()

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

bool automaton::ExtendedNFTA< SymbolType, StateType >::addFinalState ( StateType state )

inline

Adder of a final state.

Parameters

state the new state to be added to a set of final states

Returns: true if the state was indeed added

◆ addInputSymbol()

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

bool automaton::ExtendedNFTA< SymbolType, StateType >::addInputSymbol ( common::ranked_symbol< SymbolType > symbol )

inline

Adder of a input symbol.

Parameters

symbol the new symbol to be added to an input alphabet

Returns: true if the symbol was indeed added

◆ addInputSymbols()

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

void automaton::ExtendedNFTA< SymbolType, StateType >::addInputSymbols ( ext::set< common::ranked_symbol< SymbolType > > symbols )

inline

Adder of input symbols.

Parameters

symbols new symbols to be added to an input alphabet

◆ addState()

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

bool automaton::ExtendedNFTA< SymbolType, StateType >::addState ( StateType state )

inline

Adder of a state.

Parameters

state the new state to be added to a set of states

Returns: true if the state was indeed added

◆ addTransition()

template<class SymbolType , class StateType >

bool automaton::ExtendedNFTA< SymbolType, StateType >::addTransition	(	rte::FormalRTEStructure< ext::variant< SymbolType, StateType > >	rte,
		ext::vector< StateType >	prevStates,
		StateType	next
	)

Add a transition to the automaton.

The transition is in a form ( A, B, C, ... ) \times a -> X, where A, B, C, ..., X \in Q and a \in T

Parameters

children	the source states (A, B, C, ...)
current	the input symbol (a)
next	the target state (B)

Exceptions

AutomatonException when 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:

◆ addTransitions()

template<class SymbolType , class StateType >

void automaton::ExtendedNFTA< SymbolType, StateType >::addTransitions	(	rte::FormalRTEStructure< ext::variant< SymbolType, StateType > >	rte,
		ext::vector< StateType >	prevStates,
		ext::set< StateType >	next
	)

Add a transition to the automaton.

The transition is in a form ( A, B, C, ... ) \times a -> P(Q), where A, B, C, ... \in Q and a \in T, P(Q) is a powerset of states

Parameters

children	the source states (A, B, C, ...)
current	the input symbol (a)
next	the target states (P(Q))

Exceptions

AutomatonException when 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:

◆ getFinalStates() [1/2]

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

ext::set< StateType > && automaton::ExtendedNFTA< SymbolType, StateType >::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 SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

const ext::set< StateType > & automaton::ExtendedNFTA< SymbolType, StateType >::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 SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

ext::set< common::ranked_symbol< SymbolType > > && automaton::ExtendedNFTA< SymbolType, StateType >::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 SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

const ext::set< common::ranked_symbol< SymbolType > > & automaton::ExtendedNFTA< SymbolType, StateType >::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 SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

ext::set< StateType > && automaton::ExtendedNFTA< SymbolType, StateType >::getStates ( ) &&

inline

Getter of states.

Returns: the states of the automaton

Here is the call graph for this function:

◆ getStates() [2/2]

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

const ext::set< StateType > & automaton::ExtendedNFTA< SymbolType, StateType >::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 SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

ext::map< ext::pair< rte::FormalRTEStructure< ext::variant< SymbolType, StateType > >, ext::vector< StateType > >, ext::set< StateType > > && automaton::ExtendedNFTA< SymbolType, StateType >::getTransitions ( ) &&

inline

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

Returns: transition function of the automaton

◆ getTransitions() [2/2]

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

const ext::map< ext::pair< rte::FormalRTEStructure< ext::variant< SymbolType, StateType > >, ext::vector< StateType > >, ext::set< StateType > > & automaton::ExtendedNFTA< SymbolType, StateType >::getTransitions ( ) const &

inline

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

Returns: transition function of the automaton

◆ getTransitionsFromState()

template<class SymbolType , class StateType >

ext::map< ext::pair< rte::FormalRTEStructure< ext::variant< SymbolType, StateType > >, ext::vector< StateType > >, ext::set< StateType > > automaton::ExtendedNFTA< SymbolType, StateType >::getTransitionsFromState ( const StateType & from ) const

Returns: the subset of transitions where the state q is a source state

Here is the call graph for this function:

◆ getTransitionsToState()

template<class SymbolType , class StateType >

ext::map< ext::pair< rte::FormalRTEStructure< ext::variant< SymbolType, StateType > >, ext::vector< StateType > >, StateType > automaton::ExtendedNFTA< SymbolType, StateType >::getTransitionsToState ( const StateType & to ) const

Returns: the subset of transitions where the state q is a target state

Here is the call graph for this function:

◆ isDeterministic()

template<class SymbolType , class StateType >

bool automaton::ExtendedNFTA< 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 SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

auto automaton::ExtendedNFTA< SymbolType, StateType >::operator<=> ( const ExtendedNFTA< SymbolType, StateType > & other ) const

inline

The three way comparison implementation

Parameters

other the other instance

Returns: the ordering between this object and the other.

Here is the call graph for this function:

◆ operator==()

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

bool automaton::ExtendedNFTA< SymbolType, StateType >::operator== ( const ExtendedNFTA< SymbolType, StateType > & other ) const

inline

The equality comparison implementation.

Parameters

other the 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 SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

void automaton::ExtendedNFTA< SymbolType, StateType >::removeFinalState ( const StateType & state )

inline

Remover of a final state.

Parameters

state a state to be removed from a set of final states

Returns: true if the state was indeed removed

◆ removeInputSymbol()

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

void automaton::ExtendedNFTA< SymbolType, StateType >::removeInputSymbol ( const common::ranked_symbol< SymbolType > & symbol )

inline

Remover of an input symbol.

Parameters

symbol a symbol to be removed from an input alphabet

Returns: true if the symbol was indeed removed

◆ removeState()

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

void automaton::ExtendedNFTA< SymbolType, StateType >::removeState ( const StateType & state )

inline

Remover of a state.

Parameters

state a 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::ExtendedNFTA< SymbolType, StateType >::removeTransition	(	const rte::FormalRTEStructure< ext::variant< SymbolType, StateType > > &	rte,
		const ext::vector< StateType > &	prevStates,
		const StateType &	next
	)

Removes a transition from the automaton.

The transition is in a form ( A, B, C, ... ) \times a -> X, where A, B, C, ..., X \in Q and a \in T

Parameters

children	the source states (A, B, C, ...)
current	the input symbol (a)
next	the target state (B)

Returns: true if the transition was indeed removed

Here is the call graph for this function:

◆ setFinalStates()

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

void automaton::ExtendedNFTA< SymbolType, StateType >::setFinalStates ( ext::set< StateType > states )

inline

Setter of final states.

Parameters

states completely new set of final states

◆ setInputAlphabet()

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

void automaton::ExtendedNFTA< SymbolType, StateType >::setInputAlphabet ( ext::set< common::ranked_symbol< SymbolType > > symbols )

inline

Setter of input alphabet.

Parameters

symbols completely new input alphabet

◆ setStates()

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

void automaton::ExtendedNFTA< SymbolType, StateType >::setStates ( ext::set< StateType > states )

inline

Setter of states.

Parameters

states completely new set of states

◆ transitionsSize()

template<class SymbolType , class StateType >

unsigned automaton::ExtendedNFTA< SymbolType, StateType >::transitionsSize

Computes number of transitions in the automaton.

Returns: number of transitions in the automaton

Friends And Related Function Documentation

◆ operator<<

template<class SymbolType = DefaultSymbolType, class StateType = DefaultStateType>

ext::ostream & operator<<	(	ext::ostream &	out,
		const ExtendedNFTA< SymbolType, StateType > &	instance
	)

friend

Print this object as raw representation to ostream.

Parameters

out	ostream where to print
instance	object to print

Returns: modified output stream

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

alib2data/src/automaton/TA/ExtendedNFTA.h

Public Member Functions

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ ExtendedNFTA() [1/4]

◆ ExtendedNFTA() [2/4]

◆ ExtendedNFTA() [3/4]

◆ ExtendedNFTA() [4/4]

Member Function Documentation

◆ addFinalState()

◆ addInputSymbol()

◆ addInputSymbols()

◆ addState()

◆ addTransition()

◆ addTransitions()

◆ getFinalStates() [1/2]

◆ getFinalStates() [2/2]

◆ getInputAlphabet() [1/2]

◆ getInputAlphabet() [2/2]

◆ getStates() [1/2]

◆ getStates() [2/2]

◆ getTransitions() [1/2]

◆ getTransitions() [2/2]

◆ getTransitionsFromState()

◆ getTransitionsToState()

◆ isDeterministic()

◆ operator<=>()

◆ operator==()

◆ removeFinalState()

◆ removeInputSymbol()

◆ removeState()

◆ removeTransition()

◆ setFinalStates()

◆ setInputAlphabet()

◆ setStates()

◆ transitionsSize()

Friends And Related Function Documentation

◆ operator<<