Thu, 16 Apr 2009 10:14:25 +0530

Related articles |
---|

NFA->DFA - Why use epsilon transitions? alexander.morou@gmail.com (Alexander Morou) (2009-04-07) |

Re: NFA->DFA - Why use epsilon transitions? sh006d3592@blueyonder.co.uk (Stephen Horne) (2009-04-13) |

Re: NFA->DFA - Why use epsilon transitions? alexander.morou@gmail.com (2009-04-14) |

Re: NFA->DFA - Why use epsilon transitions? torbenm@pc-003.diku.dk (2009-04-14) |

Re: NFA->DFA - Why use epsilon transitions? j.vimal@gmail.com (Vimal) (2009-04-16) |

From: | Vimal <j.vimal@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Thu, 16 Apr 2009 10:14:25 +0530 |

Organization: | Compilers Central |

References: | 09-04-011 |

Keywords: | lex |

Posted-Date: | 16 Apr 2009 12:30:22 EDT |

I would like to add the following point to Stephen Horne's list.

2009/4/7 Alexander Morou <alexander.morou@gmail.com>:

*>*

*> I'm wondering if the entire reason I didn't need epsilon transitions*

*> was the method I used to build the NFA structure in the first place.*

Actually, conversion from a regular expression to a NFA is IMHO much

easier, as is outlined in many textbooks (1). The size of a NFA is

usually much smaller (and for some cases, exponentially smaller) than

a DFA. The NFA which you get by following the method (1) is called the

Thompson NFA. On a computer, it might sometimes be more effective to

maintain a subset of states as a bit-vector as opposed to maintaining

a single state on a DFA with possibly exponential number of states.

This page outlines some aspects:

http://swtch.com/~rsc/regexp/regexp1.html

--

Vimal

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.