|DFA table compression from Aho's Dragon book, need more detail heng@Ag.Arizona.Edu (1998-09-26)|
|Re: DFA table compression from Aho's Dragon book, need more detail email@example.com (1998-09-29)|
|Re: DFA table compression from Aho's Dragon book, need more detail firstname.lastname@example.org (1998-10-04)|
|From:||heng@Ag.Arizona.Edu (Heng Yuan)|
|Date:||26 Sep 1998 01:46:51 -0400|
|Organization:||University of Arizona, Tucson, AZ|
After weeks of studying, I finally got my NFA, NFA to DFA routines to
work. But, I was stuck at Aho's table compression method in the
Dragon book (p144-146).
It is said that 4 tables: default, base, next and check are to be
constructed. But, how? I could not make sense out of the names and
Another question: Aho also only quickly talked about DFA minimization,
I am not sure if I got it right: only DFA's with same important states
can be combined. Thus, at the end of the e_closure routine, I get rid
of all the epsilon edge out nodes and only keep the accept states and
alphabet edge out nodes. If there is a DFA state in the DFA states
that contains the exactly the same set of states, the discard the
newly created e_closure set and refer to the old one instead.
The last question is, what is the efficient way to mark and unmark
state T in the subset construction (NFA to DFA) on p118 of the book?
I used a stack. Also it is quit slow to find out whether if a new DFA
state is already present in the Dstates.
Please help me, I don't have much background.
Name: Heng Yuan Email: email@example.com
Return to the
Search the comp.compilers archives again.