Re: NFA to DFA, minimize DFA (Boris Burshteyn)
Mon, 7 Oct 91 10:17:36 -0700

          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 (1991-10-09)
Re: NFA to DFA, minimize DFA (1991-10-09)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Boris Burshteyn)
Keywords: lex, theory
Organization: Compilers Central
References: 91-10-015
Date: Mon, 7 Oct 91 10:17:36 -0700

>From roberto bagnara:
(4 Oct 91 09:41:18)

>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?

I have recently implemented conversion from NFA to DFA while developing
minimal state full LR1 parser generator. I supposed that the most time
consuming operations are:

1. comparison of two (or several) sets of objects.
2. getting union and intersection of several sets of objects.

It is possible to have all these operations implemented with the speed
o(l) where l is the maximum power of the involved sets. The technique is
to have an integer 'w' stored in each of the objects and mark that integer
with the value unique to the set. For example, if p1 points to a list of
objects, p2 points to some other list of objects, then the comparison
algorithm may look something like the following (assuming lists end with 0

int compare(register object *p1, register object *p2, register int i)
register int c = 0;
while ( p1 )
p1->w = i;
p1 = p1->link;
while ( p2 )
if ( p2->w != i )
return 1; // failure, sets are not equal
p2 = p2->link;
if ( c )
return 1; // failure, sets are not equal
return 0; // o'k, sets have the same elements

The driving algorithm which calls functions like compare() must increment
the 'generation number' 'i' each time before calling such a function in
order to perform a number of these operations correctly.

The technique has resulted in the speed of the LR1 parser generator
(written in C++) twice as fast as YACC.

Post a followup to this message

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