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

On Tue, 7 Apr 2009 12:36:47 -0500, Alexander Morou
<alexander.morou@gmail.com> wrote:


>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
composition algorithm.


For example...


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
each begin-state.


Optional - draw an epsilon transition from each begin-state to each
end-state.


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.


http://www.complang.org/ragel/


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 comp.compilers page.
Search the comp.compilers archives again.