##
Implementing and using finite automata toolkits

** Bruce Watson** (Ribbit Software Systems)

Finite automata (and various extensions of them) are used in areas as
diverse as: compilers, digital flight control, speech recognition,
genetic sequencing, and Java program verification. Unfortunately, as
the number of applications has grown, so has the variety of
implementations and implementation techniques. Typically, programmers
will be confused enough to resort to their text books for the most
elementary algorithms.

Recently, advances have been made in taxonomizing algorithms (for
constructing automata) and in evaluating various implementation
strategies. Armed with this, a number of general-purpose toolkits have
been developed at universities. One of these, known as the FIRE Lite,
was developed at the Eindhoven University of Technology, in the
Netherlands. We will consider the structure and use of this toolkit,
which provides implementations of all of the known algorithms for
constructing automata from regular expressions, and all of the known
algorithms for minimizing deterministic finite automata.

The first edition of the toolkit was designed with compilers in mind.
More recently, computation linguists have become interested in using
the toolkit. This has lead to the development of a much more general
interface to the toolkit, including the support of both Mealy
(transition labeled) and Moore (state labeled) regular transducers.

While such a toolkit may appear extremely complex, there are only a
few choices to be made. We also consider a ``recipe'' for making good
use of the toolkits.

Lastly, we consider the future of the toolkit. While this toolkit has
some obvious commercial value (and it is being commercialized), we are
committed to maintaining a version which is freely available for
non-commercial use.

PDF version (4 pages, 88k)