Deterministic finite automaton (DFA).
More...
#include <int.hh>
List of all members.
Classes |
| class | DFAI |
| | Data stored for a DFA. More...
|
| class | Symbols |
| | Iterator for DFA symbols. More...
|
| class | Transition |
| | Specification of a DFA transition. More...
|
| class | Transitions |
| | Iterator for DFA transitions (sorted by symbols). More...
|
Public Member Functions |
| | DFA (void) |
| | Initialize for DFA accepting the empty word.
|
| | DFA (int s, Transition t[], int f[], bool minimize=true) |
| | Initialize DFA.
|
| | DFA (const DFA &d) |
| | Initialize by DFA d (DFA is shared).
|
| int | n_states (void) const |
| | Return the number of states.
|
| int | n_transitions (void) const |
| | Return the number of transitions.
|
| unsigned int | n_symbols (void) const |
| | Return the number of symbols.
|
| unsigned int | max_degree (void) const |
| | Return maximal degree (in-degree and out-degree) of any state.
|
| int | final_fst (void) const |
| | Return the number of the first final state.
|
| int | final_lst (void) const |
| | Return the number of the last final state.
|
| int | symbol_min (void) const |
| | Return smallest symbol in DFA.
|
| int | symbol_max (void) const |
| | Return largest symbol in DFA.
|
Related Functions |
(Note that these are not member functions.)
|
| template<class Char , class Traits > |
std::basic_ostream< Char,
Traits > & | operator<< (std::basic_ostream< Char, Traits > &os, const DFA &d) |
Detailed Description
Deterministic finite automaton (DFA).
After initialization, the start state is always zero. The final states are contiguous ranging from the first to the last final state.
Definition at line 2034 of file int.hh.
Constructor & Destructor Documentation
| Gecode::DFA::DFA |
( |
void |
|
) |
[inline] |
Initialize for DFA accepting the empty word.
Definition at line 97 of file dfa.hpp.
| Gecode::DFA::DFA |
( |
int |
s, |
|
|
Transition |
t[], |
|
|
int |
f[], |
|
|
bool |
minimize = true | |
|
) |
| | |
Initialize DFA.
- Start state is given by s.
- Transitions are described by t, where the last element must have -1 as value for
i_state.
- Final states are given by f, where the last final element must be -1.
- Minimizes the DFA, if minimize is true.
- Note that the transitions must be deterministic.
Definition at line 155 of file dfa.cpp.
| Gecode::DFA::DFA |
( |
const DFA & |
d |
) |
[inline] |
Member Function Documentation
| int Gecode::DFA::n_states |
( |
void |
|
) |
const [inline] |
Return the number of states.
Definition at line 105 of file dfa.hpp.
| int Gecode::DFA::n_transitions |
( |
void |
|
) |
const [inline] |
Return the number of transitions.
Definition at line 117 of file dfa.hpp.
| unsigned int Gecode::DFA::n_symbols |
( |
void |
|
) |
const [inline] |
Return the number of symbols.
Definition at line 111 of file dfa.hpp.
| unsigned int Gecode::DFA::max_degree |
( |
void |
|
) |
const [inline] |
Return maximal degree (in-degree and out-degree) of any state.
Definition at line 123 of file dfa.hpp.
| int Gecode::DFA::final_fst |
( |
void |
|
) |
const [inline] |
Return the number of the first final state.
Definition at line 129 of file dfa.hpp.
| int Gecode::DFA::final_lst |
( |
void |
|
) |
const [inline] |
Return the number of the last final state.
Definition at line 135 of file dfa.hpp.
| int Gecode::DFA::symbol_min |
( |
void |
|
) |
const [inline] |
Return smallest symbol in DFA.
Definition at line 141 of file dfa.hpp.
| int Gecode::DFA::symbol_max |
( |
void |
|
) |
const [inline] |
Return largest symbol in DFA.
Definition at line 148 of file dfa.hpp.
Friends And Related Function Documentation
template<class Char , class Traits >
| std::basic_ostream< Char, Traits > & operator<< |
( |
std::basic_ostream< Char, Traits > & |
os, |
|
|
const DFA & |
d | |
|
) |
| | [related] |
The documentation for this class was generated from the following files:
