home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / theory / 2912 < prev    next >
Encoding:
Internet Message Format  |  1993-01-22  |  5.0 KB
  1. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!mojo.eng.umd.edu!clin
  2. From: clin@eng.umd.edu (Charles C. Lin)
  3. Newsgroups: comp.theory
  4. Subject: Re: solution or information needed
  5. Date: 22 Jan 1993 10:00:47 GMT
  6. Organization: College of Engineering, Maryversity von Uniland, College Park
  7. Lines: 91
  8. Distribution: usa
  9. Message-ID: <1jogkfINNhil@mojo.eng.umd.edu>
  10. References: <1993Jan19.151627.21525@matrix.com>
  11. NNTP-Posting-Host: state.eng.umd.edu
  12. Originator: clin@state.eng.umd.edu
  13.  
  14.  
  15. In article <1993Jan19.151627.21525@matrix.com>, srm@matrix.com (Steve Morris) writes:
  16. >
  17. >>   Does anybody have the solutions to the exercises in the classic
  18. >>computer theory book?  "Introduction to automata theory, languages, and
  19. >>computation" by Hopcroft and Ullman in 1979.  If you have any, please
  20. >>post your reply or send it to me by e-mail.  Thank you.
  21. >
  22. >I'm in a situation where some answers would be very helpful. I'm
  23. >applying to the Comp. Sci. master's program at the local university. I
  24. >have to take the Comp. Sci. GRE also. (I have a BSEE.) I'm having
  25. >trouble with some of the theory of computation questions... such as
  26. >the following from one of the GRE practice books:
  27. >
  28. >    The language {ww|w E (0 + 1)*} is
  29. >
  30. >    (A) not accepted by any Turing machine
  31. >    (B) accepted by some Turing machines, but by no pushdown automata
  32. >    (C) accepted by some pushdown automaton, but not context-free
  33. >    (D) context-free, but not regular
  34. >    (E) regular
  35. >
  36. >The practice book gives answers but not explanations. So I'm
  37. >wondering, why is (B) the answer? I guessed (E).
  38. >
  39. >I've been "reading" Brookshear's _Theory of Computation_ and Linz's
  40. >_Introduction to Formal Languages and Automata_. Having the solutions
  41. >to the problems in these texts would greatly increase my
  42. >understanding.  (These texts are NOT used for the undergrad course
  43. >here. I believe they use a book by Martin.)
  44. >
  45. >Thanks for any help.
  46.  
  47.    I recently took the CS GREs, and questions like this do not seem to
  48. be as prevalent.   While I won't say the entire test is easy, because
  49. it's not, they do seem to have made somewhat more reasonable questions.
  50.  
  51.    The reason it's not regular is that you have the repetition of the "w" twice.
  52. If it were just (0 + 1)*, it would be regular.   The repetition essentially means
  53. that somehow the finite state machine would have to recall the phrase "w".  Since
  54. "w" can be potentially infinite, and since an FSA only has finite states, then an
  55. FSA won't do.   Unlike a Turning machine, which can move the tape, an FSA has to
  56. process the input string in the order it is given.  Any other information has to
  57. be recorded by state.
  58.     
  59.     Why can't in be a pushdown automata?  A pushdown automata remebers strings
  60. that are palindromes.  So, ww^{R}, or w, and the reverse of w, could be
  61. figured out by a pushdown automata, since you just push down the elements of w,
  62. and pop them up at the halfway point.   Actually, that's not true.  It
  63. would have to be a non-deterministic pushdown because a deterministic one never
  64. knows that it has reached halfway.   A non-deterministic one can have a rule
  65. that pops the stack at any point, and so one of those will be the halfway
  66. marker, and it will recognize it.   Since ww does not have this palindrome
  67. like characteristic, then pushdowns don't work.   However, matching parentheses
  68. do work.
  69.  
  70.     Finally, a Turing machine can solve it.   How might you do this?   
  71. Assume you have an infinite tape that is filled with B's, and 1's and 0's.
  72. The tape starts at position 0 (the positions numbered from -infinity to
  73. + infinity) and has a length, l.   Now pretend that you have the following
  74. tape symbols.   0Z, 1Z, 0A, 1A, 0B, 1B, and B.   Suppose you want to
  75. find out if 0 1 0 0 1 0 should be accepted by the Turing machine (this should
  76. work).  Then, have the tape originally read 0Z 1Z 0Z 0Z 1Z 0Z.   We start
  77. the machine at the leftmost 0Z.  Make it a 0Z.  Now move right until you
  78. see either a B, a 1B, or a 0B.   The first time, you will see a B (when you
  79. get past the rightmost 0Z).  Move left (changes state).  Change the 0Z to
  80. a 0B.  Make sure that it is a 0Z or a 1Z before doing this.   You then get
  81. B 0A 1Z 0Z 0Z 1Z 0B B.   OK, noe move left until you encounter a 0A, or
  82. an 1A.  Move right.   Change that to a 1A.   And so forth.   You eventully
  83. get
  84.  
  85.  
  86.              B  0 1 0 0 1 0 B
  87.                 A A A B B B
  88.  
  89.    The intuitive idea is start at the left, and mark the box with A, go
  90. to the far right, mark it with a B, go to the next left, mark it with an
  91. A, go to the next far right, mark it with a B.   So basically, this has
  92. made even set of A's, and B's.   Now, start at the leftmost point, the
  93. 0A, change that to a OJ.   Go to the first mark with a B.  If it matches
  94. the number ), change it to a 0J as well.   Essentially, you will match letter
  95. by letter, going back and forth.
  96.  
  97.    Unfortunately, I can't think of a more rigorous answer to your question.
  98. Unless you've played around with writing stuff for Turing machines, it
  99. can be a little difficult to get some of the tricks to manipulate them.
  100.  
  101.    In any case, good luck.
  102.  
  103.                 -- Charles
  104.  
  105.