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

alexander.morou@gmail.com
Tue, 14 Apr 2009 03:24:08 -0700 (PDT)

          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: alexander.morou@gmail.com
Newsgroups: comp.compilers
Date: Tue, 14 Apr 2009 03:24:08 -0700 (PDT)
Organization: Compilers Central
References: 09-04-011 09-04-016
Keywords: lex, DFA
Posted-Date: 16 Apr 2009 12:28:08 EDT

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


Actually I still need the non-determinism in NFA for the system
initially. This is due to the nature of the way it's built, I
can't guarantee what's 'next' so prematurely making DFA states
based upon only part of the equation (as it's being built), would
lead to an incorrect DFA result. So the NFA step is still necessary.
After your simple explanation and reading up more on epsilon
transitions, all I've really done is the same thing, without the extra
epsilon steps. Since the goal in this case is clear and not intended
for multiple types of input, I can get away with a simpler non-eps.
version.


Though ironically I've started using a similar system in another area
of the project, which uses the same code (adjusted for type
differences)
to create the same kind of graphs. I'm hoping to make a simple
visualizer for DFA/NFA for the visual layout experience. Though due
to the language I'm using, I still don't think that I would've needed
epsilon transitions, but rather an abstraction layer for the system
to operate upon in which common functional aspects are represented in
a uniform manner (generic typing models are nice).



Post a followup to this message

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