2003-09-24 Good book for Theoretical Foundations of Computer Science

I'm an University student at Portugal (University of Algarve), and my Infinitesimal Math 3 course was replaced with the Theoretical Foundations of Computer Science course.
One of the advised books was this "Elements of the Theory of Computation" by H. R. Lewis e C. H. Papadimitriou, which isn't an easy book to the ones that don't like "abstractions". This book is about Math/Computer Science, with an high level of formalism, due to all the theorems and proofs, so it implies that you have some mathematical background and interest. This isn't a Programming book.

Some people say that this is an advanced book, not be given to undergraduate students, but the fact is that this is a course lectured in the 2nd year of my Computer Science - Teaching Branch degree, here in my University.

This book covers an introduction to Discrete Mathematics (sets, relations, strings, ...), Finite Automata ( regular expressions and languages ), Context-free Languages, Turing Machines, Uncomputability and the Halting Problem (undecidable problems), Computational Complexity and NP-Completeness.

One of the major problems of this book is the lack of suficient solved examples, precious to self learners like myself. Most authors forget this crucial aspect. I'm one of the persons that prefers to learn by example.

Other good alternatives to this book (they cover most of the same topics) are:

- "Automata and Formal Language" by Dean Kelley.
- "Introduction to the Theory of Computation" by M. Sipser
- "Introduction to Automata Theory, Languages and Computation" by J. E. Hopcroft, R. Motwani e J. D. Ullman

Elements of the Theory of Computation is a good book, but not a basic one. And it's target audience is very restricted. Surely not a "for dummies" like type.