|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:||Stephen Horne <email@example.com>|
|Date:||Mon, 13 Apr 2009 03:26:16 +0100|
|Posted-Date:||13 Apr 2009 17:54:59 EDT|
On Tue, 7 Apr 2009 12:36:47 -0500, Alexander Morou
>I have a question about epsilon transitions in standard NFA
>implementations: What exactly are they for?
One reason is that many different automata compositions can be
implemented very simply using epsilon transitions. You then use a
single simple epsilon-elimination and nondeterminism-reducing
algorithm rather than needing to build that complexity into every
Concatenation - draw an epsilon transition from each end-state in the
first machine to each begin-state in the second machine.
Repeat one-or-more - draw an epsilon transition from each end-state to
Optional - draw an epsilon transition from each begin-state to each
Ragel is a program which allows lexical analysis code to be generated,
and which composes FSMs in this kind of way. The manual is pretty good
at explaining how each of the composition operators works.
If you don't do FSM composition - e.g. if you derive the whole FSM
model in one step - I would guess that epsilon transitions aren't
useful (though I am far from expert, and may well be wrong). However,
if you use this approach, I'm not sure why you would be dealing with
nondeterministic automata anyway.
Return to the
Search the comp.compilers archives again.