Archon::Utilities::DFA Class Reference

Deterministic finite state automata (DFA). More...

#include <archon/util/dfa.H>

Collaboration diagram for Archon::Utilities::DFA:

[legend]List of all members.

Public Member Functions
	DFA (const NFA &, vector< set< int > > *stateSets=0, AnchorInfo *anchorInfo=0)
	Construct a DFA that accepts exactly the same language as the NFA passed as argument.
	DFA (Minimize)
	Construct the DFA with the minimal number of states that accepts exactly the same language as the DFA passed as argument.
int	getNumberOfStates () const
const State &	getState (int i) const
string	print (const Printer &printer=getDefaultPrinter(), int width=0) const
Static Public Member Functions
static const Printer &	getDefaultPrinter ()
Classes
struct	AnchorInfo
class	Edge
struct	Minimize
struct	Printer
class	State

---

Detailed Description

Deterministic finite state automata (DFA).

As an extension to a standard DFA, this one may have more than one start state.

Definition at line 45 of file dfa.H.

---

Constructor & Destructor Documentation

Archon::Utilities::DFA::DFA (  const NFA &  , vector< set< int > > *  stateSets = 0, AnchorInfo *  anchorInfo = 0 )

Construct a DFA that accepts exactly the same language as the NFA passed as argument. The resulting DFA will never have more start states than the NFA and if the NFA has at least one start state then so has the DFA. In particular, if the NFA has one start state then the DFA gets one start state. The start states will always be the first states in the DFA. Parameters: stateSets  If not 0 record the state sets that result from the subset construction in 'stateSets'. The first DFA state corresponds to the first set in 'stateSets' and so on. anchorInfo  If not 0 a user defined range of symbols have a special meaning within both automata. Todo: Explain further. Definition at line 288 of file dfa.C. References Archon::Utilities::NFA::constructDFA(), and Archon::Utilities::NFA::states.

Archon::Utilities::DFA::DFA (  Minimize   )

Construct the DFA with the minimal number of states that accepts exactly the same language as the DFA passed as argument. The new DFA will never have more start states than the old one and if the old one has at least one start state then so has the new. In particular, if the old DFA has one start state then the new DFA gets one start state. The start states will always be the first states in the new DFA. Definition at line 295 of file dfa.C. References Archon::Utilities::DFA::Minimize::a, and minimize().

---

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

• archon/util/dfa.H
• archon/util/dfa.C

---