Theory of computer science: automata, languages and computation

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.