Introduction to the Theory of Computation, Second Edition | Michael Sipser

Introduction to the Theory of Computation, Second Edition | Michael Sipser | Excellent presentation of the material

books:

Introduction to th...

	Introduction to the Theory of Computation, Second Edition Michael Sipser Course Technology, 2005 - 456 pages average customer review:based on 51 reviews view larger image
	for more information click here

highly recommended

This highly anticipated revision builds upon the strengths of the previous edition. Sipser's candid, crystal-clear style allows students at every level to understand and enjoy this field. His innovative "proof idea" sections explain profound concepts in plain English. The new edition incorporates many improvements students and professors have suggested over the years, and offers updated, classroom-tested problem sets at the end of each chapter.

My choice for textbook in my computation theory class

I recently encountered this book at a publisher's booth at a computer conference and read it on the ride back home. This morning I made a trip to the college bookstore and notified them that it is the textbook that I will be using in my computation theory class this spring.
The chapter titles are:

0) Introduction - this chapter contains the fundamental mathematical background of sets, functions, graphs and proofs. For most students, it could be skipped or skimmed.
1) Regular languages - this chapter is an introduction to deterministic and nondeterministic finite automata and regular expressions.
2) Context-free languages - an introduction to context-free grammars and pushdown automata.
3) The Church-Turing theses - an introduction to Turing machines and the variants, such as multiple tapes and nondeterministic Turing machines.
4) Decidability - the definition of decidability and how Turing machines and finite automata are used to prove or disprove if a language is decidable.
5) Reducibility - the definition of reducible and how Turing machines can be used to execute reductions.
6) The recursion theorem - an introduction to the recursion theorem and some applications to formal theories.
7) Time complexity - the first chapter in the coverage of algorithmic complexity, in this case execution time.
8) Space complexity - an examination of the complexity of algorithms from the perspective of the amount of memory required.
9) Intractability - an examination of the problems that can be solved in principle but not in practice.
10) Advanced topics in complexity theory - approximation algorithms, probabilistic algorithms, alternation, interactive proof systems, parallel computation and cryptography.

There is less coverage of grammars than most books, which is replaced by more in the area of algorithmic analysis. In my opinion, that is an appropriate tradeoff, the analysis of algorithms gives the students some understanding of how automata are applied in computer science.
Another excellent feature of this book is the solutions to selected exercises that appear at the end of the chapters. My estimate is that reasonably detailed solutions to approximately one-third of the problems are included. This allows the students to work extra problems by themselves, and helps the instructor if they are asked to do another example in class that they have not already worked through.
The exposition is very good; I am convinced that the students will be able to read the material on their own, which is one more reason why I adopted this book for my course.

for more information click here

Excellent presentation of the material

I would recommend this book to anyone looking to learn the basics of computation theory and formal languages or for someone looking to revisit this material after an absence.

The book is very readable and covers the basics in a systematic fashion. I haven't looked at this material since my university days, but found it very easy to read and digest.

Don't be afraid of the proofs

This is a great book. The topics are covered in a clear and interesting way. I came to this book after having been exposed to NFA's and DFA's in a compiler course and this exposition is much more enlightening. The proofs in this book are very well written in my opinion, very clear. Studying proof techniques in a book such as Solow's "How to Read and Do Proofs" will prepare you well to understand the proofs in this book.

for more information click here

A very nice book for undergraduates and graduates to understand computation theory.

I had read a few other books on automata, but I was not able to get clear notion about pumping lemmas, decidability and so on. However, when I read the 1st edition of this book, finally, I got those concepts. One of great things in this book is proof ideas. This book has very clear and concise explanations about proofs.
I bought 2nd edition of this book, since it has lots of solved problems and exercises. those solved problems will boost your understanding the text and they contains a few things you should know, but omitted in the text.
If you don't understand many concepts in automata and computability with other textbooks, I strongly recommend this book.

for more information click here