Generated on for Gecode by doxygen 1.17.0

Finite automaton with deterministic construction by default. More...

#include <gecode/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.

Static Public Member Functions

static DFA nfa (int s, Transition t[], int f[])
 Construct a nondeterministic finite automaton.
static DFA nfa (int s, std::initializer_list< Transition > t, std::initializer_list< int > f)
 Construct a nondeterministic finite automaton from lists.

(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

Finite automaton with deterministic construction by default.

The constructors and init() require deterministic transitions. Use nfa() to retain nondeterministic transitions without determinization or minimization. Every transition consumes one symbol; epsilon transitions are not supported.

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 2620 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 518 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 522 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 162 of file dfa.cpp.

◆ nfa() [1/2]

DFA Gecode::DFA::nfa ( int s,
Transition t[],
int f[] )
static

Construct a nondeterministic finite automaton.

Start state is s. The last transition in t must have -1 as its input state, and the last final state in f must be -1. Multiple transitions may share an input state and symbol. Every transition consumes one symbol; epsilon transitions are not supported. Unreachable states are removed, but the automaton is neither determinized nor minimized.

Definition at line 545 of file dfa.cpp.

◆ nfa() [2/2]

DFA Gecode::DFA::nfa ( int s,
std::initializer_list< Transition > t,
std::initializer_list< int > f )
static

Construct a nondeterministic finite automaton from lists.

Start state is s, transitions are t, and final states are f. No sentinel elements are needed. As for the array overload, nondeterminism is retained and epsilon transitions are not supported.

Definition at line 550 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.

◆ 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: