Automata

There are many different automaton classes, and many of them can be composed. This composition is often lazy, which helps performance. Any automaton can be used using a number of operations. (Not all operations are defined for all types of automata.)

For the complete API documentation, see the Doxygen documentation.

The operations often show symmetry, since automata can be traversed in the direction of the arcs, or the opposite direction. The direction is indicated with either of two classes:

struct flipsta::Forward

Empty type that indicates the forward direction in an automaton.

struct flipsta::Backward

Empty type that indicates the backward direction in an automaton.

constexpr Forward forward

Empty object that indicates the forward direction of traversing an automaton.

constexpr Backward backward

Empty object that indicates the backward direction of traversing an automaton.

Intrinsic operations

The operations access an automaton immutably, i.e. without changing it. They usually require that the automaton remains in memory and remains unchanged.

auto constexpr descriptor

Return the descriptor that the automaton uses to convert between expanded and compressed representations of labels.

Parameters
  • automaton -

    The automaton.

auto constexpr states

Return A range of states in the automaton.

Parameters
  • automaton -

    The automaton.

auto constexpr hasState

Return true iff state is in automaton.

Parameters
  • automaton -

    The automaton.

  • state -

    The state of interest.

auto constexpr terminalStates

Return a range of terminal states and their labels.

If direction is forward, then the initial states are returned; if direction is backward, then the final states are returned. The result type is a range of pairs, or another range type, of states and labels.

Parameters
  • automaton -

    The automaton.

  • direction -

    The direction from which the states of interest start.

auto constexpr terminalLabel

Return the terminal label of a state.

If direction is forward, then this is the start label; if direction is backward, then the final label is returned.

If the state is not a terminal state in direction, or the state does not exist, return math::zero<Label>().

Parameters
  • automaton -

    The automaton to find the state in.

  • direction -

    Indicates whether the interest is in a start state (Forward) or in a final state (Backward).

  • State -

    The state for which the label is sought.

auto constexpr arcsOn

Return A range of all arcs connected to state state in the automaton.

If Direction is forward, the arcs out_of state are returned. If Direction is backward, the arcs into state are returned.

Pre
hasState (automaton, state).
Parameters
  • automaton -

    The automaton.

  • direction -

    The direction to take from state.

  • state -

    The state of interest.

auto constexpr times

Call math::times, with the order of the two arguments depending on direction.

This corresponds to the direction of traversal in automata: when traversing an automaton in forward direction, the labels of an arc a and an arc b that follows immediately are combined with math::times (a, b). When traversing the automaton in backward direction, the arguments must be reversed. This function does that.

Parameters
  • direction -

    The direction of traversal. Must be Forward or Backward.

  • left -

    Left-hand operand.

  • right -

    Right-hand operand.

These operations deal with the internal representations of labels:

auto constexpr terminalStatesCompressed

Return a range of terminal states and their compressed labels.

If direction is forward, then the initial states are returned; if direction is backward, then the final states are returned. The result type is a range of pairs, or another range type, of states and labels.

See
terminalStates
Parameters
  • automaton -

    The automaton.

  • direction -

    The direction from which the states of interest start.

auto constexpr terminalLabelCompressed

Return the compressed terminal label of a state.

If direction is forward, then this is the start label; if direction is backward, then the final label is returned.

If the state is not a terminal state in direction, or the state does not exist, return math::zero<Label>().

auto constexpr arcsOnCompressed

Return A range of all arcs connected to state state in the automaton.

If Direction is forward, the arcs out_of state are returned. If Direction is backward, the arcs into state are returned. The labels on the arcs are in the compressed representation.

Pre
hasState (automaton, state).
See
arcOn
Parameters
  • automaton -

    The automaton.

  • direction -

    The direction to take from state.

  • state -

    The state of interest.

These compile-time helpers are defined:

template <class Automaton>
struct flipsta::AutomatonTag

Evaluate to a tag type for the automaton type.

To mark a type as an automaton, specialise AutomatonTagUnqualified, which receives an unqualified type.

template <class Automaton>
struct flipsta::IsAutomaton

Evaluate to true iff Automaton is an automaton.

template <class Automaton, class Enable = void>
struct flipsta::StateType

The general type of state that the automaton uses.

If Automaton is not an automaton, then this does not contain any type, so that SFINAE is possible.

