17 Jan 2003 20:08:59 -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: | "Michael N. Christoff" <mchristoff@sympatico.ca> |

Newsgroups: | comp.compilers |

Date: | 17 Jan 2003 20:08:59 -0500 |

Organization: | Bell Sympatico |

References: | 03-01-051 |

Keywords: | lex, DFA |

Posted-Date: | 17 Jan 2003 20:08:58 EST |

"Unmesh joshi" <unmesh_joshi@hotmail.com> wrote in message

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

In an NFA you may have transitions to multiple states. Let t be the

transition function and q,q1,q2 be states and m a symbol. You may

have t(q,m) = {q1,q2}. Therefore a state in a corrseponding DFA needs

to keep track of all the possible branches that may be taken

simultaneously. This can be done by using one state of a DFA to

represent the pair of states {q1,q2}.

If an NFA has |Q|, then the corresponding DFA may have upto 2^|Q| states,

one state for each possible combination of states in the NFA.

l8r, Mike N. Christoff

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.