|NFA->DFA - Why use epsilon transitions? firstname.lastname@example.org (Alexander Morou) (2009-04-07)|
|Re: NFA->DFA - Why use epsilon transitions? email@example.com (Stephen Horne) (2009-04-13)|
|Re: NFA->DFA - Why use epsilon transitions? firstname.lastname@example.org (2009-04-14)|
|Re: NFA->DFA - Why use epsilon transitions? email@example.com (2009-04-14)|
|Re: NFA->DFA - Why use epsilon transitions? firstname.lastname@example.org (Vimal) (2009-04-16)|
|From:||email@example.com (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)|
|Date:||Tue, 14 Apr 2009 17:53:24 +0200|
|Organization:||Department of Computer Science, University of Copenhagen|
|Posted-Date:||16 Apr 2009 12:29:50 EDT|
Alexander Morou <firstname.lastname@example.org> 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.
Return to the
Search the comp.compilers archives again.