Re: NFA to DFA

[jsa@organon.com (Jon S Anthony)]

In article <3199D093.41C67EA6@escmail.orl.mmc.com> "Theodore E. Dennison" <dennison@escmail.orl.mmc.com> writes:

> > > ARRAYS of boolean in a bitwise fashion. So why bother with some fancy
> > > generic ADT package (that might have bugs)?
> > 
> > Simple.  If the universe over which you can construct sets is "big",
> > but the sets themselves are typically not "so big" relative to the
> > universe (the cardinality of the compliment of any set >> cardinality
> > of the set - at least typically...) then the array of boolean impl.
> > offers poor quality of service (maybe not even plausible...).  Also,
> 
> What? You don't LIKE bit arrays that take up 1/8th of your virtual
> memory space?  :-)
> 
> O.K. But most Modula-2 compilers couldn't handle sets that large either.

I believe that the original "definition" of Modula-2 by Wirth had sets
being completely lame and virtually useless.  They had to fit within a
single "machine word".  To get sets that were actually useful (in
anything like a typical range of applications) you had to build your
own - i.e., build a set ADT.  Typically this was _implemented_ using
the basic set type.  This gave you a kind of poor-man's "equivalent" to
what you get in Ada with packed arrays of boolean for free.


> What you are describing is more of a list than a set. An ADT would be
> put to good use in making a list look like a set.

Well, I'm not really describing anything - not enough detail for that.
But, I am talking about a _set_ type - its implementation (whether by
lists or what have you) is not relevant.  That is why a set ADT makes
sense.  You can have the abstraction and the impl. can vary - as I
mentioned, in Ada95 it can even vary at runtime.

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com