[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: regex/fsa theory
From: |
Eray Ozkural |
Subject: |
Re: regex/fsa theory |
Date: |
Sun, 24 Mar 2002 01:30:42 +0200 |
-----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-----