home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / theory / 2911 next >
Encoding:
Text File  |  1993-01-21  |  2.1 KB  |  43 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!spool.mu.edu!yale.edu!yale!cs.yale.edu!ginkgo.theory.cs.yale.edu!fischer
  3. From: fischer-michael@cs.yale.edu (Michael Fischer)
  4. Subject: Re: solution or information needed
  5. Message-ID: <1993Jan21.153028.7679@cs.yale.edu>
  6. Sender: news@cs.yale.edu (Usenet News)
  7. Nntp-Posting-Host: ginkgo.theory.cs.yale.edu
  8. Reply-To: fischer-michael@cs.yale.edu (Michael Fischer)
  9. Organization: Yale University Computer Science Dept., New Haven, CT 06520-2158
  10. X-Newsreader: TIN [version 1.1az (for az) PL8]
  11. References: <1993Jan19.151627.21525@matrix.com>
  12. Distribution: usa
  13. Date: Thu, 21 Jan 1993 15:30:28 GMT
  14. Lines: 27
  15.  
  16. Steve Morris (srm@matrix.com) wrote:
  17.  
  18. : >   Does anybody have the solutions to the exercises in the classic
  19. : >computer theory book?  "Introduction to automata theory, languages, and
  20. : >computation" by Hopcroft and Ullman in 1979.  If you have any, please
  21. : >post your reply or send it to me by e-mail.  Thank you.
  22.  
  23. : I'm in a situation where some answers would be very helpful. 
  24.  
  25. You need understanding, not answers.  One of the main themes of
  26. classical language and automata theory is to classify the power of
  27. various grammar and machine models.  A beautiful theory has developed
  28. that gives elegant characterizations of the capabilities and
  29. limitations of these devices.  To see why {ww | w E {0,1}*} is not
  30. regular, for example, you need to know about the pumping lemma for
  31. regular sets and other techniques for proving non-regularity.  To see
  32. why it is not accepted by a pushdown store machine, it is useful to
  33. know about the connections between pushdown store machines and
  34. context-free languages and to know about the pumping lemma for
  35. context-free languages.  To see why it can be accepted by a Turing
  36. machine, you need an understanding of the kinds of things Turing
  37. machines can do and how they can do them.  If you read and understand
  38. the Hopcroft and Ullman book, you won't need somebody else to furnish
  39. solutions to the exercises for you.
  40. ==================================================
  41. | Michael Fischer <fischer-michael@cs.yale.edu>  |
  42. ==================================================
  43.