Re: NFA to DFA question

Clint Olsen <clint@0lsen.net>
17 Jan 2003 19:40:42 -0500

          From comp.compilers
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)
| List of all articles for this month |
From: Clint Olsen <clint@0lsen.net>
Newsgroups: comp.compilers
Date: 17 Jan 2003 19:40:42 -0500
Organization: AT&T Broadband
References: 03-01-051
Keywords: lex, DFA
Posted-Date: 17 Jan 2003 19:40:42 EST

  Unmesh joshi wrote:
> 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.


Since an NFA can have multiple state transitions per character of input,
and a DFA cannot, it follows that a state in the DFA corresponds to a set
of NFA states (possibly multiple states). The best analogy is given at the
end of that paragraph you quoted where they discuss simultating an NFA and
DFA for the same input string.


The source code from 'flex' should give you an implementation of converting
an NFA to a DFA.


-Clint

Post a followup to this message

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