home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / theory / 2933 < prev    next >
Encoding:
Internet Message Format  |  1993-01-27  |  1.3 KB
  1. Path: sparky!uunet!idacrd!desj@ccr-p.ida.org
  2. From: desj@ccr-p.ida.org (David desJardins)
  3. Newsgroups: comp.theory
  4. Subject: Re: solution or information needed
  5. Message-ID: <1852@idacrd.UUCP>
  6. Date: 28 Jan 93 01:01:23 GMT
  7. References: <1993Jan19.151627.21525@matrix.com> <1jogkfINNhil@mojo.eng.umd.edu>
  8. Sender: desj@idacrd.UUCP
  9. Organization: IDA Center for Communications Research, Princeton
  10. Lines: 19
  11.  
  12. Charles C. Lin <clin@eng.umd.edu> writes:
  13. >>    The language {ww|w E (0 + 1)*} is
  14. >>    (A) not accepted by any Turing machine
  15. >>    (B) accepted by some Turing machines, but by no pushdown automata
  16. >>    (C) accepted by some pushdown automaton, but not context-free
  17. >>    (D) context-free, but not regular
  18. >>    (E) regular
  19.  
  20. > I recently took the CS GREs, and questions like this do not seem to
  21. > be as prevalent.   While I won't say the entire test is easy, because
  22. > it's not, they do seem to have made somewhat more reasonable questions.
  23.  
  24. Does any other reader of this newsgroup want to defend the proposition
  25. that this is an "unreasonable" question??  This is about the easiest
  26. nontrivial question one could pose on the theory of computation; either
  27. this question is perfectly reasonable, or there is no need for theory,
  28. and thus for this newsgroup.
  29.  
  30.                                         David desJardins
  31.