Re: NFA->DFA - Why use epsilon transitions?

torbenm@pc-003.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Tue, 14 Apr 2009 17:53:24 +0200

          From comp.compilers

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)
| List of all articles for this month |

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.