This is a book about Theory of Computer Science and it is a free ebook just for you. If you want to about Theory of Computer Science then you are at the right place. You can download this ebook with no cost just only from here. You can read this ebook online here. So let us read altogether and download it.
Preface of this Book
The enlarged third edition of Theory 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.
The sections on pigeonhole principle and the principle of induction (both in Chapter 2) have been expanded. In Chapter 5, a rigorous proof of Kleene's theorem has been included. The chapter on LR(k) grammars remains the same Chapter 8 as in the second edition.
Chapter 9 focuses on the treatment of Turing machines (TMs). A new section on high-level description of TM has been added and this is used in later examples and proofs. Some techniques for the construction of TMs have been added in Section 9.6. The multitape Turing machine and the nondeterministic Turing machine are discussed in Section 9.7.
A new chapter (Chapter 10) on decidability and recursively enumerable languages is included in this third edition. In the previous edition only a sketchy introduction to these concepts was given. Some examples of recursively enumerable languages are given in Section 10.3 and undecidable languages are discussed in Section lOA. The halting problem of TM is
discussed in Section 10.5. Chapter 11 on computability is Chapter 9 of the previous edition without changes.
Chapter 12 is a new chapter on complexity theory and NP-complete problems. Cook's theorem is proved in detail. A section on Quantum Computation is added as the last section in this chapter. Although this topic
does not fall under the purview of theoretical computer science, this section
is added with a view to indicating how the success of Quantum Computers will lead to dramatic changes in complexity theory in the future.
The book fulfils the curriculum needs of undergraduate and postgraduate students of computer science and engineering as well as those of MCA courses. Though designed for a one-year course, the book can be used as a one semester text by a judicious choice of the topics presented.
Special thanks go to all the teachers and students who patronized this book over the years and offered helpful suggestions that have led to this new edition. In particular, the critical comments of Prof. M. Umaparvathi, Professor of Mathematics, Seethalakshmi College, Tiruchirapalli are gratefully acknowledged.
Finally. the receipt of suggestions, comments and error reports for further
improvement of the book would be welcomed and duly acknowledged.
