About Book

"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.

Content

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