Algorithms for Minimization of Finite-State Automata

This page describes software I wrote to implement minimization algorithms for cyclic finite-state automata.

Implemented algorithms

• Incremental minimization by Bruce Watson with my substantial modifications. I wrote the program to test the modifications.
• Hopcroft algorithm
• Hopcroft-Ullman algorithm
• Aho-Sethi-Ullman algorithm
• Brzozowski algorithm

Bruce Watson and I wrote a paper about the algorithm. It appeared in volume 9 issue 1 of the journal Natural Language Engineering. The original algorithm by Bruce Watson was enhanced with my modifications. In short, they consist of:

• Presorting the states on finality, the number of outgoing transitions, and labels on outgoing transitions.
• Putting into variable S (stack of pairs - arguments of the function equiv - see the description of the original algorithm) only the pair of states from the top level of nested calls of the function equiv, and pairs of states that have at least 2 incoming transitions.
• Introducing full memoization on pairs of states, using the UNION-FIND algorithm for dependency chains.

Software

You can download the programs from ftp://ftp.pg.gda.pl/pub/software/xtras-PG/fsa/minim.tar.gz. The programs are free for non-commercial use. They are provided "as is"; I offer you you no guaranty.

The software consists of three programs:

• minimize - the main program in the package. It minimizes automata using any minimization algorithm.
• genaut - generates artificial automata. Generated automata are almost always minimal.
• inflate - increases the number of states in an automaton without changing its language. Note that only cyclic automata can be inflated to an arbitrary size.

Customization