Re: NFA to DFA

[JEAN CLAUDE GALLO <jean-claude.gallo@avions.aerospatiale.fr>]

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