Re: NFA to DFA question

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