Re: regex/fsa theory

[Eray Ozkural]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Saturday 23 March 2002 16:39, Bob Ham wrote:
> On Fri, 2002-03-22 at 00:44, Eray Ozkural wrote:
> > What do you want to do?
>
> 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.

Best Regards,

- -- 
Eray Ozkural (exa) <address@hidden>
Comp. Sci. Dept., Bilkent University, Ankara
www: http://www.cs.bilkent.edu.tr/~erayo
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE8nRAkfAeuFodNU5wRAultAJ9iIDtDVRPGfQDqx8RjS1zbhFxmvgCfcRke
9+M9buyqAeQbGqyNPedtrr4=
=IzRS
-----END PGP SIGNATURE-----