A Deterministic Finite Automaton. More...

#include <DFA.h>

Public Member Functions
	DFA (unsigned int initial, bool isAccepting=false)
	Constructs the DFA. More...

void	addState (unsigned int state, bool isAccepting=false)
	Adds a state to the DFA. More...

void	addTransition (unsigned int p, Sigma symbol, unsigned int q)
	Adds a transition to the DFA. More...

bool	isAccepted (const std::list< Sigma > &word)
	Tests whether the word is accepted by the DFA. More...

bool	isAccepted (const std::vector< Sigma > &word)
	Tests whether the word is accepted by the DFA. More...

unsigned int	getNumberOfStates () const
	Returns the number of states in this DFA. More...

std::string	to_dot () const
	Constructs a string that is the representation of the DFA in the DOT language. More...

template<typename T >
std::unique_ptr< DFA< T > >	convert (const std::map< Sigma, T > &conversionMap) const
	Creates a new DFA with exactly the same number of states and the same transitions but the type of the alphabet is changed. More...

bool	isAcceptingState (unsigned int state) const
	Tests whether the given state is a final (or accepting) state. More...

const std::unordered_set< unsigned int > &	getStates () const
	Returns the set of states in this DFA. More...

const std::unordered_set< unsigned int > &	getAcceptingStates () const
	Returns the set of accepting states of this DFA. More...

unsigned int	getInitialState () const
	Returns the initial state of this DFA. More...

const std::map< unsigned int, std::map< Sigma, unsigned int > >	getTransitions () const
	Returns the function delta. More...

bool	isState (unsigned int state) const
	Checks if the given state number is in the states set. More...

Detailed Description

template<typename Sigma>
class gsjj::DFA< Sigma >

A Deterministic Finite Automaton.

A DFA is encoded by a 5-tuple $(Q, \Sigma, q_0, \delta, F)$ with:

, the set of states. Here, a state is represented by an integer (starting from 0)
$\Sigma$ , the alphabet. Here, the alphabet is all the values that can be coded in a given C++ type (for example, a char)
, the initial state
$\delta$ , the transition function such that delta: $Q \times Sigma \rightarrow Q: \delta(q, a) = p$
, the set of final/accepting states

We make the assumption that $Q$ cannot be empty (because there must be at least the initial state).

Template Parameters

Sigma The type of the alphabet (for example, char).

Definition at line 39 of file DFA.h.

Constructor & Destructor Documentation

◆ DFA()

template<typename Sigma >

gsjj::DFA< Sigma >::DFA	(	unsigned int	initial,
		bool	isAccepting = `false`
	)

inline

Constructs the DFA.

Parameters

initial	The initial state
isAccepting	Whether the initial state is accepting or not

Definition at line 47 of file DFA.h.

Member Function Documentation

◆ addState()

template<typename Sigma >

void gsjj::DFA< Sigma >::addState	(	unsigned int	state,
		bool	isAccepting = `false`
	)

inline

Adds a state to the DFA.

The functions checks that the state does not yet exist.

Parameters

state	The number of the state.
isAccepting	Whether the new state is accepting or not

Definition at line 62 of file DFA.h.

◆ addTransition()

template<typename Sigma >

void gsjj::DFA< Sigma >::addTransition	(	unsigned int	p,
		Sigma	symbol,
		unsigned int	q
	)

inline

Adds a transition to the DFA.

If the DFA is in the state p and reads the given symbol, it goes to the state q. The function checks that delta(p, symbol) does not yet exist and that p and q exist.

Parameters

p	The state where the transition starts
symbol	The symbol to read to activate the transition
q	The state where the transition ends

Definition at line 79 of file DFA.h.

◆ convert()

template<typename Sigma >

template<typename T >

std::unique_ptr<DFA<T> > gsjj::DFA< Sigma >::convert ( const std::map< Sigma, T > & conversionMap ) const

inline

Creates a new DFA with exactly the same number of states and the same transitions but the type of the alphabet is changed.

Parameters

conversionMap A map giving the conversion between the current alphabet and the target alphabet

Returns: A DFA for which the alphabet is of type T

Template Parameters

T	The type of the DFA to create

Definition at line 170 of file DFA.h.

◆ getAcceptingStates()

template<typename Sigma >

const std::unordered_set<unsigned int>& gsjj::DFA< Sigma >::getAcceptingStates ( ) const

inline

Returns the set of accepting states of this DFA.

Note that every state in this set is also in getStates, of course

Returns: The accepting states

Definition at line 214 of file DFA.h.

◆ getInitialState()

template<typename Sigma >

unsigned int gsjj::DFA< Sigma >::getInitialState ( ) const

inline

Returns the initial state of this DFA.

The initial state is of course present in getStates

Returns: The initial state

Definition at line 224 of file DFA.h.

◆ getNumberOfStates()

template<typename Sigma >

unsigned int gsjj::DFA< Sigma >::getNumberOfStates ( ) const

inline

Returns the number of states in this DFA.

Returns: The number of states

Definition at line 144 of file DFA.h.

◆ getStates()

template<typename Sigma >

const std::unordered_set<unsigned int>& gsjj::DFA< Sigma >::getStates ( ) const

inline

Returns the set of states in this DFA.

Returns: The states

Definition at line 204 of file DFA.h.

◆ getTransitions()

template<typename Sigma >

const std::map<unsigned int, std::map<Sigma, unsigned int> > gsjj::DFA< Sigma >::getTransitions ( ) const

inline

Returns the function delta.

The map associates the state to a map. This map associates a symbol a to a state q.

Definition at line 233 of file DFA.h.

◆ isAccepted() [1/2]

template<typename Sigma >

bool gsjj::DFA< Sigma >::isAccepted ( const std::list< Sigma > & word )

inline

Tests whether the word is accepted by the DFA.

Parameters

word	The word to test

Returns: True iff the word is accepted by the DFA

Definition at line 99 of file DFA.h.

◆ isAccepted() [2/2]

template<typename Sigma >

bool gsjj::DFA< Sigma >::isAccepted ( const std::vector< Sigma > & word )

inline

Tests whether the word is accepted by the DFA.

Parameters

word	The word to test

Returns: True iff the word is accepted by the DFA

Definition at line 124 of file DFA.h.

◆ isAcceptingState()

template<typename Sigma >

bool gsjj::DFA< Sigma >::isAcceptingState ( unsigned int state ) const

inline

Tests whether the given state is a final (or accepting) state.

Parameters

state The state to test

Returns: True iff state is accepting

Definition at line 196 of file DFA.h.

◆ isState()

template<typename Sigma >

bool gsjj::DFA< Sigma >::isState ( unsigned int state ) const

inline

Checks if the given state number is in the states set.

Parameters

state The state to check

Returns: True iff state is in the DFA

Definition at line 242 of file DFA.h.

◆ to_dot()

template<typename Sigma >

std::string gsjj::DFA< Sigma >::to_dot ( ) const

inline

Constructs a string that is the representation of the DFA in the DOT language.

Returns: The string

Definition at line 152 of file DFA.h.

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

include/gsjj/DFA.h

Public Member Functions

Detailed Description

template<typename Sigma> class gsjj::DFA< Sigma >

Constructor & Destructor Documentation

◆ DFA()

Member Function Documentation

◆ addState()

◆ addTransition()

◆ convert()

◆ getAcceptingStates()

◆ getInitialState()

◆ getNumberOfStates()

◆ getStates()

◆ getTransitions()

◆ isAccepted() [1/2]

◆ isAccepted() [2/2]

◆ isAcceptingState()

◆ isState()

◆ to_dot()

template<typename Sigma>
class gsjj::DFA< Sigma >