Sun, 24 Feb 2008 18:22:51 -0500

Related articles |
---|

Why nfa-epsilon? erikd@mega-nerd.com (Erik de Castro Lopo) (2008-02-24) |

Re: Why nfa-epsilon? derekrss@yahoo.ca (Derek) (2008-02-24) |

Re: Why nfa-epsilon? cfc@shell01.TheWorld.com (Chris F Clark) (2008-02-24) |

From: | Chris F Clark <cfc@shell01.TheWorld.com> |

Newsgroups: | comp.compilers |

Date: | Sun, 24 Feb 2008 18:22:51 -0500 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 08-02-066 |

Keywords: | lex |

Posted-Date: | 25 Feb 2008 09:56:32 EST |

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)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.