template <class Automaton, class Enable = void>
struct flipsta::LabelType

Compute the general type of label that the automaton uses.

If Automaton is not an automaton, then this does not contain any type, so that SFINAE is possible.

template <class Automaton, class Enable = void>
struct flipsta::DescriptorType

Compute the general type of descriptor that the automaton uses.

If Automaton is not an automaton, then this does not contain any type, so that SFINAE is possible.

template <class Automaton, class Enable = void>
struct flipsta::CompressedLabelType

Compute the compressed label type that the automaton uses.

If Automaton is not an automaton, then this does not contain any type, so that SFINAE is possible.

A mutable automaton: Automaton

flipsta::Automaton is a mutable automaton type.

template <class State, class Label, class TerminalLabel = void>
class flipsta::Automaton

An automaton that stores its states and arcs explicitly.

All access operations are supported.

Templates
  • State -

    The state type.

  • Label -

    The label type on arcs.

  • TerminalLabel -

    (optional) The label type for initial and final states. If Label is a symbol, this may need to be a different type to indicate an empty symbol sequence. If it is not given, it is set to the result type of calling math::one <Label>().

Public Type

typedef State_ State

The state type, equal to the template parameter.

typedef Label_ Label

The label type, equal to the template parameter.

typedef boost::mpl::if_< std::is_same< TerminalLabel_, void >, typename label::GetDefaultTerminalLabel< Label >::type, TerminalLabel_ >::type TerminalLabel

The terminal label type, by default

Public Functions

Automaton()

Initialise with no states, no arcs, and a default-constructed descriptor.

Automaton(Descriptor const & descriptor)

Initialise with no states, no arcs, and the descriptor as given.

Parameters
  • descriptor -

    The value of the descriptor to use.

void addState(State const & state)

Add a new state to the automaton.

Exceptions
  • StateExists -

    iff the state is already in the automaton.

void addArc(State const & source, State const & destination, Label const & label)

Add an arc to the automaton.

The states must already be in the automaton.

Parameters
  • source -

    The source state.

  • destination -

    The destination state.

  • label -

    the label on the arc.

Exceptions
  • StateNotFound -

    if the source or destination state does not exist.

template <class Direction, class TerminalLabel2>
void setTerminalLabel(Direction direction, State const & state, TerminalLabel2 const & label)

Set the initial or final label for a state.

If the label equals semiring-zero, the state is removed from the set of terminal states. If the label is non-zero, the state is added with the label, or if the state is already a terminal state, then the label is updated.

Parameters
  • direction -

    If Direction is forward, set the initial state label; if it is backward, set the final state label.

  • state -

    The state to set as a terminal state. This must be in the automaton.

  • label -

    The label to set on the state. The label may be of a different type from TerminalLabel, but it must either be equal to semiring-zero, or it must be convertible to TerminalLabel.

An explicit arc type: ExplicitArc

flipsta::ExplicitArc is the arc type used by flipsta::Automaton. It also shows the interface that any arc type must adhere to.

template <class State_, class Label_>
class flipsta::ExplicitArc

An arc type for automata that stores its data explicitly.

And arc is characterised by three pieces of information, which this class holds explicitly:

  • The state it comes from, the source state.
  • The state it goes to, the destination state.
  • The label on the arc.
Templates
  • State -

    The type of the states.

  • Label -

    The type of the label.

Public Type

typedef State_ State

The type of the states.

typedef Label_ Label

The type of the label.

Public Functions

ExplicitArc(Forward const & direction, State const & source, State const & destination, Label const & label)

Construct with the data explicitly.

Parameters
  • direction -

    Indicate that the second argument is the source and the third the destination.

  • source -

    The source state.

  • destination -

    The destination state.

  • label -

    The label on the arc.

ExplicitArc(Backward const & direction, State const & destination, State const & source, Label const & label)

Construct with the data explicitly.

Parameters
  • direction -

    Indicate that the second argument is the destination and the third the source.

  • destination -

    The destination state.

  • source -

    The source state.

  • label -

    The label on the arc.

template <class OtherArc>
ExplicitArc(OtherArc const & other)

Construct by copying the data from another arc.

State const & state(Backward) const

Returns the source state.

State const & state(Forward) const

Returns the destination state.

Label const & label() const

Returns the label on the arc.

Table Of Contents

Previous topic

Labels

Next topic

Examining automata

This Page