Table of contents Preface
Introduction
Part 1: Mathematical Notation and Techniques
Chapter 1: Basic Mathematical Objects
Chapter 2: Mathematical Induction and Recursive Definitions
Part II: Regular Languages and Finite Automata
Chapter 3: Regular Expressions and Finite Automata
Chapter 4: Nondeterminism and Kleene?s Theorem
Chapter 5: Regular and Nonregular Languages
Part III: Context- Free Languages and Pushdown Automata
Chapter 6: Context-Free Grammars
Chapter 7: Pushdown Automata
Chapter 8: Context-Free and Non-Context- Free Languages
Part IV: Turing Machines and Their Languages
Chapter 9: Turning Machines
Chapter 10: Recursively Enumerable Languages
Part V: Unsolvable Problems and Computable Functions
Chapter 11: Unsolved Problems
Chapter 12: Computable Functions
Part VI: Introduction and Classifying Complexity
Chapter 13: Measuring and Classifying Complexity
Chapter 14: Tractable and Intractable Problems
References
Bibliography
Index of Notation
Index
New Features
? Offers a gentle and gradual introduction of the necessary mathematical tools in the context in which they are used.
? Emphasizes on formal languages, automata and abstract models of computation, and computability, and it includes an introduction to computational complexity and NP-completeness.
? Martin offers an enormous number and variety of exercises.
? Solved Exercises-114
? Unsolved Exercises-440
? More challenging Problems-226