FSA Utilities

The FSA Utilities tool-box is a collection of tools to manipulate regular expressions, finite-state automata and finite-state transducers (both string-to-string and string-to-weight transducers). Manipulations include determinisation (both for finite-state acceptors and finite-state transducers), minimisation, composition, complementation, intersection, Kleene closure, etc. Various visualisation tools are available to browse finite-state automata. The tool-box is implemented in SICStus Prolog.

The motivation for the FSA Utilities tool-box has been the rapidly growing interest for finite-state techniques in computational linguistics. The FSA Utilities tool-box has been developed to experiment with these techniques. The tool-box is available free of charge under Gnu General Public License.³ The following provides an overview of the functionality of the tool-box.

• Construction of finite automata on the basis of regular expressions. Regular expression operators include concatenation, Kleene closure, union and option (the standard regular expression operators). Furthermore the extended regular expression operators are provided: complement, difference and intersection. Symbols can be intervals of symbols, or the `Any'-variable which matches any symbol. Regular expression operators are provided for operations on the underlying automaton, including minimisation and determinisation. Finally, we support user-defined regular expression operators.

• We also provide operators for transductions such as composition, cross-product, same-length-cross-product, domain, range, identity and inversion.

• Determinisation and Minimisation. Three different minimisation algorithms are supported: Hopcroft's algorithm [5], Hopcroft and Ullman's algorithm [6], and Brzozowski's algorithm [2].

• Determinisation and minimisation of string-to-string and string-to-weight transducers [9,10].
• Visualisation. Support includes built-in visualisation (Tcl/Tk, LaTeX, Postscript) and interfaces to third party graph visualisation software (Graphviz (dot), VCG, daVinci).

• Random generation of finite automata (an extension of the algorithm in [8] to allow the generation of finite automata containing $\epsilon$-moves).