Re: NFA to DFA question

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