Re: NFA to DFA question

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?


I like to think of a state machine as a box of lights. In a DFA, only
one light, the one representing the current state, is on at any given
time. Which light comes on after the next symbol is read depends upon
the symbol itself and which light is currently on.


In an NFA, several lights may be on simultaneously, one for each state
that is reachable from the starting state given the symbols input so
far. Whether a particular light comes on after the next symbol is
read depends upon whether that state is reachable from one of the
currently lit states via that symbol.


Now, one can write down all the possible combinations of lights being
on or off in an NFA box and assign each combination a number. One can
then say for each combination and for each possible symbol what the
next combination must be. But this is exactly what a DFA is. Hence
each possible set of states (combination of lights) in an NFA is
represented by a single state in the corresponding DFA.


Hope this helps,


Ralph

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