Re: NFA to DFA question

                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
universes" view.


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
universes.


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
path was.


-t

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