Mon, 13 Apr 2009 03:26:16 +0100

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) |

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.