Re: NFA to DFA question

Joachim Durchholz <joachim_d@gmx.de>
25 Jan 2003 01:03:14 -0500

          From comp.compilers
Related articles
NFA to DFA question unmesh_joshi@hotmail.com (Unmesh joshi) (2003-01-12)
Re: NFA to DFA question clint@0lsen.net (Clint Olsen) (2003-01-17)
Re: NFA to DFA question thp@cs.ucr.edu (2003-01-17)
Re: NFA to DFA question mchristoff@sympatico.ca (Michael N. Christoff) (2003-01-17)
Re: NFA to DFA question lord@emf.emf.net (2003-01-21)
Re: NFA to DFA question joachim_d@gmx.de (Joachim Durchholz) (2003-01-25)
Re: NFA to DFA question rafe@cs.mu.oz.au (Ralph Becket) (2003-01-30)
| List of all articles for this month |
From: Joachim Durchholz <joachim_d@gmx.de>
Newsgroups: comp.compilers
Date: 25 Jan 2003 01:03:14 -0500
Organization: Compilers Central
References: 03-01-051
Keywords: DFA, lex
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
parallel.


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.


Regards,
Joachim

Post a followup to this message

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