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

Vimal <j.vimal@gmail.com>
Thu, 16 Apr 2009 10:14:25 +0530

          From comp.compilers

Related articles
NFA->DFA - Why use epsilon transitions? alexander.morou@gmail.com (Alexander Morou) (2009-04-07)
Re: NFA->DFA - Why use epsilon transitions? sh006d3592@blueyonder.co.uk (Stephen Horne) (2009-04-13)
Re: NFA->DFA - Why use epsilon transitions? alexander.morou@gmail.com (2009-04-14)
Re: NFA->DFA - Why use epsilon transitions? torbenm@pc-003.diku.dk (2009-04-14)
Re: NFA->DFA - Why use epsilon transitions? j.vimal@gmail.com (Vimal) (2009-04-16)
| List of all articles for this month |

From: Vimal <j.vimal@gmail.com>
Newsgroups: comp.compilers
Date: Thu, 16 Apr 2009 10:14:25 +0530
Organization: Compilers Central
References: 09-04-011
Keywords: lex
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 <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



Post a followup to this message

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