🚀 go-pugleaf

In article <1993Jan19.151627.21525@matrix.com>, srm@matrix.com (Steve Morris) writes:
>
>>   Does anybody have the solutions to the exercises in the classic
>>computer theory book?  "Introduction to automata theory, languages, and
>>computation" by Hopcroft and Ullman in 1979.  If you have any, please
>>post your reply or send it to me by e-mail.  Thank you.
>
>I'm in a situation where some answers would be very helpful. I'm
>applying to the Comp. Sci. master's program at the local university. I
>have to take the Comp. Sci. GRE also. (I have a BSEE.) I'm having
>trouble with some of the theory of computation questions... such as
>the following from one of the GRE practice books:
>
>	The language {ww|w E (0 + 1)*} is
>
>	(A) not accepted by any Turing machine
>	(B) accepted by some Turing machines, but by no pushdown automata
>	(C) accepted by some pushdown automaton, but not context-free
>	(D) context-free, but not regular
>	(E) regular
>
>The practice book gives answers but not explanations. So I'm
>wondering, why is (B) the answer? I guessed (E).
>
>I've been "reading" Brookshear's _Theory of Computation_ and Linz's
>_Introduction to Formal Languages and Automata_. Having the solutions
>to the problems in these texts would greatly increase my
>understanding.  (These texts are NOT used for the undergrad course
>here. I believe they use a book by Martin.)
>
>Thanks for any help.

   I recently took the CS GREs, and questions like this do not seem to
be as prevalent.   While I won't say the entire test is easy, because
it's not, they do seem to have made somewhat more reasonable questions.

   The reason it's not regular is that you have the repetition of the "w" twice.
If it were just (0 + 1)*, it would be regular.   The repetition essentially means
that somehow the finite state machine would have to recall the phrase "w".  Since
"w" can be potentially infinite, and since an FSA only has finite states, then an
FSA won't do.   Unlike a Turning machine, which can move the tape, an FSA has to
process the input string in the order it is given.  Any other information has to
be recorded by state.
    
    Why can't in be a pushdown automata?  A pushdown automata remebers strings
that are palindromes.  So, ww^{R}, or w, and the reverse of w, could be
figured out by a pushdown automata, since you just push down the elements of w,
and pop them up at the halfway point.   Actually, that's not true.  It
would have to be a non-deterministic pushdown because a deterministic one never
knows that it has reached halfway.   A non-deterministic one can have a rule
that pops the stack at any point, and so one of those will be the halfway
marker, and it will recognize it.   Since ww does not have this palindrome
like characteristic, then pushdowns don't work.   However, matching parentheses
do work.

    Finally, a Turing machine can solve it.   How might you do this?   
Assume you have an infinite tape that is filled with B's, and 1's and 0's.
The tape starts at position 0 (the positions numbered from -infinity to
+ infinity) and has a length, l.   Now pretend that you have the following
tape symbols.   0Z, 1Z, 0A, 1A, 0B, 1B, and B.   Suppose you want to
find out if 0 1 0 0 1 0 should be accepted by the Turing machine (this should
work).  Then, have the tape originally read 0Z 1Z 0Z 0Z 1Z 0Z.   We start
the machine at the leftmost 0Z.  Make it a 0Z.  Now move right until you
see either a B, a 1B, or a 0B.   The first time, you will see a B (when you
get past the rightmost 0Z).  Move left (changes state).  Change the 0Z to
a 0B.  Make sure that it is a 0Z or a 1Z before doing this.   You then get
B 0A 1Z 0Z 0Z 1Z 0B B.   OK, noe move left until you encounter a 0A, or
an 1A.  Move right.   Change that to a 1A.   And so forth.   You eventully
get


             B  0 1 0 0 1 0 B
                A A A B B B

   The intuitive idea is start at the left, and mark the box with A, go
to the far right, mark it with a B, go to the next left, mark it with an
A, go to the next far right, mark it with a B.   So basically, this has
made even set of A's, and B's.   Now, start at the leftmost point, the
0A, change that to a OJ.   Go to the first mark with a B.  If it matches
the number ), change it to a 0J as well.   Essentially, you will match letter
by letter, going back and forth.

   Unfortunately, I can't think of a more rigorous answer to your question.
Unless you've played around with writing stuff for Turing machines, it
can be a little difficult to get some of the tricks to manipulate them.

   In any case, good luck.

				-- Charles