automaton::simplify::UselessStatesRemover Class Reference

#include <UselessStatesRemover.h>

Static Public Member Functions
template<class T >
static T	remove (const T &fsm)
template<class SymbolType , class StateType >
static automaton::MultiInitialStateNFA< SymbolType, StateType >	remove (const automaton::MultiInitialStateNFA< SymbolType, StateType > &fsm)
template<class SymbolType , class StateType >
static automaton::DFTA< SymbolType, StateType >	remove (const automaton::DFTA< SymbolType, StateType > &fta)
template<class SymbolType , class StateType >
static automaton::NFTA< SymbolType, StateType >	remove (const automaton::NFTA< SymbolType, StateType > &fta)
template<class SymbolType , class StateType >
static automaton::ArcFactoredNondeterministicZAutomaton< SymbolType, StateType >	remove (const automaton::ArcFactoredNondeterministicZAutomaton< SymbolType, StateType > &afza)
template<class SymbolType , class StateType >
static automaton::ArcFactoredDeterministicZAutomaton< SymbolType, StateType >	remove (const automaton::ArcFactoredDeterministicZAutomaton< SymbolType, StateType > &afza)

Detailed Description

Algorithm for the removal of useless states from a finite automaton and a deterministic finite tree automaton. A state q is called useless if there is no path from q to any final state.

For a finite automaton, we implement Melichar: Jazyky a překlady, 2.32. For a deterministic finite tree automaton, we implement ???

See also

automaton::simplify::Trim

automaton::simplify::UnreachableStatesRemover

Member Function Documentation

remove() [1/6]

template<class SymbolType , class StateType >

automaton::ArcFactoredDeterministicZAutomaton< SymbolType, StateType > automaton::simplify::UselessStatesRemover::remove ( const automaton::ArcFactoredDeterministicZAutomaton< SymbolType, StateType > &  afza )

static

Here is the call graph for this function:

remove() [2/6]

template<class SymbolType , class StateType >

automaton::ArcFactoredNondeterministicZAutomaton< SymbolType, StateType > automaton::simplify::UselessStatesRemover::remove ( const automaton::ArcFactoredNondeterministicZAutomaton< SymbolType, StateType > &  afza )

static

Removes unreachable states from a deterministic arc-factored z-automaton

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

Template Parameters

SymbolType	Type for input symbols.
StateType	Type for states.

Parameters

afdza

automaton to trim

Returns

afdza without unreachable states

Here is the call graph for this function:

remove() [3/6]

template<class SymbolType , class StateType >

automaton::DFTA< SymbolType, StateType > automaton::simplify::UselessStatesRemover::remove ( const automaton::DFTA< SymbolType, StateType > &  fta )

static

Removes unreachable states from a deterministic finite tree automaton.

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

Template Parameters

SymbolType	Type for input symbols.
RankType	Type for rank (arity) in ranked alphabet.
StateType	Type for states.

Parameters

dfta	automaton to trim

Returns

autoamton without unreachable states

Here is the call graph for this function:

remove() [4/6]

template<class SymbolType , class StateType >

automaton::MultiInitialStateNFA< SymbolType, StateType > automaton::simplify::UselessStatesRemover::remove ( const automaton::MultiInitialStateNFA< SymbolType, StateType > &  fsm )

static

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

Template Parameters

SymbolType	Type for input symbols.
StateType	Type for states.

Here is the call graph for this function:

remove() [5/6]

template<class SymbolType , class StateType >

automaton::NFTA< SymbolType, StateType > automaton::simplify::UselessStatesRemover::remove ( const automaton::NFTA< SymbolType, StateType > &  fta )

static

Removes unreachable states from a deterministic finite tree automaton.

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

Template Parameters

SymbolType	Type for input symbols.
RankType	Type for rank (arity) in ranked alphabet.
StateType	Type for states.

Parameters

dfta	automaton to trim

Returns

autoamton without unreachable states

Here is the call graph for this function:

remove() [6/6]

template<class T >

T automaton::simplify::UselessStatesRemover::remove ( const T &  fsm )

static

Removes useless states from an automaton.

Template Parameters

T	type of a finite automaton

Parameters

automaton

automaton to trim

Returns

automaton without useless states

Here is the call graph for this function:

Here is the caller graph for this function:

---

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

• alib2algo/src/automaton/simplify/UselessStatesRemover.h