Gecode::DFA Class Reference
Functionality by programming task » Programming models » Using integer variables and constraints » Extensional constraints

Deterministic finite automaton (DFA). More...

`#include <int.hh>`

## Classes

class | Transition
| Specification of a DFA transition. More...
class | Transitions
| Iterator for DFA transitions (sorted by symbols). More...
class | Symbols
| Iterator for DFA symbols. More...
class | DFAI
| Data stored for a DFA. More...

## Public Member Functions

void | init (int s, Transition t[], int f[], bool minimize=true)
| Initialize DFA.
| DFA (void)
| Initialize for DFA accepting the empty word.
| DFA (int s, Transition t[], int f[], bool minimize=true)
| Initialize DFA.
| DFA (int s, std::initializer_list< Transition > t, std::initializer_list< int > f, bool minimize=true)
| Initialize DFA.
| DFA (const DFA &d)
| Initialize by DFA d (DFA is shared).
bool | operator== (const DFA &d) const
| Test whether DFA is equal to d.
bool | operator!= (const DFA &d) const
| Test whether DFA is not equal to d.
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.
std::size_t | hash (void) const
| Return hash key.
Public Member Functions inherited from Gecode::SharedHandle
| SharedHandle (void)
| Create shared handle with no object pointing to.
| SharedHandle (SharedHandle::Object *so)
| Create shared handle that points to shared object so.
| SharedHandle (const SharedHandle &sh)
| Copy constructor maintaining reference count.
SharedHandle & | operator= (const SharedHandle &sh)
| Assignment operator maintaining reference count.
| ~SharedHandle (void)
| Destructor that maintains reference count.
| operator bool (void) const
| Whether handle points to an object.

## Related Symbols

(Note that these are not member symbols.)
template<class Char, class Traits>
std::basic_ostream< Char, Traits > & | operator<< (std::basic_ostream< Char, Traits > &os, const DFA &d)

## Additional Inherited Members

Protected Member Functions inherited from Gecode::SharedHandle
SharedHandle::Object * | object (void) const
| Access to the shared object.
void | object (SharedHandle::Object *n)
| Modify shared object.

## 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 2049 of file int.hh.

## Constructor & Destructor Documentation

## DFA() [1/4]

Gecode::DFA::DFA | ( | void |  | ) |

inline

Initialize for DFA accepting the empty word.

Definition at line 131 of file dfa.hpp.

## DFA() [2/4]

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 474 of file dfa.cpp.

## DFA() [3/4]

Gecode::DFA::DFA | ( | int | s,
|  | std::initializer_list< Transition > | t,
|  | std::initializer_list< int > | f,
|  | bool | minimize = true )

Initialize DFA.

- Start state is given by s.
- Transitions are described by t.
- Final states are given by f.
- Minimizes the DFA, if minimize is true.
- Note that the transitions must be deterministic.

Definition at line 478 of file dfa.cpp.

## DFA() [4/4]

Gecode::DFA::DFA | ( | const DFA & | d | ) |

inline

Initialize by DFA d (DFA is shared).

Definition at line 135 of file dfa.hpp.

## Member Function Documentation

## init()

void Gecode::DFA::init | ( | 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 152 of file dfa.cpp.

## operator==()

bool Gecode::DFA::operator== | ( | const DFA & | d | ) | const

inline

Test whether DFA is equal to d.

Definition at line 330 of file dfa.hpp.

## operator!=()

bool Gecode::DFA::operator!= | ( | const DFA & | d | ) | const

inline

Test whether DFA is not equal to d.

Definition at line 347 of file dfa.hpp.

## n_states()

int Gecode::DFA::n_states | ( | void |  | ) | const

inline

Return the number of states.

Definition at line 139 of file dfa.hpp.

## n_transitions()

int Gecode::DFA::n_transitions | ( | void |  | ) | const

inline

Return the number of transitions.

Definition at line 151 of file dfa.hpp.

## n_symbols()

unsigned int Gecode::DFA::n_symbols | ( | void |  | ) | const

inline

Return the number of symbols.

Definition at line 145 of file dfa.hpp.

## max_degree()

unsigned int Gecode::DFA::max_degree | ( | void |  | ) | const

inline

Return maximal degree (in-degree and out-degree) of any state.

Definition at line 157 of file dfa.hpp.

## final_fst()

int Gecode::DFA::final_fst | ( | void |  | ) | const

inline

Return the number of the first final state.

Definition at line 163 of file dfa.hpp.

## final_lst()

int Gecode::DFA::final_lst | ( | void |  | ) | const

inline

Return the number of the last final state.

Definition at line 169 of file dfa.hpp.

## symbol_min()

int Gecode::DFA::symbol_min | ( | void |  | ) | const

inline

Return smallest symbol in DFA.

Definition at line 175 of file dfa.hpp.

## symbol_max()

int Gecode::DFA::symbol_max | ( | void |  | ) | const

inline

Return largest symbol in DFA.

Definition at line 182 of file dfa.hpp.

## hash()

std::size_t Gecode::DFA::hash | ( | void |  | ) | const

inline

Return hash key.

Definition at line 189 of file dfa.hpp.

## Friends And Related Symbol Documentation

## operator<<()

template<class Char, class Traits>

std::basic_ostream< Char, Traits > & operator<< | ( | std::basic_ostream< Char, Traits > & | os,
|  | const DFA & | d )

related

Print DFA d

Definition at line 293 of file dfa.hpp.

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

- gecode/int.hh
- gecode/int/extensional/dfa.cpp
- gecode/int/extensional/dfa.hpp