|NFA->DFA - Why use epsilon transitions? firstname.lastname@example.org (Alexander Morou) (2009-04-07)|
|Re: NFA->DFA - Why use epsilon transitions? email@example.com (Stephen Horne) (2009-04-13)|
|Re: NFA->DFA - Why use epsilon transitions? firstname.lastname@example.org (2009-04-14)|
|Re: NFA->DFA - Why use epsilon transitions? email@example.com (2009-04-14)|
|Re: NFA->DFA - Why use epsilon transitions? firstname.lastname@example.org (Vimal) (2009-04-16)|
|Date:||Thu, 16 Apr 2009 10:14:25 +0530|
|Posted-Date:||16 Apr 2009 12:30:22 EDT|
I would like to add the following point to Stephen Horne's list.
2009/4/7 Alexander Morou <email@example.com>:
> I'm wondering if the entire reason I didn't need epsilon transitions
> was the method I used to build the NFA structure in the first place.
Actually, conversion from a regular expression to a NFA is IMHO much
easier, as is outlined in many textbooks (1). The size of a NFA is
usually much smaller (and for some cases, exponentially smaller) than
a DFA. The NFA which you get by following the method (1) is called the
Thompson NFA. On a computer, it might sometimes be more effective to
maintain a subset of states as a bit-vector as opposed to maintaining
a single state on a DFA with possibly exponential number of states.
This page outlines some aspects:
Return to the
Search the comp.compilers archives again.