|NFA to DFA question email@example.com (Unmesh joshi) (2003-01-12)|
|Re: NFA to DFA question firstname.lastname@example.org (Clint Olsen) (2003-01-17)|
|Re: NFA to DFA question email@example.com (2003-01-17)|
|Re: NFA to DFA question firstname.lastname@example.org (Michael N. Christoff) (2003-01-17)|
|Re: NFA to DFA question email@example.com (2003-01-21)|
|Re: NFA to DFA question firstname.lastname@example.org (Joachim Durchholz) (2003-01-25)|
|Re: NFA to DFA question email@example.com (Ralph Becket) (2003-01-30)|
|From:||Joachim Durchholz <firstname.lastname@example.org>|
|Date:||25 Jan 2003 01:03:14 -0500|
|Posted-Date:||25 Jan 2003 01:03:12 EST|
Let me give it another try from Tom Lord's perspective: offering an
intuitive view of what's happening during the NFA->DFA conversion.
The basic idea is not to run the NFA as it is, but to build an NFA
simulator that traces all possible execution histories of the NFA in
The simulator is just like the NFA, but instead of a single state, it
uses a set of states. Initially, the simulator set-of-states consists of
the start states of the NFA; whenever it gets an input C, it constructs
the new set of states by following all arrows from states in its
stateset that are labelled with C.
The DFA is just a precomputed version of the simulator. It's again
just a single state at a time, but every state in its graph
corresponds to a set of state from the NFA. The construction process
just traces out all possible execution histories of the NFA.
Hope this clarifies things a bit further.
Return to the
Search the comp.compilers archives again.