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

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

Return to the comp.compilers page.
Search the comp.compilers archives again.