next up previous
Next: Finite-state Transducers Up: Operations on Finite Automata Previous: Determinization

Minimization

Currently, the toolbox supports three different implementations of the minimization operation. The option -m indicates that the algorithm of Hopcroft and Ullman ([6]) should be used. The input automaton should already be deterministic. The option -m2 indicates the use of Brzozowski's method (Brzozowski [2]). The input automaton does not need to be deterministic. The option -m3 indicates that Hopcroft's algorithm should be used (Hopcroft [5]). The input automaton must be deterministic. The implementation of these algorithms is described in section 6.3.


% fsa -d < y.nd | fsa -m > y.m
% fsa -m2 < y.nd > y.m
(24)



Noord G.J.M. van
1998-09-28