Re: NFA to DFA question (Tom Lord)
21 Jan 2003 00:02:09 -0500

          From comp.compilers

Related articles
NFA to DFA question (Unmesh joshi) (2003-01-12)
Re: NFA to DFA question (Clint Olsen) (2003-01-17)
Re: NFA to DFA question (2003-01-17)
Re: NFA to DFA question (Michael N. Christoff) (2003-01-17)
Re: NFA to DFA question (2003-01-21)
Re: NFA to DFA question (Joachim Durchholz) (2003-01-25)
Re: NFA to DFA question (Ralph Becket) (2003-01-30)
| List of all articles for this month |

From: (Tom Lord)
Newsgroups: comp.compilers
Date: 21 Jan 2003 00:02:09 -0500
Organization: -- Quality Internet Access. (510) 704-2929 (Voice)
References: 03-01-051
Keywords: lex
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
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

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.


Post a followup to this message

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