The following outlines ways of examining automata.
Most operations for examining automata are generic and rely on the intrinsic operations. However, some operations can be optimised for certain types of automata, and then have different performance characteristics.
The Flipsta library cannot actually draw automata; but it can produce .dot files that are straightforward to convert into, say, PDF or SVG, using Graphviz dot.
Produce a .dot file for Graphviz dot to convert into a graphical representation.
The names of states are put inside the nodes; the start and end labels, if any, go next to it. This uses the “xlabel” attribute and requires dot version 2.28 to render. Earlier versions leave out the labels.
The textual representation of states and labels is acquired by streaming them into an ostream.
Assuming the Graphviz dot is installed, then after writing the textual representation to automaton.dot, saying the following on the command line will convert it into a PDF file:
dot -Tpdf automaton.dot -o automaton.pdf
The ostream to output the textual representation to.
The automaton to be drawn.
Lay levels out horizontally instead of vertically.
For various algorithms it is important to traverse automata in a specific order. For example, finding the shortest distance in an acyclic automaton traverses the automaton in topological order. The standard algorithm for finding the topological order uses depth-first traversal.
The standard return value for a function that traverses an automaton is a, possibly lazy, range of states. (Using callback functions would be possible, but this would be more cumbersome to use.)
A topological order is an order of the states of an automaton in which for each transition the source comes before the destination. It is possible to order the states iff the automaton is acyclic.
Return the states of the automaton in topological order.
This may be computed lazily. The automaton must remain in memory and unaltered while the range that is returned is being used.
The standard implementation holds a container of arcs. It is implemented iff traverse is implemented for the automaton and the direction. It takes linear time in the number of transitions and linear space in the number of states to build this.
A specialised implementation can be provided for some automata. An example is automata based on products of automata, for which this can be a lazy list which takes up less space.
Iff the automaton is not acyclic (so that topological order is not defined). In the default implementation, the exception will have errorInfoState <State> attached to it with the state that was detected to have a path to itself. The exception may be thrown during traversal.
A basic way to traverse an automaton is depth-first search.
Traverse the automaton and return (lazily) a range of states marked with their meaning.
The automaton must remain unchanged while the resulting range is being used. The range is non-copyable but it is moveable.
This uses “depth-first search” (for those in the know) to find a spanning forest, and keeps going until the each state have been tried as roots. (Either the state has been seen before, or it is the root of a new tree.) The elements of the resulting range are of type TraversedState <State>. This contains a state, and an enum indicating what stage of traversal the state was involved in. Usually you will want to filter only elements with a limited sets of indicator.
If you do not know how depth-first search works, here is what you need to know to use this function.
The automaton must have states() and arcsOnCompressed.
Pointer to the automaton to traverse. A copy of the pointer will be kept, and destructed when the range is destructed. This can be a unique_ptr. The automaton should not change while the range is used.
The direction in which to traverse the automaton.
Event generated while traversing an automaton using depth-first search.
Public Members
The state that this event concerns.
The type of event.
Indicate the meaning of the state during depth-first traversal.
Values:
Indicates the state will be the root of a tree.
Indicates that a newly discovered state is now being visited.
Indicates that the visit to the state has finished.
Indicates that the state was rediscovered while it was being visited.
Indicates that the state was rediscovered while it was not being visited any more.