automaton::simplify::Normalize Class Reference

#include <Normalize.h>

Static Public Member Functions
template<class SymbolType , class StateType >
static automaton::DFA< SymbolType, unsigned >	normalize (const automaton::DFA< SymbolType, StateType > &fsm)
template<class SymbolType , class StateType >
static automaton::CompactDFA< SymbolType, unsigned >	normalize (const automaton::CompactDFA< SymbolType, StateType > &fsm)
template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >
static automaton::RealTimeHeightDeterministicDPDA< InputSymbolType, unsigned, unsigned >	normalize (const automaton::RealTimeHeightDeterministicDPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &pda)
template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >
static automaton::DPDA< InputSymbolType, unsigned, unsigned >	normalize (const automaton::DPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &pda)
template<class SymbolType , class StateType >
static automaton::DFTA< SymbolType, unsigned >	normalize (const automaton::DFTA< SymbolType, StateType > &fta)

Detailed Description

Normalization of an automaton. Basically, we rename the automaton's properties (states, pushdown symbols, ...) in such fashion, that the naming is same for isomorphic automata.

Unlike Rename, we can normalize only deterministic automata.

See also

automaton::simplify::Rename

Member Function Documentation

normalize() [1/5]

template<class SymbolType , class StateType >

automaton::CompactDFA< SymbolType, unsigned > automaton::simplify::Normalize::normalize ( const automaton::CompactDFA< SymbolType, StateType > &  fsm )

static

Normalization of compact deterministic finite automata. The process of normalization is a BFS traversal through the graph representing the automaton. The states are named by integers in the visited order.

Template Parameters

SymbolType	Type for input symbols.
StateType	Type for states.

Parameters

dfa	compact determinsitic finite automaton to normalize

Returns

compact dfa with state labels normalized

Exceptions

exception::CommonException

if the passed dfa was not minimal connected dfa

Here is the call graph for this function:

normalize() [2/5]

template<class SymbolType , class StateType >

automaton::DFA< SymbolType, unsigned > automaton::simplify::Normalize::normalize ( const automaton::DFA< SymbolType, StateType > &  fsm )

static

Normalization of deterministic finite automata. The process of normalization is a BFS traversal through the graph representing the automaton. The states are named by integers in the visited order.

Template Parameters

SymbolType	Type for input symbols.
StateType	Type for states.

Parameters

dfa	determinsitic finite automaton to normalize

Returns

dfa with state labels normalized

Exceptions

exception::CommonException

if the passed dfa was not minimal connected dfa

Here is the call graph for this function:

normalize() [3/5]

template<class SymbolType , class StateType >

automaton::DFTA< SymbolType, unsigned > automaton::simplify::Normalize::normalize ( const automaton::DFTA< SymbolType, StateType > &  fta )

static

Normalization of deterministic finite tree automata. The process of normalization is a BFS traversal through the graph representing the automaton. The states are named by integers in the visited order.

Template Parameters

SymbolType	Type for input symbols.
RankType	Type for input symbols rank.
StateType	Type for states.

Parameters

dfa	determinsitic finite tree automaton to normalize

Returns

fta with state labels normalized

Exceptions

exception::CommonException

if the passed dfa was not minimal dfta

Here is the call graph for this function:

normalize() [4/5]

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >

automaton::DPDA< InputSymbolType, unsigned, unsigned > automaton::simplify::Normalize::normalize ( const automaton::DPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &  pda )

static

Normalization of deterministic pushdown automata. The process of normalization of states is a BFS traversal through the graph representing the automaton. The states are named by integers in the visited order. We normalize also the pushdown store symbols.

Template Parameters

InputSymbolType	Type for input symbols.
PushdownStoreSymbolType	Type for pushdown store symbols.
StateType	Type for states.

Parameters

dpda	determinsitic pushdown automaton to normalize

Returns

dpda with state labels normalized

Exceptions

exception::CommonException

if the passed dpda was not deterministic connected pda

Here is the call graph for this function:

normalize() [5/5]

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >

automaton::RealTimeHeightDeterministicDPDA< InputSymbolType, unsigned, unsigned > automaton::simplify::Normalize::normalize ( const automaton::RealTimeHeightDeterministicDPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &  pda )

static

Normalization of deterministic pushdown automata. The process of normalization of states is a BFS traversal through the graph representing the automaton. The states are named by integers in the visited order. We normalize also the pushdown store symbols.

Template Parameters

InputSymbolType	Type for input symbols.
PushdownStoreSymbolType	Type for pushdown store symbols.
StateType	Type for states.

Parameters

pda	determinsitic pushdown automaton to normalize

Returns

pda with state labels normalized

Exceptions

exception::CommonException

if the passed dpda was not deterministic connected pda

Here is the call graph for this function:

---

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

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