[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: regex/fsa theory

From: Bob Ham
Subject: Re: regex/fsa theory
Date: 11 Apr 2002 15:26:42 +0100

On Sat, 2002-03-23 at 23:30, Eray Ozkural wrote:

> > I'm doing an fsa minimiser using the (I assume) usual method of marking
> > pairs. But, I don't know if I should be including the epsilon closure
> > when checking which pairs are already marked.  I assume I should be,
> > given that what's at issue is whether or not the transitions make a
> > difference to the strings that are accepted, and the epsilon transitions
> > make such a difference.
> >
> Yes, you should be I think.
> But you are talking of two things. Converting an NFA to DFA, and minimizing a 
> DFA. So I think you're looking for an algorithm that translates an NFA to a 
> minimal DFA on the fly, that may be possible but I'm not sure where the 
> algorithm is written :) I suggest you to first go with a more conservative 
> approach.
> >
> > I don't believe I know the Cinderella book. I've got the Ullman crew's
> > Compilers and Martin's Introduction to Languages and Theory of
> > Computation.  Should I be adding one to that?
> - From Jargon File (4.3.0, 30 APR 2001) [jargon]:
>   Cinderella Book [CMU] n. "Introduction to Automata Theory, Languages,
>      and Computation", by John Hopcroft and Jeffrey Ullman, (Addison-Wesley,
>      1979). So called because the cover depicts a girl (putatively
>      Cinderella) sitting in front of a Rube Goldberg device and holding a
>      rope coming out of it. On the back cover, the device is in shambles
>      after she has (inevitably) pulled on the rope. See also {{book titles}}.
> The dragon book (compiler) you mention is somewhat more practical.  The 
> algorithm there minimizes a DFA for you, of course a DFA does not have 
> epsilon transitions :), so I suggest you to read section 3.9 more carefully.

My copy of the Cinderella book arrived his morning, finally.  After 5
minutes reading, I realise the problem.  I was using the marking-pairs
algorithm as described in Martin's book.  In that, it doesn't specify
whether or not it's for DFAs or NFAs, and it appears that for some
reason, I assumed it was for NFAs.  It's quite worrying that I got this
far without me or my tutor noticing this, but not much can be done about
it now, I guess.

Also, the book gives a nice clear description of the delta function for
NFAs with epsilon transitions: here's it's type signature:

delta := Q x (Sigma U {epsilon}) -> Q*

I was thinking that the epsilon didn't come in here, and the Q*
contained the results of an epsilon closure, which is not the case.

Luckily, this stuff shouldn't effect the code much; it just means that
my minimiser needs a few more functions.  Also, it looks as if I'll be
converting to a DFA in order to minimise it.  Luckily, the algorithm to
remove epsilon transitions, being very similar to subset-construction,
also converts to a DFA :)

Many thanks for the help,


Bob Ham: address@hidden  http://pkl.net/~node/

My music: http://mp3.com/obelisk_uk
GNU Hurd: http://hurd.gnu.org/

reply via email to

[Prev in Thread] Current Thread [Next in Thread]