Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
|
Nondeterministic Z-Automaton. Computation model for unranked regular tree languages. More...
#include <NondeterministicZAutomaton.h>
Public Types | |
typedef SymbolTypeT | SymbolType |
typedef StateTypeT | StateType |
Friends | |
ext::ostream & | operator<< (ext::ostream &out, const NondeterministicZAutomaton &instance) |
Additional Inherited Members | |
![]() | |
static void | registerComponent () |
static void | unregisterComponent () |
Nondeterministic Z-Automaton. Computation model for unranked regular tree languages.
Defined in Björklund, Drewes, Satta: Z-Automata for Compact and Direct Representation of Unranked Tree Languages https://doi.org/10.1007/978-3-030-23679-3_7
Nondeterministic Z-Automaton is a quadruple A = (\Sigma, Q, R, F), where \Sigma is an input alphabet; Q is the finite set of states, Q \cap T = \emptyset; R is the set of transition rules, each of the form s -> q, q \in Q, s is a tree over \Sigma \cup Q; F is a set of final states
SymbolTypeT | used for the symbols of the tree the automaton is executed on. |
StateTypeT | used for the states, and the initial state of the automaton. |
typedef StateTypeT automaton::NondeterministicZAutomaton< SymbolTypeT, StateTypeT >::StateType |
typedef SymbolTypeT automaton::NondeterministicZAutomaton< SymbolTypeT, StateTypeT >::SymbolType |
|
explicit |
Creates a new instance of the automaton.
|
explicit |
Creates a new instance of the automaton with a concrete set of states, input alphabet, and a set of final states.
states | the initial set of states of the automaton |
inputAlphabet | the initial input alphabet |
finalStates | the initial set of final states of the automaton |
|
inline |
Adder of a final state.
state | the new state to be added to a set of final states |
|
inline |
Adder of a input symbol.
symbol | the new symbol to be added to an input alphabet |
|
inline |
Adder of input symbols.
symbols | new symbols to be added to an input alphabet |
|
inline |
Adder of a state.
state | the new state to be added to a set of states |
bool automaton::NondeterministicZAutomaton< SymbolType, StateType >::addTransition | ( | ext::variant< SymbolType, StateType > | symbol, |
ext::vector< ext::variant< SymbolType, 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
children | the source states (A, B, C, ...) |
current | the input symbol (a) |
next | the target state (B) |
AutomatonException | when transition contains state or symbol not present in the automaton components |
|
inline |
Getter of final states.
|
inline |
Getter of final states.
|
inline |
Getter of the input alphabet.
|
inline |
Getter of the input alphabet.
|
inline |
Getter of states.
|
inline |
Getter of states.
|
inline |
Get the transition function of the automaton in its natural form.
|
inline |
Get the transition function of the automaton in its natural form.
|
inline |
q
|
inline |
q
|
inline |
The three way comparison implementation
other | the other instance |
other
.
|
inline |
The equality comparison implementation.
other | the other object to compare with. |
|
inline |
Remover of a final state.
state | a state to be removed from a set of final states |
|
inline |
Remover of an input symbol.
symbol | a symbol to be removed from an input alphabet |
|
inline |
Remover of a state.
state | a state to be removed from a set of states |
bool automaton::NondeterministicZAutomaton< SymbolType, StateType >::removeTransition | ( | const ext::variant< SymbolType, StateType > & | symbol, |
const ext::vector< ext::variant< SymbolType, StateType > > & | states, | ||
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
children | the source states (A, B, C, ...) |
current | the input symbol (a) |
next | the target state (B) |
|
inline |
Setter of final states.
states | completely new set of final states |
|
inline |
Setter of input alphabet.
symbols | completely new input alphabet |
|
inline |
Setter of states.
states | completely new set of states |
|
friend |
Print this object as raw representation to ostream.
out | ostream where to print |
instance | object to print |