automaton::properties::EpsilonClosure Class Reference

#include <EpsilonClosure.h>

Static Public Member Functions
template<class SymbolType , class StateType >
static ext::set< StateType >	epsilonClosure (const automaton::EpsilonNFA< SymbolType, StateType > &fsm, const StateType &q)
template<class SymbolType , class StateType >
static ext::set< StateType >	epsilonClosure (const automaton::EpsilonNFTA< SymbolType, StateType > &fta, const StateType &q)
template<class T > requires isDFA < T > || isNFA < T > || isMultiInitialStateNFA < T >
static ext::set< typename T::StateType >	epsilonClosure (const T &fsm, const typename T::StateType &q)
template<class SymbolType , class StateType >
static ext::set< StateType >	epsilonClosure (const automaton::ExtendedNFA< SymbolType, StateType > &fsm, const StateType &q)
template<class SymbolType , class StateType >
static ext::set< StateType >	epsilonClosure (const automaton::CompactNFA< SymbolType, StateType > &fsm, const StateType &q)

Detailed Description

Algorithm computing an epsilon closure of a single state in a finite automaton.

Member Function Documentation

epsilonClosure() [1/5]

template<class SymbolType , class StateType >

ext::set< StateType > automaton::properties::EpsilonClosure::epsilonClosure ( const automaton::CompactNFA< SymbolType, StateType > &  fsm, const StateType &  q  )

static

Computes epsilon closure for a state of an compact nondeterministic finite automaton. Any string of size 0 is considered as epsilon.

Template Parameters

SymbolType	Type for the input symbols.
StateType	Type for the states.

Parameters

fsm	compact nondeterministic finite automaton
state	state for which we want to compute the closure

Returns

set of states representing the epsilon closures of a state of fsm

Exceptions

exception::CommonException

if state is not in the set of fsm states

Here is the call graph for this function:

epsilonClosure() [2/5]

template<class SymbolType , class StateType >

ext::set< StateType > automaton::properties::EpsilonClosure::epsilonClosure ( const automaton::EpsilonNFA< SymbolType, StateType > &  fsm, const StateType &  q  )

static

Computes epsilon closure for a state of a nondeterministic finite automaton with epsilon transitions. Implemented using breadth-first search.

Template Parameters

SymbolType	Type for the input symbols.
StateType	Type for the states.

Parameters

fsm	nondeterministic finite automaton with epsilon transitions
state	state for which we want to compute the closure

Returns

set of states representing the epsilon closures of a state of fsm

Exceptions

exception::CommonException

if state is not in the set of fsm states

Here is the call graph for this function:

Here is the caller graph for this function:

epsilonClosure() [3/5]

template<class SymbolType , class StateType >

ext::set< StateType > automaton::properties::EpsilonClosure::epsilonClosure ( const automaton::EpsilonNFTA< SymbolType, StateType > &  fta, const StateType &  q  )

static

Computes epsilon closure for a state of a nondeterministic finite tree automaton with epsilon transitions. Implemented using breadth-first search.

Template Parameters

SymbolType	Type for the input symbols.
StateType	Type for the states.

Parameters

fsm	nondeterministic finite tree automaton with epsilon transitions
state	state for which we want to compute the closure

Returns

set of states representing the epsilon closures of a state of fsm

Exceptions

exception::CommonException

if state is not in the set of fsm states

Here is the call graph for this function:

epsilonClosure() [4/5]

template<class SymbolType , class StateType >

ext::set< StateType > automaton::properties::EpsilonClosure::epsilonClosure ( const automaton::ExtendedNFA< SymbolType, StateType > &  fsm, const StateType &  q  )

static

Computes epsilon closure for a state of an extended nondeterministic finite automaton. Any regexp that can denote epsilon word is considered as an epsilon transition for the purpose of this algorithm.

Template Parameters

SymbolType	Type for the input symbols.
StateType	Type for the states.

Parameters

fsm	extended nondeterministic finite automaton
state	state for which we want to compute the closure

Returns

set of states representing the epsilon closures of a state of fsm

Exceptions

exception::CommonException

if state is not in the set of fsm states

Here is the call graph for this function:

epsilonClosure() [5/5]

template<class T >
requires isDFA < T > || isNFA < T > || isMultiInitialStateNFA < T >

static ext::set< typename T::StateType > automaton::properties::EpsilonClosure::epsilonClosure ( const T &  fsm, const typename T::StateType &  q  )

static

Computes epsilon closure for given states of a nondeterministic finite automaton with multiple initial states. Epsilon closure of a state q of an automaton without epsilon transitions is eps-closure(q) = {q}.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Template Parameters

T	type of tested automaton.

Parameters

fsm	(nondeterministic) finite automaton (with multiple initial states)
state	state for which we want to compute the closure

Returns

mapping of states to set of states representing the epsilon closures for each state of fsm

---

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

• alib2algo/src/automaton/properties/EpsilonClosure.h