Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
|
Deterministic finite automaton. Accepts regular languages. More...
#include <DFA.h>
Public Types | |
typedef SymbolTypeT | SymbolType |
typedef StateTypeT | StateType |
Friends | |
ext::ostream & | operator<< (ext::ostream &out, const DFA &instance) |
Additional Inherited Members | |
![]() | |
static void | registerComponent () |
static void | unregisterComponent () |
Deterministic 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 -> B, where A, B \in Q and a \in T, F (FinalStates) = set of final states
Note that target state of a transition is required. This class is used to store minimal, total, ... variants of deterministic finite automata.
SymbolTypeT | used for the terminal alphabet |
StateTypeT | used to the states, and the initial state of the automaton. |
typedef StateTypeT automaton::DFA< SymbolTypeT, StateTypeT >::StateType |
typedef SymbolTypeT automaton::DFA< SymbolTypeT, StateTypeT >::SymbolType |
|
explicit |
Creates a new instance of the automaton with a concrete initial state.
initialState | the initial state of the automaton |
|
explicit |
Creates a new instance of the automaton with a concrete set of states, input alphabet, initial state, and a set of final states.
states | the initial set of states of the automaton |
inputAlphabet | the initial input alphabet |
initialState | the initial state of the automaton |
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::DFA< 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
current | the source state (A) |
input | 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 initial state.
|
inline |
Getter of the initial state.
|
inline |
Getter of the input alphabet.
|
inline |
Getter of the input alphabet.
|
inline |
Getter of states.
|
inline |
Getter of states.
ext::map< ext::pair< StateType, SymbolType >, StateType > && automaton::DFA< SymbolType, StateType >::getTransitions | ( | ) | && |
Get the transition function of the automaton in its natural form.
const ext::map< ext::pair< StateType, SymbolType >, StateType > & automaton::DFA< SymbolType, StateType >::getTransitions | ( | ) | const & |
Get the transition function of the automaton in its natural form.
ext::iterator_range< typename ext::map< ext::pair< StateType, SymbolType >, StateType >::const_iterator > automaton::DFA< SymbolType, StateType >::getTransitionsFromState | ( | const StateType & | from | ) | const |
Get a subset of the transition function of the automaton, with the source state fixed as a view to the internal representation.
from | filter the transition function based on this state as a source state |
ext::map< ext::pair< StateType, SymbolType >, StateType > automaton::DFA< SymbolType, StateType >::getTransitionsToState | ( | const StateType & | to | ) | const |
Get the transition function of the automaton, with the target state fixed in the transitions natural representation.
to | filter the transition function based on this state as a source state |
bool automaton::DFA< SymbolType, StateType >::isTotal |
Determines whether the automaton is total.
The automaton is total if and only if:
size
of transition function \forall states \times input symbols = 1
|
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::DFA< 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
current | the source state (A) |
input | the input symbol (a) |
next | the target state (B) |
|
inline |
Setter of final states.
states | completely new set of final states |
|
inline |
Setter of the initial state.
state | new initial state of the automaton |
|
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 |