Re: NFA to DFA, minimize DFA

>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
link):


int compare(register object *p1, register object *p2, register int i)
{
register int c = 0;
while ( p1 )
{
p1->w = i;
p1 = p1->link;
c++;
}
while ( p2 )
{
if ( p2->w != i )
return 1; // failure, sets are not equal
p2 = p2->link;
c--;
}
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.
--

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