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.