|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:||firstname.lastname@example.org (Tom Lord)|
|Date:||21 Jan 2003 00:02:09 -0500|
|Organization:||emf.net -- Quality Internet Access. (510) 704-2929 (Voice)|
|Posted-Date:||21 Jan 2003 00:02:09 EST|
I am reading the compilers book by Aho ullman, and I have one
doubt about NFA to DFA conversion.
"Every state of DFA corresponds to 'set of states' in
NFA". Can anybody explain to me this? Does anybody has a
source code sample for NFA-DFA? May be if I implement the DFA
algorithm I will understand what that means.
I'm interpreting that question as a search for an intuitive model.
You've gotten several replies, all saying the same thing but
differently. Here's the one I've found useful: the "multiple
Your goal in running an automata is (say, for now, slightly
oversimplifying) to read tokens from input, take transitions, and
eventually reach a final state.
With an NFA, you read a token, and you sometimes have a choice: more
than one transition is possible. You could go to this node or to that
node: it's _nondeterministic_.
Let's describe that by saying that in one possible universe you take
one transition, but in another possible universe you take another.
So each transition on your NFA gives you a _set_ of possible
Now we can make a graph of sets of universes: from the initial state,
on a given character, you reach a possible set of universes. In our
new graph, make that entire set of universes a single node. On a
different character, you might reach a different set of universes:
make that set a different node.
Keep doing that: from one set of universes, on a given character,
there's another set that you might wind up at. That's a new node.
Anytime in this process that you wind up with two sets of universes
that have exactly the same members -- well, treat those as equal --
those are the same node in your new graph.
The new graph that you build this way is a DFA. From your NFA you
built a DFA. Now you can go back and read the math of NFA->DFA
conversion with the intuitive model of multiple universes in mind.
For example, you can prove that you're really building a DFA. For
another example: you can prove that if you reach a set of possible
universes that includes an NFA final state, then there is an NFA path
for that input that reaches a final state. And you can prove that, in
general, you can't tell by looking at the DFA path just what that NFA
Return to the
Search the comp.compilers archives again.