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 TECHNIQUESChapter 1: Basic Mathematical Objects Chapter 2: Mathematical Induction and Recursive Definitions PART II: REGULAR LANGUAGES AND FINITE AUTOMATAChapter 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 AUTOMATAChapter 6: Context-Free Grammars Chapter 7: Pushdown Automata Chapter 8: Context-Free and Non-Context- Free Languages PART IV: TURING MACHINES AND THEIR LANGUAGESChapter 9: Turning Machines Chapter 10: Recursively Enumerable Languages PART V: UNSOLVABLE PROBLEMS AND COMPUTABLE FUNCTIONSChapter 11: Unsolved Problems Chapter 12: Computable Functions PART VI: INTRODUCTION AND CLASSIFYING COMPLEXITYChapter 13: Measuring and Classifying Complexity Chapter 14: Tractable and Intractable Problems References Bibliography Index of Notation Index |