# Re: NFA to DFA, minimize DFA

## karsten@tfl.dk (Karsten Nyblad, TFL)9 Oct 91 09:38:00 +0100

From comp.compilers

Related articles
NFA to DFA, minimize DFA roberto@cernvax.cern.ch (1991-10-04)
Re: NFA to DFA, minimize DFA bburshte@pyrps5.eng.pyramid.com (1991-10-07)
Re: NFA to DFA, minimize DFA karsten@tfl.dk (1991-10-09)
| List of all articles for this month |

 Newsgroups: comp.compilers From: karsten@tfl.dk (Karsten Nyblad, TFL) Keywords: NFA, DFA Organization: TFL, A Danish Telecommunication Research Laboratory References: 91-10-015 Date: 9 Oct 91 09:38:00 +0100

In article 91-10-015, roberto@cernvax.cern.ch (roberto bagnara) writes:
> Has anybody got a good (e.g. *fast*) algorithm/implementation for the
> problem of converting an NFA (nondeterministic finite automaton) to a DFA
> (deterministic finite automaton)? And for the problem of minimizing the
> number of states of a DFA?

A few tricks:

1) The algorithm in the dragon book is more general than needed
in most cases. The algorithm assumes that there may be
states from where there is no way to an accept state. That
is often not the case. If there is a path from all states
to an accept state, then you know that two states are only equal
if they accept the same set of letters. This can be used
for dividing the states into equivalence classes before
using the general algorithm, that will then be simpler and
have much less work.

2) The order in which the states are checked to find
out whether or not they should still be considered
equivalent is important. In scanner generators,
the algorithm using best order might be linear in
the number of states' time consumption, but the worst
might be in the square.

3) You can mark states with direct transitions to states
that are in equivalence classes that are split in two.
You will need to add pointers from states to their
predecessors in order to do that. When you search
for equivalence classes to split, you search for marked
states instead, and before splitting a class, you remove
the marks on states in that class.