| Introduction | |
Introduction to Languages and the Theory of Computation is a highly popular text which provides an introduction to the theory of computation emphasizing on formal languages, automata and abstract models of computation, and computability; it also includes an introduction to computational complexity and NP-completeness. | |
| Key features | |
| 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 | |
