Re: Why nfa-epsilon?

Erik de Castro Lopo <erikd@mega-nerd.com> writes:


> I'm perfectly happy with my understanding of the difference between
> NFAs and DFAs, but as far as I can see there are at least two
> (possibly overlapping) kinds of NFAs:
>
> - NFAs with epsilon transitions, where no input symbols are
> consumed when moving from state to state on an epsilon
> transition.
>
> - NFAs which when in some state and accepting an input symbol
> can transtion to more than one state.
>
> I realise that these two are basically eqivalent and that either
> of these could be converted to the other, but I've found a couple
> of articles on the web explaining the conversion of the first type
> of NFA to a DFA, but none explaining the second.
>
> Why is that?


Although I can't be certain, it is probably because there is an easy
path using the 1st type of NFA (with epsilon transitions) to go from a
textual regular expression to an NFA with epsilon transitions
(e.g. either Thompson's construction or Glushkov's) and then do subset
construction to get you to a DFA. Since this path solves most of the
problems one currently wants addressed, NFA's of your 2nd type would
need a compelling reason to be investigated further.


As you note, you can trivially convert NFA's of the 2nd type into the
1st type, simply take a state with more than 1 edge on a given symbol
into two (or more) states joined by epsilon transitions, each state
having one 1 edge on each symbol. Then, you can apply the normal
already well-known subset construction algorithm.


Now, again, if you can show some advantage to dealing with the 2nd
type of NFA, then perhaps it will catch on. However, there is inertia
to the knowledge we already have that will be need to be overcome.


Worth mentioning is that last summer I worked with Michela Becchi, an
intern from Washington University (in St Louis), on various mixtures
of NFAs and DFAs. She showed that some simple permutations on the
subset construction algorithms allowed one to efficiently solve
several problems the neither NFAs nor DFAs alone are practical upon.


I would not be surprised if other non-traditional NFA uses and models
had their appropriate place. Not everything worth knowing can be
found on an easily accessed web page.


Hope this helps,
-Chris


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

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