Automata need to inherit from this class and implement certain methods. More...

#include <automaton.h>

Public Member Functions
	automaton (bool collapse_epsilon=false, bool no_epsilon_produced=false)
	Constructor. More...

printer_base< State > *	int_state_printer () const
	Optionally Implement Returns a printer for states. More...

printer_base< Symbol > *	int_symbol_printer () const
	Optionally Implement Returns a printer for symbols. More...

bool	int_is_final_state (const State &state) const
	Implement This function determines if a specific state is final. More...

void	int_initial_states (State_vector &states) const
	Implement Returns the initial states. More...

void	int_successors (const State &state, const Symbol &sigma, State_vector &successors) const
	Implement Returns the successor for a specific state. More...

void	int_next_symbols (const State &state, Symbol_vector &symbols) const
	Implement Returns possible successor symbols for a state. More...

bool	int_is_epsilon (const Symbol &symbol) const
	Implement Determines if a symbol should be considered an epsilon transition. More...

bool	is_final_state (const State &state) const
	This function determines if a specific state is final. More...

void	initial_states (State_vector &states) const
	Returns the initial states. More...

void	initial_states (State_set &states) const
	Returns the initial states. More...

State_vector	initial_states () const
	Returns a set of initial states. More...

void	successors (const State &state, const Symbol &sigma, State_vector &successors1) const
	Returns the successor for a specific state. More...

State_set	successors (const State_set &states, const Symbol &sigma) const
	Finds successors for a set of states. More...

void	successors (const State_set &states, const Symbol &sigma, State_set &successors1) const
	Returns successors for a set of states. More...

State_vector	successors (const State &state, const Symbol &sigma) const
	Returns successors for a state. More...

void	next_symbols (const State &state, Symbol_vector &symbols) const
	Returns possible successor symbols for a state. More...

Symbol_vector	next_symbols (const State &state) const
	Returns possible successor symbols of a state. More...

void	next_symbols (const State &state, Symbol_set &symbols) const
	Returns possible successor symbols of a state. More...

const printer_base< State > &	state_printer () const
	Returns a printer for states. More...

const printer_base< Symbol > &	symbol_printer () const
	Returns a printer for symbols. More...

bool	is_epsilon (const Symbol &symbol) const
	Determines if a symbol should be considered an epsilon transition. More...

bool	is_final_state (const State_set &states) const
	Determines if one of the states is final. More...

Public Attributes
bool	collapse_epsilon
	If true during exploration of the next state the epsilons will be fully explored. If false then epsilon transitions may be returned.

bool	no_epsilon_produced
	Indicates that the implementation of next_symbols(const State&,Symbol_set&) const will never produce epsilon transitions.

Detailed Description

template<class State, class Symbol, class Implementation>
class Limi::automaton< State, Symbol, Implementation >

Automata need to inherit from this class and implement certain methods.

We use the curiously recurring template pattern (CRTP). This means that the custom automaton must inherit from this class and pass itself as the Implementation template argument. Furthermore none of the methods should be declared virtual (virtual function calls are too slow) and small functions should be declared inline if possible. Functions that need to be implemented by the deriving class start with int_ and are marked as Implement.

Template Parameters

State	The state class that the automaton will use.
Symbol	The symbol class.
Implementation	The deriving class must pass its own name here.

Constructor & Destructor Documentation

template<class State, class Symbol, class Implementation>

Limi::automaton< State, Symbol, Implementation >::automaton	(	bool	collapse_epsilon = `false`,
		bool	no_epsilon_produced = `false`
	)

inline

Constructor.

Parameters

collapse_epsilon	This class will automatically collapse epsilon transitions. That means that if the derived class returns a successor for a specific state, this class will query for all epsilon successors of that state recursively and include them all in the successor set. This is costly in terms of performance.
no_epsilon_produced	This should be set to false if the automaton is known not to generate epsilon transitions. It implies collapse_epsilon is set to false. This field is needed because Limi::antichain_algo::antichain_algo() will reject any automaton B where collapse_epsilon is false unless no_epsilon_produced is true.

