From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,955fad43713fdf44
X-Google-Attributes: gid103376,public
From: JEAN CLAUDE GALLO <jean-claude.gallo@avions.aerospatiale.fr>
Subject: Re: NFA to DFA
Date: 1996/05/13
Message-ID: <31973BF5.41C67EA6@avions.aerospatiale.fr>#1/1
X-Deja-AN: 154572953
references: <4n1its$rtt@news2.h1.usa.pipeline.com>
content-type: text/plain; charset=us-ascii
organization: AEROSPATIALE AVIONS
mime-version: 1.0
newsgroups: comp.lang.ada
x-mailer: Mozilla 2.0 (X11; I; SunOS 4.1.3_U1 sun4m)
Date: 1996-05-13T00:00:00+00:00
List-Id: <comp.lang.ada>


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