Input description: A deterministic finite automaton M.
Problem description: The smallest deterministic finite automaton M' such that M' behaves identically to M.
Discussion: Problems associated with constructing and minimizing finite state machines arise repeatedly in software and hardware design applications. Finite state machines are best thought of as pattern recognizers, and minimum-size machines correspond to recognizers that require less time and space. Complicated control systems and compilers are often built using finite state machines to encode the current state and associated actions, as well as the set of possible transitions to other states. Minimizing the size of this machine minimizes its cost.
Finite state machines are best thought of as edge-labeled directed graphs,
where
each vertex represents one of n states and each edge a transition from one
state to the other on receipt of the alphabet symbol
that labels the edge.
The automaton above analyzes
a given sequence of coin tosses, with the dark states signifying that an
even number of heads have been observed.
Automata can be represented using any graph data structure (see
Section 
), or by using an 
transition matrix, where 
is the size of the alphabet.
Finite state machines are often used to specify search patterns in the guise
of regular expressions, which are
patterns formed by and-ing, or-ing, and
looping over smaller regular expressions.
For example, the regular expression 
matches any
string on (a,b,c) that begins and ends with an a (including a itself).
The best way to test whether a string is described by a given regular
expression (especially if many strings will be tested)
is to construct the equivalent finite automaton and then simulate
the machine on the string.
See Section for alternative approaches to string matching.
We consider three different problems on finite automata:
Algorithms for minimizing the number of states in a deterministic finite automaton (DFA) appear in any book on automata theory. The basic approach works by partitioning the states into gross equivalence classes and then refining the partition. Initially, the states are partitioned into accepting, rejecting, and other classes. The transitions from each node branch to a given class on a given symbol. Whenever two states , t in the same class C branch to elements of different classes, the class C must be partitioned into two subclasses, one containing , the other containing t.
This algorithm makes a sweep though all the classes
looking for a new partition, and repeating the process from scratch if it finds
one.
This yields an 
algorithm, since at most n-1 sweeps need ever
be performed.
The final equivalence classes correspond to the states in the minimum
automaton.
In fact, a more
efficient, 
algorithm is known with available implementations
discussed below.
In fact, any NFA can be mechanically converted to an equivalent DFA, which can then be minimized as above. However, converting an NFA to a DFA can cause an exponential blowup in the number of states, which perversely might later be eliminated in the minimization. This exponential blowup makes automaton minimization problems NP-hard whenever you do not start with a DFA.
The proofs of equivalence between NFAs, DFAs, and regular expressions are elementary enough to be covered in undergraduate automata theory classes. However, they are surprisingly nasty to implement, for reasons including but not limited to the exponential blowup of states. Implementations are discussed below.
The nondeterministic construction uses 
-moves, which are
optional
transitions that require no input to fire.
On reaching a state with an -move, we must assume that the machine
can be in either state.
Using such -moves, it is straightforward to construct an
automaton from a depth-first traversal of the parse tree of the regular
expression.
This machine will have O(m) states, if m is the length of the regular
expression.
Further, simulating this machine on a string of length n takes O(m n)
time, since we need consider each state/prefix pair only once.
The deterministic construction starts with the parse tree for the regular
expression, observing that each leaf represents one of the alphabet symbols
in the pattern.
After recognizing a prefix of the text, we can be left in some subset of
these possible positions, which would correspond to a state in the finite
automaton.
The derivatives method builds up this automaton state by state as it
is needed.
Even so, some regular expressions of length m require 
states in
any DFA implementing them, such as 
.
There is no way to avoid this exponential blowup in the space required.
Note, however, that it takes linear time to simulate an
input string on any automaton, regardless of the size of the automaton.
Implementations: FIRE Engine is a finite automaton toolkit, written in C++
by Bruce Watson.
It provides production-quality implementations of finite automata and
regular expression algorithms.
Several finite automaton minimization algorithms have been implemented,
including Hopcroft's 
algorithm.
Both deterministic and nondeterministic automata are supported.
FIRE Engine
has been used for compiler construction, hardware modeling, and computational
biology applications.
It is strictly a computing engine and does not provide a graphical
user interface.
FIRE Engine is available by anonymous ftp from ftp.win.tue.nl in the
directory /pub/techreports/pi/watson.phd/.
A greatly improved commercial version is available
from www.RibbitSoft.com.
Grail is a C++ package for symbolic computation with finite automata and regular expressions, from Darrell Raymond and Derrick Wood. Grail enables one to convert between different machine representations and to minimize automata. It can handle machines with 100,000 states and dictionaries of 20,000 words. All code and documentation are accessible from the WWW site http://www.csd.uwo.ca/research/grail, as well as pointers to a variety of other automaton packages. Commercial use of Grail is not allowed without approval, although it is freely available to students and educators.
An implementation in C of a regular-expression
matching algorithm appears in [BR95].
The source code for this program is printed in the text and
is available on disk for a modest fee.
A bare bones implementation in C of a regular-expression pattern matching
algorithm
appears in [GBY91].
See Section .
XTango (see Section )
includes a simulation of a DFA.
Many of the other animations (but not this one) are interesting and
quite informative to watch.
FLAP (Formal Languages and Automata Package) is a
tool by Susan Rodger for drawing and simulating
finite automata, pushdown automata, and
Turing machines. Using FLAP, one can draw a graphical representation
(transition diagram) of an automaton, edit it, and simulate the automaton
on some input.
FLAP was developed in C++ for X-Windows.
See http://www.cs.duke.edu:80/ 
rodger/tools/tools.html.
Notes: Aho [Aho90] provides a good survey on algorithms for
pattern matching,
and a particularly clear exposition for the case where the patterns
are regular expressions.
The technique for regular expression pattern matching with -moves
is due to Thompson [Tho68].
Other expositions on finite automaton pattern matching include [AHU74].
Hopcroft [Hop71] gave an optimal algorithm
for minimizing the number of states in DFAs.
The derivatives method of constructing a finite state machine from a regular
expression is due to Brzozowski [Brz64] and has been
expanded upon in [BS86].
Expositions on the derivatives method includes Conway [].
Testing the equivalence of two nondeterministic finite state machines
is PSPACE-complete [SM73].
Related Problems: Satisfiability (see page ).
string matching (see page ).
