In many situations an automaton is conveniently described through a diagram like the following
This diagram describes a (deterministic) automaton with \( 3 \) states (the elements of the set \( \{1,2,3\}). \) The arrow pointing to the state \( 1 \) indicates that \( 1 \) is the initial state and the two circles around state \( 3 \) indicate that \( 3 \) is a final or accepting state. The set \( \{a,b\} \) is the alphabet of the automaton; its elements are called letters and are the labels of the edges of the diagram. The words \( a \) , \( ab^2 \) , \( b^5a^3b \) are examples of words recognized by the automaton since they are labels of paths from the initial to the final state.
The set of words recognized by an automaton is called the language of the automaton. It is a rational language and may be represented through a rational expression. For instance,
(aUb)(a(aUb)Ub(aUb))*
is a rational expression representing the language of the above automaton.
Kleene's Theorem states that a language is rational if and only if it is the language of a finite automaton. Both directions of Kleene's Theorem can be proved constructively, and these algorithms, to go from an automaton to a rational expression and vice-versa, are implemented in this package.
Of course, one has to pay attention to the size of the output produced. When producing a deterministic automaton equivalent to a given rational expression one can obtain an optimal solution (the minimal automaton) using standard algorithms [AHU74].
When producing a rational expression for the language of an automaton, and taking into account some reasonable measure for the size of a rational expression, to determine a minimal one is apparently computationally difficult. We use here some heuristic methods (to be published elsewhere) which in practice lead to very reasonable results.
The development of this work has benefited from the existence of AMoRE [MMP+95], a package written in C to handle Automata, Monoids and Regular Expressions. In fact, its manual has been very useful and some of the algorithms implemented here are those implemented in AMoRE. In this package, unlike what happened with AMoRE, we do not have to worry about the monoid part in order to make it useful to semigroup theorists, since monoids are already implemented in GAP and we may take advantage of this fact. We just need a function to compute the transition semigroup of an automaton.
The parts of this package that have not so directly to do with automata or rational expressions are put into appendices in this manual. Some words about these appendices follow.
Using the external program Graphviz [DEG+02] to graph visualization, one can visualize automata. This very convenient tool presently works easily under LINUX.
Given a finitely generated subgroup of the free group it is possible to compute a flower automaton and perform Stallings foldings over it in order to obtain an inverse automaton corresponding to the given subgroup.
generated by GAPDoc2HTML