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:
Empty type that indicates the forward direction in an automaton.
Empty type that indicates the backward direction in an automaton.
Empty object that indicates the forward direction of traversing an automaton.
Empty object that indicates the backward direction of traversing an automaton.
The operations access an automaton immutably, i.e. without changing it. They usually require that the automaton remains in memory and remains unchanged.
Return the descriptor that the automaton uses to convert between expanded and compressed representations of labels.
The automaton.
Return A range of states in the automaton.
The automaton.
Return true iff state is in automaton.
The automaton.
The state of interest.
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.
The automaton.
The direction from which the states of interest start.
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>().
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 automaton.
The direction to take from state.
The state of interest.
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.
These operations deal with the internal representations of labels:
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.
The automaton.
The direction from which the states of interest start.
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>().
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.
The automaton.
The direction to take from state.
The state of interest.
These compile-time helpers are defined:
Evaluate to a tag type for the automaton type.
To mark a type as an automaton, specialise AutomatonTagUnqualified, which receives an unqualified type.
Evaluate to true iff Automaton is an automaton.
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.
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.
flipsta::Automaton is a mutable automaton type.
An automaton that stores its states and arcs explicitly.
All access operations are supported.
The state type.
The label type on arcs.
(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
The state type, equal to the template parameter.
The label type, equal to the template parameter.
The terminal label type, by default
Public Functions
Initialise with no states, no arcs, and a default-constructed descriptor.
Initialise with no states, no arcs, and the descriptor as given.
The value of the descriptor to use.
Add a new state to the automaton.
iff the state is already in the automaton.
Add an arc to the automaton.
The states must already be in the automaton.
The source state.
The destination state.
the label on the arc.
if the source or destination state does not exist.
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.
If Direction is forward, set the initial state label; if it is backward, set the final state label.
The state to set as a terminal state. This must be in the automaton.
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.
flipsta::ExplicitArc is the arc type used by flipsta::Automaton. It also shows the interface that any arc type must adhere to.
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 type of the states.
The type of the label.
Public Type
The type of the states.
The type of the label.
Public Functions
Construct with the data explicitly.
Indicate that the second argument is the source and the third the destination.
The source state.
The destination state.
The label on the arc.
Construct with the data explicitly.
Indicate that the second argument is the destination and the third the source.
The destination state.
The source state.
The label on the arc.
Construct by copying the data from another arc.
Returns the label on the arc.