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

Stephen Horne <sh006d3592@blueyonder.co.uk>
Mon, 13 Apr 2009 03:26:16 +0100

          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: Stephen Horne <sh006d3592@blueyonder.co.uk>
Newsgroups: comp.compilers
Date: Mon, 13 Apr 2009 03:26:16 +0100
Organization: virginmedia.com
References: 09-04-011
Keywords: lex, DFA
Posted-Date: 13 Apr 2009 17:54:59 EDT

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.



Post a followup to this message

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