Re: NFA to DFA, minimize DFA (Karsten Nyblad, TFL)
9 Oct 91 09:38:00 +0100

          From comp.compilers

Related articles
NFA to DFA, minimize DFA (1991-10-04)
Re: NFA to DFA, minimize DFA (1991-10-07)
Re: NFA to DFA, minimize DFA (1991-10-09)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (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 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

Post a followup to this message

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