** Next:** Practical Experience
**Up:** A note on Implementation
** Previous:** Determinization of Transducers

##

Minimization

The *FSA Utilities* toolbox provides implementations of
three different minimization algorithms. For a comparison of these and
other minimization algorithms, refer to Watson ([16]).
The first minimization algorithm is taken from Hopcroft and Ullman
([6]). In our implementation the following phases
can be identified. Firstly, transitions are added to the incoming
automaton to ensure that the transition function is total (note that
it is assumed that the input is already deterministic). Then, in the
second step, all pairs of non-identical states are computed. In the
third phase, the automaton is adapted in such a way that states that
were found to be identical receive a single name. Finally, some
unneccessary transitions are thrown away (those ending and starting in
the `sink' state).

The computation of the set of pairs of non-identical states starts out
with pairs of states for which one element is a final state and the
other element is not a final state: these clearly are non-identical.
These pairs are taken as an agenda and we then proceed to find more
pairs of non-identical states on the basis of these pairs. Such new
non-identical pairs can be obtained by the following reasoning. If
`P` and `Q` are non-identical states, and there are
transitions `trans(P1,Sym,P)` and `trans(Q1,Sym,Q)` then ` P1, Q1` is a pair of non-identical states too.

The *FSA Utilities* toolbox also provides an implementation of
Brzozowski's method of minimizing an automaton (Brzozowski
[2], Watson [16]). In this method the
(possibly non-deterministic) automaton is reversed, determinized,
reversed and determinized. Note that this method is often much faster
than the previous method. Moreover the input can be non-deterministic.
Finally, the implementation is very simple, since it consists
only of automaton reversal (a particularly simple operation) and
determinization (which is useful independently).

The third algorithm for minimization that is provided is the algorithm
from Hopcroft ([5]). Our implementation closely follows
the presentation of Watson [16]). A disadvantage of this
algorithm is that it is much more complicated than the other two.

** Next:** Practical Experience
**Up:** A note on Implementation
** Previous:** Determinization of Transducers
*Noord G.J.M. van *

1998-09-28