Why nfa-epsilon?

Erik de Castro Lopo <erikd@mega-nerd.com>
Sun, 24 Feb 2008 09:48:01 +1100

          From comp.compilers
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)
| List of all articles for this month |
From: Erik de Castro Lopo <erikd@mega-nerd.com>
Newsgroups: comp.compilers
Date: Sun, 24 Feb 2008 09:48:01 +1100
Organization: Mega Nerd
Keywords: lex, question
Posted-Date: 24 Feb 2008 00:40:55 EST

Hi all,


I'm playing around with the conversion of NFAs to DFAs.


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?


Erik
--
-----------------------------------------------------------------
Erik de Castro Lopo
-----------------------------------------------------------------
"I ran it on my DeathStation 9000 and demons flew out of my nose." --Kaz


Post a followup to this message

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