Theory of Computer Science (Automata, Languages and Computation) Third Edition by K.L.P. Mishra and N. Chandrasekran pdf.
Theory of Computer Science (Automata, Languages and Computation) Third Edition free pdf download.
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 onesemester text by a judicious choice of the topics presented.
Download Theory of Computer Science (Automata, Languages and Computation) Third Edition in free pdf format.