Re: NFA to DFA, minimize DFA

bburshte@pyrps5.eng.pyramid.com (Boris Burshteyn)Mon, 7 Oct 91 10:17:36 -0700

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 bburshte@pyrps5.eng.pyramid.com (1991-10-09)
Re: NFA to DFA, minimize DFA karsten@tfl.dk (1991-10-09)
| List of all articles for this month |

 Newsgroups: comp.compilers From: bburshte@pyrps5.eng.pyramid.com (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;
c++;
}
while ( p2 )
{
if ( p2->w != i )
return 1; // failure, sets are not equal
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.
--

Post a followup to this message