Theory of Computer Science: Automata, Languages and Computation
This Third Edition, in response to the enthusiastic reception given by academia and students to the previous edition, offers a cohesive presentation of all aspects of theoretical computer science, namely automata, formal languages, computability, and complexity. Besides, it includes coverage of mathematical preliminaries. NEW TO THIS EDITION • Expanded sections on pigeonhole principle and the principle of induction (both in Chapter 2) • A rigorous proof of Kleene’s theorem (Chapter 5) • Major changes in the chapter on Turing machines (TMs) – A new section on high-level description of TMs – Techniques for the construction of TMs – Multitape TM and nondeterministic TM • A new chapter (Chapter 10) on decidability and recursively enumerable languages • A new chapter (Chapter 12) on complexity theory and NP-complete problems • A section on quantum computation in Chapter 12. • KEY FEATURES • Objective-type questions in each chapter—with answers provided at the end of the book. • Eighty-three additional solved examples—added as Supplementary Examples in each chapter. • Detailed solutions at the end of the book to chapter-end exercises. The book is designed to meet the needs of the undergraduate and postgraduate students of computer science and engineering as well as those of the students offering courses in computer applications.
What people are saying - Write a review
Other editions - View all
A-moves accepting algorithm automata basis for induction boolean expression Chapter concatenation construction context-free grammar context-free language context-sensitive corresponding defined by Table Definition denote derivation tree deterministic disjunctive normal form E L(G element equivalent grammar final finite automaton finite number formula given in Example grammar G graph halts Hence induction hypothesis input string input symbol integer Iqoi L(Gl leftmost derivation Let G LR(k Mealy machine Moore machine natural number NDFA nondeterministic Note NP-complete NP-complete problems number of a’s obtained output palindrome parsing polynomial predicate Premise primitive recursive functions Proof proposition prove pumping lemma pushdown R/W head recursively enumerable regular expression regular grammar regular set replaced represented sentence sentential form sequence simulate Solution Let subset substring tape symbols terminal string transition system Transition Table truth table truth value Turing machine variables vertex vertices