NFA to DFA

NFA to DFA

[Boaz Chow]

do you know how to implement SET adt and the operations in Ada? 
 
I have this project that requires me to check if a pattern is in a given
string by converting NFA to DFA. 
 
for example : 
 
abcd is in the string difjdabcddkjf 
 
I have done this with a short cut (i.e. I've done this without using SET) 
 
but that's only the first part.  the second part requires me to write a
program that generates another program (a source code) that implement the
operation for transfering a NFA to a DFA.  This I need SET!  ADA does not
have SET!!! 
 
I have tried to use an array to implement set but that gives me a big
problem. 
 
any idea on what the best way to implement SET? 
-- 
   ______   Meow 
   \ OO /  _/  
  :(__ =) 
    U \\ 
 
http://www.sci.csupomona.edu/~cchow 

Re: NFA to DFA

[JEAN CLAUDE GALLO]

Boaz Chow wrote:
> 
> do you know how to implement SET adt and the operations in Ada?
> 
> I have this project that requires me to check if a pattern is in a given
> string by converting NFA to DFA.
> 
> for example :
> 
> abcd is in the string difjdabcddkjf
> 
> I have done this with a short cut (i.e. I've done this without using SET)
> 
> but that's only the first part.  the second part requires me to write a
> program that generates another program (a source code) that implement the
> operation for transfering a NFA to a DFA.  This I need SET!  ADA does not
> have SET!!!
> 
> I have tried to use an array to implement set but that gives me a big
> problem.
> 
> any idea on what the best way to implement SET?
> --
>    ______   Meow
>    \ OO /  _/
>   :(__ =)
>     U \\
> 
> http://www.sci.csupomona.edu/~cchow


generic packages
You may found examples of SETS in "Software Components with Ada"
(G.Booch). He explain theory of Set algorithm and Ada83 generic packages
examples. See a
lso 'Data Structures and Algorithms' by Aho, Ullman and Hopcroft who
gave useful explanation of Sets theroy.

There after is the specification of the abstract data type
Set_Simple_Sequential_Bounded_Managed_Iterator package from Booch. This
is the bounded form, the data structure supporting the set abstraction
is a static array, with an iterator to traverse the sets. 


generic
    type Item is private;
package Set_Simple_Sequential_Bounded_Managed_Iterator is
    type Set (The_Size : Positive) is limited private;

    procedure Copy	    (From_The_Set : in     Set;
                             To_The_Set   : in out Set);
    procedure Clear	    (The_Set      : in out Set);
    procedure Add	    (The_Item     : in     Item;
                             To_The_Set   : in out Set);
    procedure Remove	    (The_Item     : in     Item;
                             From_The_Set : in out Set);
    procedure Union	    (Of_The_Set   : in     Set;
                             And_The_Set  : in     Set;
                             To_The_Set   : in out Set);
    procedure Intersection  (Of_The_Set   : in     Set;
                             And_The_Set  : in     Set;
                             To_The_Set   : in out Set);
    procedure Difference    (Of_The_Set   : in     Set;
                             And_The_Set  : in     Set;
                             To_The_Set   : in out Set);

    function Is_Equal		(Left	    : in Set;
                                 Right	    : in Set) return Boolean;
    function Extent_Of          (The_Set    : in Set) return Natural;
    function Is_Empty           (The_Set    : in Set) return Boolean;
    function Is_A_Member	(The_Item   : in Item;
                                 Of_The_Set : in Set) return Boolean;
    function Is_A_Subset	(Left	    : in Set;
                                 Right	    : in Set) return Boolean;
    function Is_A_Proper_Subset	(Left	    : in Set;
                                 Right	    : in Set) return Boolean;

    generic
    	with procedure Process (The_Item : in Item;
                                Continue : out Boolean);
    procedure Iterate (Over_The_Set : in Set);

    Overflow           : exception;
    Item_Is_In_Set     : exception;
    Item_Is_Not_In_Set : exception;


private
    type Items is array(Positive range <>) of Item;
    type Set(The_Size : Positive) is
	record
	    The_Back  : Natural := 0;
	    The_Items : Items(1 .. The_Size);
	end record;

end Set_Simple_Sequential_Bounded_Managed_Iterator;

You can instanciate this package for characters, declare two sets
variables, one containing {a,b,c,d} and one containing {d,i,j,a,b,c,k,f}
and then compute the intersection between sets (the mathematical set
concept avoid duplicated items).

If you need more, for example the body of that example, you can e-mail
to me at jean-claude.gallo@avions.aerospatiale.fr

jean claude Gallo

Re: NFA to DFA

[Theodore E. Dennison]

JEAN CLAUDE GALLO wrote:
> 
> Boaz Chow wrote:
> >
> > do you know how to implement SET adt and the operations in Ada?
> >
> 
> generic packages
> You may found examples of SETS in "Software Components with Ada"
> (G.Booch). He explain theory of Set algorithm and Ada83 generic packages

Being an old Modula-2 programmer (where Sets are basic structure types,
like records), I have several times sat down to implement a generic
SET ADT package. Every time, I have discovered that arrays of boolean
give me exactly what I want with one simple type declaration. This
is because Ada defines the boolean operators AND and OR to work on 
ARRAYS of boolean in a bitwise fashion. So why bother with some fancy
generic ADT package (that might have bugs)?
   
-- 
T.E.D.          
                |  Work - mailto:dennison@escmail.orl.mmc.com  |
                |  Home - mailto:dennison@iag.net              |
                |  URL  - http://www.iag.net/~dennison         |

Re: NFA to DFA

[Jon S Anthony]

In article <31987C20.167EB0E7@escmail.orl.mmc.com> "Theodore E. Dennison" <dennison@escmail.orl.mmc.com> writes:

> Being an old Modula-2 programmer (where Sets are basic structure types,
> like records), I have several times sat down to implement a generic
> SET ADT package. Every time, I have discovered that arrays of boolean
> give me exactly what I want with one simple type declaration. This
> is because Ada defines the boolean operators AND and OR to work on 
> 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,
in Ada95, another reason is to allow a kind of dynamic QOS based on
universe size.  I suppose this latter wouldn't be so much "generic"
as "abstract".

Lest you think this is not very plausible to occur ("too big" universe),
just think of "wide characters".

/Jon

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

617.484.3383
jsa@organon.com

Re: NFA to DFA

[Theodore E. Dennison]

Jon S Anthony wrote:
> 
> In article <31987C20.167EB0E7@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.
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.

-- 
T.E.D.          
                |  Work - mailto:dennison@escmail.orl.mmc.com  |
                |  Home - mailto:dennison@iag.net              |
                |  URL  - http://www.iag.net/~dennison         |

Re: NFA to DFA

[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

Data Structures as ADTs (was: NFA to DFA)

[Matthew Heaney]

In article <31987C20.167EB0E7@escmail.orl.mmc.com>, "Theodore E. Dennison"
<dennison@escmail.orl.mmc.com> wrote:

>JEAN CLAUDE GALLO wrote:
>> 
>> Boaz Chow wrote:
>> >
>> > do you know how to implement SET adt and the operations in Ada?
>> >
>> 
>> generic packages
>> You may found examples of SETS in "Software Components with Ada"
>> (G.Booch). He explain theory of Set algorithm and Ada83 generic packages
>
>Being an old Modula-2 programmer (where Sets are basic structure types,
>like records), I have several times sat down to implement a generic
>SET ADT package. Every time, I have discovered that arrays of boolean
>give me exactly what I want with one simple type declaration. This
>is because Ada defines the boolean operators AND and OR to work on 
>ARRAYS of boolean in a bitwise fashion. So why bother with some fancy
>generic ADT package (that might have bugs)?

Well, then, why bother with abstraction at all?  Why even bother programming 
in a language that offers direct support for programmer-defined abstractions?

The whole point is that an abstract data type hides inessential information
from the complexity-challanged human programmer.

Indeed, the whole purpose of "software engineering" is to figure out what
tools humans need to build large, complex systems constructed from
software.  Abstract data types are in fact one of those tools; witness the
popularity of object-oriented programming.

There's a hidden assumption in the statement that "some fancy  ADT package might
have bugs": that you could do it some other way, not using an ADT, and
have fewer bugs.

But just the opposite is true: not only will the system you build without
using ASTs have more bugs, you might very well fail to get the system even
built!

Time and time again I've seen programmers use an array as a data structure, when
they should have been using an abstract data type.  You have to consider
much more
state information when manipulating arrays than you do when manipulating a
higher-level (more abstract) structure, so the likelihood of an error is
much, much greater.

If you don't believe me, then read

   Data Structured Programming: Program Design without Arrays and Pointers
   Harlan D. Mills and Richard C. Linger
   IEEE Transactions on Software Engineering, Vol SE-12, No 2, Feb 1986

  On the Criteria To Be Used In Decomposing Systems into Modules
   D.L. Parnas
   Communications of the ACM, Dec 1972

and while you're at it, be sure to read

   The Magical Number Seven, Plus or Minus Two: 
    Some Limits on Our Capacity for Processing Information
   G.A. Miller
   The Psychological Review, 1956


Booch specifically includes a form for discrete types, which is *implemented*
as you suggested: as an array of Booleans.  See the discussion of The
Discrete Form
in Chapter 10, Sets and Bags, of his book Software Components with Ada.

The rule is: Never use an array, or a linked list for that matter, as a
data structure; they
are much too primitive.  Use an array or linked list only to *implement*
data structures that are abstract data types.

Now ya know!

Matt

--------------------------------------------------------------------
Matthew Heaney                       Estormza Software
Software Development Consultant      4765 Bellflower Ave F
mheaney@ni.net                       North Hollywood CA 91602
                                     (818) 985-1271

Re: Data Structures as ADTs (was: NFA to DFA)

[Theodore E. Dennison]

Matthew Heaney wrote:
> 
> In article <31987C20.167EB0E7@escmail.orl.mmc.com>, "Theodore E. Dennison"
> <dennison@escmail.orl.mmc.com> wrote:
> 
> >JEAN CLAUDE GALLO wrote:
> >>
> >> Boaz Chow wrote:
> >> >
> >> > do you know how to implement SET adt and the operations in Ada?
> >> >
> >>
> >> generic packages
> >> You may found examples of SETS in "Software Components with Ada"
> >> (G.Booch). He explain theory of Set algorithm and Ada83 generic packages
> >
> >give me exactly what I want with one simple type declaration. This
> >is because Ada defines the boolean operators AND and OR to work on
> >ARRAYS of boolean in a bitwise fashion. So why bother with some fancy
> >generic ADT package (that might have bugs)?
> 
> Well, then, why bother with abstraction at all?  Why even bother programming
> in a language that offers direct support for programmer-defined abstractions?
> 

I suppose I could take this silly argument to the other extreme: 
Pretend you have convinced me and suggest that all built-in types
are useless and that only a moron would use Integer or Natural for
array indexes when he could use a generic ADT named 
Sequential_Bounded_Unmanaged_Incrementable_Mathematical_Intgeral,
but I don't really have the energy today.

It's not like your SPARC chip knows what a boolean array is. A boolean
array IS AN ABSTRACTION. And it is an abstraction that happens to come
with all the operations needed of sets. (Hint: this was NOT by accident)

If it makes you feel better, here's an abstraction for you:

type Set is array (Possibilities) of Boolean;
function Union (Left : in Set; Right : in Set) renames "OR";
function Intersection (Left : in Set; Right : in Set) renames "AND";

Have a blast.

-- 
T.E.D.          
                |  Work - mailto:dennison@escmail.orl.mmc.com  |
                |  Home - mailto:dennison@iag.net              |
                |  URL  - http://www.iag.net/~dennison         |