Your textbook…
Theory of Computing: A Gentle Introduction
ISBN-10: 0-13-027961-7
ISBN-13: 978-0-13-027961-3
Published by Prentice Hall
© 2001
Pub. Date: Jun 13, 2000
Format: Paper
Table of Contents
(NOTE: Each chapter concludes with Exercises.)
1. Introduction.
2. Finite Automata.
3. Context Free Languages.
4. Turing Machines.
5. Undecidability.
6. Computational Complexity.
References.
List of Symbols.
Index.
1. Introduction.
Why Study the Theory of Computing? What Is Computation? The Contents of This Book. Mathematical Preliminaries.
2. Finite Automata.
Deterministic Finite Automata. Nondeterministic Finite Automata. Determinism versus Nondeterminism. Regular Expressions. Nonregular Languages. Algorithms for Finite Automata. The State Minimization Problem.
3. Context Free Languages.
Context-Free Grammars. Parsing. Pushdown Automata. Languages and Automata. Closure Properties. Languages That Are Not Context-Free. Chomsky Normal Form. Determinism.
4. Turing Machines.
Definition of a Turing Machine. Computations by Turing Machines. Extensions of Turing Machines. Nondeterministic Turing Machines. Turing Enumerable Languages.
5. Undecidability.
The Church-Turing Thesis. Universal Turing Machines. The Halting Problem. Undecidable Problems.
6. Computational Complexity.
The Definition and the Class P. The Class N P. N P-Completeness.
References.
List of Symbols.
Index.
