To get at least some idea of the system's practical behavior, first consider a finite-state automaton recognizing all mono-syllabic Dutch words. This non-deterministic automaton (written by Gosse Bouma) has 185 transitions, 9 jumps, 42 states and 26 symbols. Determinization takes 200 milliseconds (on a 1995 HP-UX 9000/735), resulting in an automaton with 49 states and 392 transitions. Minimization is much slower: it takes about 24 seconds to reduce the number of states to 36 and the number of transitions to 315. If Brzozowski's method is used, minimization can be done in less than three seconds and has the additional advantage that the input need not be determinized first. Hopcroft's method takes about 11 seconds.

As another example consider a finite-state *transducer* which
translates temporal expressions such as *two minutes before half
past seven* into `7 28`. This automaton is larger: it has 5824
states, 8809 transitions, 67 input symbols and 61 output symbols.
Determinization takes less than 5 seconds. The result has 1714 states
and 3362 transitions. In comparison, in order to determinize the
automaton defining the domain of the transduction (obtained by simply
removing the output part of the symbols) takes less than three
seconds. The resulting automaton can be minimized (using Brzozowski's
method) in about four seconds.

1998-09-28