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

I would like to add the following point to Stephen Horne's list.


2009/4/7 Alexander Morou <alexander.morou@gmail.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:


http://swtch.com/~rsc/regexp/regexp1.html


--
Vimal

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