Member Function Documentation

template<class State, class Symbol, class Implementation>

void Limi::automaton< State, Symbol, Implementation >::initial_states ( State_vector & states ) const

inline

Returns the initial states.

Parameters

states A list of states where the initial states must be added.

template<class State, class Symbol, class Implementation>

void Limi::automaton< State, Symbol, Implementation >::initial_states ( State_set & states ) const

inline

Returns the initial states.

Parameters

states A list of states where the initial states must be added.

template<class State, class Symbol, class Implementation>

State_vector Limi::automaton< State, Symbol, Implementation >::initial_states ( ) const

inline

Returns a set of initial states.

Returns: The set of initial states.

template<class State, class Symbol, class Implementation>

void Limi::automaton< State, Symbol, Implementation >::int_initial_states ( State_vector & states ) const

Implement Returns the initial states.

Parameters

states A list of states where the initial states must be added.

template<class State, class Symbol, class Implementation>

bool Limi::automaton< State, Symbol, Implementation >::int_is_epsilon ( const Symbol & symbol ) const

Implement Determines if a symbol should be considered an epsilon transition.

If a symbol is an epsilon transition it means that this symbol will be collapsed and never appear if collapse_epsilon is true. If collapse_epsilon is false the symbol will appear in the counter-example produced by the language inclusion, but the right-hand side will not be advanced on an epsilon transition.

Returns: Returns true if a symbol should be considered an epsilon transition.

template<class State, class Symbol, class Implementation>

bool Limi::automaton< State, Symbol, Implementation >::int_is_final_state ( const State & state ) const

Implement This function determines if a specific state is final.

Parameters

state The state to examine.

Returns: True if state is final, false otherwise.

template<class State, class Symbol, class Implementation>

void Limi::automaton< State, Symbol, Implementation >::int_next_symbols	(	const State &	state,
		Symbol_vector &	symbols
	)		const

Implement Returns possible successor symbols for a state.

Note that it is possible to return symbols by this function and when later int_successors() is queried for a specific symbol it returns an empty list. This function must return a superset of possible successor symbols.

Parameters

state	The state for which successor symbols should be listed.
symbols	A vector of symbols, where the symbols on the outgoing edges of state should be added. May not be empty when the function is called.

template<class State, class Symbol, class Implementation>

printer_base<State>* Limi::automaton< State, Symbol, Implementation >::int_state_printer ( ) const

inline

Optionally Implement Returns a printer for states.

This function is called once the first time the printer is requested using state_printer. The default implementation will return a new instance of Limi::printer <State>.

Returns: A pointer to the printer. The base class will take ownership of the pointer and delete it when destructed.

template<class State, class Symbol, class Implementation>

void Limi::automaton< State, Symbol, Implementation >::int_successors	(	const State &	state,
		const Symbol &	sigma,
		State_vector &	successors
	)		const

Implement Returns the successor for a specific state.

Parameters

state	The state for which the successors should be determined.
sigma	The symbol indicating the transition that should be followed.
successors	The vector where the successors should be added. The vector may be empty on function call.

template<class State, class Symbol, class Implementation>

printer_base<Symbol>* Limi::automaton< State, Symbol, Implementation >::int_symbol_printer ( ) const

inline

Optionally Implement Returns a printer for symbols.

This function is called once the first time the printer is requested using symbol_printer. The default implementation will return a new instance of Limi::printer <Symbol>.

Returns: A pointer to the printer. The base class will take ownership of the pointer and delete it when destructed.

template<class State, class Symbol, class Implementation>

bool Limi::automaton< State, Symbol, Implementation >::is_epsilon ( const Symbol & symbol ) const

inline

Determines if a symbol should be considered an epsilon transition.

If a symbol is an epsilon transition it means that this symbol will be collapsed and never appear if collapse_epsilon is true. If collapse_epsilon is false the symbol will appear in the counter-example produced by the language inclusion, but the right-hand side will not be advanced on an epsilon transition.

