home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / theory / 2915 < prev    next >
Encoding:
Text File  |  1993-01-23  |  1.6 KB  |  35 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!cs.utexas.edu!usc!ucla-cs!ucla-ma!sonia!aps
  3. From: aps@sonia.math.ucla.edu (Alexei Stolboushkin)
  4. Subject: Re: solution or information needed
  5. Message-ID: <1993Jan22.214830.26496@math.ucla.edu>
  6. Sender: news@math.ucla.edu
  7. Organization: UCLA Mathematics Department
  8. References: <1993Jan19.151627.21525@matrix.com> <1993Jan21.153028.7679@cs.yale.edu>
  9. Distribution: usa
  10. Date: Fri, 22 Jan 93 21:48:30 GMT
  11. Lines: 22
  12.  
  13. In article <1993Jan21.153028.7679@cs.yale.edu> fischer-michael@cs.yale.edu (Michael Fischer) writes:
  14.  
  15. ...
  16.  
  17. >You need understanding, not answers.  One of the main themes of
  18. >classical language and automata theory is to classify the power of
  19. >various grammar and machine models.  A beautiful theory has developed
  20. >that gives elegant characterizations of the capabilities and
  21. >limitations of these devices.  To see why {ww | w E {0,1}*} is not
  22. >regular, for example, you need to know about the pumping lemma for
  23. >regular sets and other techniques for proving non-regularity.  To see
  24. >why it is not accepted by a pushdown store machine, it is useful to
  25.      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  26. certainly it IS context-free, and therefore accepted by a PDA.
  27.  
  28. >know about the connections between pushdown store machines and
  29. >context-free languages and to know about the pumping lemma for
  30. >context-free languages.  To see why it can be accepted by a Turing
  31. >machine, you need an understanding of the kinds of things Turing
  32. >machines can do and how they can do them.  If you read and understand
  33. >the Hopcroft and Ullman book, you won't need somebody else to furnish
  34. >solutions to the exercises for you.
  35.