Preface
The enlarged third edition of Thea/}' of Computer Science is the result of the
enthusiastic reception given to earlier editions of this book and the feedback
received from the students and teachers who used the second edition for
several years,
The new edition deals with all aspects of theoretical computer science,
namely automata, formal languages, computability and complexity, Very
few books combine all these theories and give/adequate examples. This book
provides numerous examples that illustrate the basic concepts. It is profusely
illustrated with diagrams. While dealing with theorems and algorithms, the
emphasis is on constructions. Each construction is immediately followed by an
example and only then the formal proof is given so that the student can master
the technique involved in the construction before taking up the formal proof.
The key feature of the book that sets it apart from other books is the
provision of detailed solutions (at the end of the book) to chapter-end
exercises.
The chapter on Propositions and Predicates (Chapter 10 of the second
edition) is now the first chapter in the new edition. The changes in other
chapters have been made without affecting the structure of the second edition.
The chapter on Turing machines (Chapter 7 of the second edition) has
undergone major changes.
A novel feature of the third edition is the addition of objective type
questions in each chapter under the heading Self-Test. This provides an
opportunity to the student to test whether he has fully grasped the fundamental
concepts. Besides, a total number of 83 additional solved examples have been
added as Supplementary Examples which enhance the variety of problems
dealt with in the book.
ix
http://engineeringbooks.net
The enlarged third edition of Thea/}' of Computer Science is the result of the
enthusiastic reception given to earlier editions of this book and the feedback
received from the students and teachers who used the second edition for
several years,
The new edition deals with all aspects of theoretical computer science,
namely automata, formal languages, computability and complexity, Very
few books combine all these theories and give/adequate examples. This book
provides numerous examples that illustrate the basic concepts. It is profusely
illustrated with diagrams. While dealing with theorems and algorithms, the
emphasis is on constructions. Each construction is immediately followed by an
example and only then the formal proof is given so that the student can master
the technique involved in the construction before taking up the formal proof.
The key feature of the book that sets it apart from other books is the
provision of detailed solutions (at the end of the book) to chapter-end
exercises.
The chapter on Propositions and Predicates (Chapter 10 of the second
edition) is now the first chapter in the new edition. The changes in other
chapters have been made without affecting the structure of the second edition.
The chapter on Turing machines (Chapter 7 of the second edition) has
undergone major changes.
A novel feature of the third edition is the addition of objective type
questions in each chapter under the heading Self-Test. This provides an
opportunity to the student to test whether he has fully grasped the fundamental
concepts. Besides, a total number of 83 additional solved examples have been
added as Supplementary Examples which enhance the variety of problems
dealt with in the book.
ix
http://engineeringbooks.net