Returns: Returns true if a symbol should be considered an epsilon transition.

template<class State, class Symbol, class Implementation>

bool Limi::automaton< State, Symbol, Implementation >::is_final_state ( const State & state ) const

inline

This function determines if a specific state is final.

Parameters

state The state to examine.

Returns: True if state is final, false otherwise.

template<class State, class Symbol, class Implementation>

bool Limi::automaton< State, Symbol, Implementation >::is_final_state ( const State_set & states ) const

inline

Determines if one of the states is final.

Parameters

states A set of states.

Returns: True iff any of the states is a final state.

template<class State, class Symbol, class Implementation>

void Limi::automaton< State, Symbol, Implementation >::next_symbols	(	const State &	state,
		Symbol_vector &	symbols
	)		const

inline

Returns possible successor symbols for a state.

Parameters

state	The state for which successor symbols should be listed.
symbols	A set of symbols, where the symbols on the outgoing edges of state should be added. Need not be empty when the function is called.

template<class State, class Symbol, class Implementation>

Symbol_vector Limi::automaton< State, Symbol, Implementation >::next_symbols ( const State & state ) const

inline

Returns possible successor symbols of a state.

Parameters

state The state.

Returns: The symbols on the outgoing edges of state

template<class State, class Symbol, class Implementation>

void Limi::automaton< State, Symbol, Implementation >::next_symbols	(	const State &	state,
		Symbol_set &	symbols
	)		const

inline

Returns possible successor symbols of a state.

Parameters

state	The state.
symbols	A set of symbols, where the symbols on the outgoing edges of state should be added. Need not be empty when the function is called.

template<class State, class Symbol, class Implementation>

const printer_base<State>& Limi::automaton< State, Symbol, Implementation >::state_printer ( ) const

inline

Returns a printer for states.

The function is efficient and can be called often.

Returns: A reference to the printer.

template<class State, class Symbol, class Implementation>

void Limi::automaton< State, Symbol, Implementation >::successors	(	const State &	state,
		const Symbol &	sigma,
		State_vector &	successors1
	)		const

inline

Returns the successor for a specific state.

Parameters

state	The state for which the successors should be determined.
sigma	The symbol indicating the transition that should be followed.
successors1	The set where the successors should be added. The set need not be empty on function call.

template<class State, class Symbol, class Implementation>

State_set Limi::automaton< State, Symbol, Implementation >::successors	(	const State_set &	states,
		const Symbol &	sigma
	)		const

inline

Finds successors for a set of states.

Parameters

states	The starting states
sigma	The symbol we are looking for a successor for

Returns: A set of successor states

template<class State, class Symbol, class Implementation>

void Limi::automaton< State, Symbol, Implementation >::successors	(	const State_set &	states,
		const Symbol &	sigma,
		State_set &	successors1
	)		const

inline

Returns successors for a set of states.

Parameters

states	The starting states
sigma	The symbol we are looking for a successor for
successors1	Successors are added to this set.

template<class State, class Symbol, class Implementation>

State_vector Limi::automaton< State, Symbol, Implementation >::successors	(	const State &	state,
		const Symbol &	sigma
	)		const

inline

Returns successors for a state.

Parameters

state	The state.
sigma	The symbol for successors.

Returns: The successors of state for symbol sigma.

template<class State, class Symbol, class Implementation>

const printer_base<Symbol>& Limi::automaton< State, Symbol, Implementation >::symbol_printer ( ) const

inline

Returns a printer for symbols.

The function is efficient and can be called often.

Returns: A reference to the printer.

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

Limi/automaton.h

Public Member Functions

Public Attributes

Detailed Description

template<class State, class Symbol, class Implementation> class Limi::automaton< State, Symbol, Implementation >

Constructor & Destructor Documentation

Member Function Documentation

template<class State, class Symbol, class Implementation>
class Limi::automaton< State, Symbol, Implementation >