* NFA to DFA @ 1996-05-11 0:00 Boaz Chow 1996-05-13 0:00 ` JEAN CLAUDE GALLO ` (3 more replies) 0 siblings, 4 replies; 8+ messages in thread From: Boaz Chow @ 1996-05-11 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: NFA to DFA 1996-05-11 0:00 NFA to DFA Boaz Chow @ 1996-05-13 0:00 ` JEAN CLAUDE GALLO 1996-05-14 0:00 ` Theodore E. Dennison 1996-05-14 0:00 ` NFA to DFA Jon S Anthony ` (2 subsequent siblings) 3 siblings, 1 reply; 8+ messages in thread From: JEAN CLAUDE GALLO @ 1996-05-13 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: NFA to DFA 1996-05-13 0:00 ` JEAN CLAUDE GALLO @ 1996-05-14 0:00 ` Theodore E. Dennison 1996-05-16 0:00 ` Data Structures as ADTs (was: NFA to DFA) Matthew Heaney 0 siblings, 1 reply; 8+ messages in thread From: Theodore E. Dennison @ 1996-05-14 0:00 UTC (permalink / raw) 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 | ^ permalink raw reply [flat|nested] 8+ messages in thread
* Data Structures as ADTs (was: NFA to DFA) 1996-05-14 0:00 ` Theodore E. Dennison @ 1996-05-16 0:00 ` Matthew Heaney 1996-05-16 0:00 ` Theodore E. Dennison 0 siblings, 1 reply; 8+ messages in thread From: Matthew Heaney @ 1996-05-16 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Data Structures as ADTs (was: NFA to DFA) 1996-05-16 0:00 ` Data Structures as ADTs (was: NFA to DFA) Matthew Heaney @ 1996-05-16 0:00 ` Theodore E. Dennison 0 siblings, 0 replies; 8+ messages in thread From: Theodore E. Dennison @ 1996-05-16 0:00 UTC (permalink / raw) 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 | ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: NFA to DFA 1996-05-11 0:00 NFA to DFA Boaz Chow 1996-05-13 0:00 ` JEAN CLAUDE GALLO @ 1996-05-14 0:00 ` Jon S Anthony 1996-05-15 0:00 ` Theodore E. Dennison 1996-05-15 0:00 ` Jon S Anthony 3 siblings, 0 replies; 8+ messages in thread From: Jon S Anthony @ 1996-05-14 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: NFA to DFA 1996-05-11 0:00 NFA to DFA Boaz Chow 1996-05-13 0:00 ` JEAN CLAUDE GALLO 1996-05-14 0:00 ` NFA to DFA Jon S Anthony @ 1996-05-15 0:00 ` Theodore E. Dennison 1996-05-15 0:00 ` Jon S Anthony 3 siblings, 0 replies; 8+ messages in thread From: Theodore E. Dennison @ 1996-05-15 0:00 UTC (permalink / raw) 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 | ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: NFA to DFA 1996-05-11 0:00 NFA to DFA Boaz Chow ` (2 preceding siblings ...) 1996-05-15 0:00 ` Theodore E. Dennison @ 1996-05-15 0:00 ` Jon S Anthony 3 siblings, 0 replies; 8+ messages in thread From: Jon S Anthony @ 1996-05-15 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~1996-05-16 0:00 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 1996-05-11 0:00 NFA to DFA Boaz Chow 1996-05-13 0:00 ` JEAN CLAUDE GALLO 1996-05-14 0:00 ` Theodore E. Dennison 1996-05-16 0:00 ` Data Structures as ADTs (was: NFA to DFA) Matthew Heaney 1996-05-16 0:00 ` Theodore E. Dennison 1996-05-14 0:00 ` NFA to DFA Jon S Anthony 1996-05-15 0:00 ` Theodore E. Dennison 1996-05-15 0:00 ` Jon S Anthony
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox