[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
--
Bob Ham: address@hidden http://pkl.net/~node/
My music: http://mp3.com/obelisk_uk
GNU Hurd: http://hurd.gnu.org/
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- Re: regex/fsa theory,
Bob Ham <=