21 Jan 2003 00:02:09 -0500

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) |

From: | lord@emf.emf.net (Tom Lord) |

Newsgroups: | comp.compilers |

Date: | 21 Jan 2003 00:02:09 -0500 |

Organization: | emf.net -- 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

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.