Re: NFA to DFA, minimize DFA

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.


Karsten Nyblad
TFL, A Danish Telecommunication Research Laboratory
E-mail: karsten@tfl.dk
--

Return to the comp.compilers page.
Search the comp.compilers archives again.