Tue, 14 Apr 2009 17:53:24 +0200

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: | torbenm@pc-003.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen) |

Newsgroups: | comp.compilers |

Date: | Tue, 14 Apr 2009 17:53:24 +0200 |

Organization: | Department of Computer Science, University of Copenhagen |

References: | 09-04-011 |

Keywords: | lex, DFA |

Posted-Date: | 16 Apr 2009 12:29:50 EDT |

Alexander Morou <alexander.morou@gmail.com> writes:

*> I have a question about epsilon transitions in standard NFA*

*> implementations: What exactly are they for?*

*>*

*> I've never really understood their purpose, other than to confuse*

*> people trying to understand FSA and regular languages (with respect*

*> to language scanner generation).*

As Stephen Horne mentioned, the most compelling reason is to allow

NFAs for regular expressions to be built compositionally from regular

expressions in an easy way. There are methods for building

epsilon-free NFAs compositionally from epsilon-free regular

expressions, but these are much more complicated.

Also, with epsilon transitions, the size of an NFA for a regexp of

size N is O(N) states and O(N) transitions, but without epsilon

transitions, the maximal size increases to O(N) states and O(N^2)

transitions. Granted, that is not important if you intend to convert

to a DFA afterwards, as this has O(2^N) states and transitions.

Torben

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.