Gecode::DFA Class Reference

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.

---

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]

Initialize by DFA d (DFA is shared)

Definition at line 101 of file dfa.hpp.

---

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]

Print DFA d

Definition at line 249 of file dfa.hpp.

---

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

• gecode/int.hh (Revision: 12537)
• gecode/int/extensional/dfa.cpp (Revision: 9773)
• gecode/int/extensional/dfa.hpp (Revision: 10684)