🚀 go-pugleaf

Steve Morris (srm@matrix.com) wrote:

: >   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. 

You need understanding, not answers.  One of the main themes of
classical language and automata theory is to classify the power of
various grammar and machine models.  A beautiful theory has developed
that gives elegant characterizations of the capabilities and
limitations of these devices.  To see why {ww | w E {0,1}*} is not
regular, for example, you need to know about the pumping lemma for
regular sets and other techniques for proving non-regularity.  To see
why it is not accepted by a pushdown store machine, it is useful to
know about the connections between pushdown store machines and
context-free languages and to know about the pumping lemma for
context-free languages.  To see why it can be accepted by a Turing
machine, you need an understanding of the kinds of things Turing
machines can do and how they can do them.  If you read and understand
the Hopcroft and Ullman book, you won't need somebody else to furnish
solutions to the exercises for you.
==================================================
| Michael Fischer <fischer-michael@cs.yale.edu>  |
==================================================