30 Jan 2003 00:04:05 -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: | Ralph Becket <rafe@cs.mu.oz.au> |

Newsgroups: | comp.compilers |

Date: | 30 Jan 2003 00:04:05 -0500 |

Organization: | http://www.TeraNews.com - FREE NNTP Access |

References: | 03-01-051 |

Keywords: | lex, DFA |

Posted-Date: | 30 Jan 2003 00:04:05 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?*

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.