Concise guide to computation theory

Part I The Theory of Computation.

1. Everything Begins with Computation

Computational Barrier

Propiety of Computational Models

Using this Book Efficiently

2. Preliminaries to the Theory of Computation

Set

Strings and Languages

Functions and Problems

Relations and Graphs

Boolean Operations and Boolean Formulas

Propositions and Proofs

Descriptions of Algorithms

Problems

Part II Automata and Languages.

3. Finite Automata

Modeling by Automata

Nondeterministic Finite Automaton

Regular Expression

Properties of Regular Languages

Problems

4. Context-Free Languages

Context-Free Grammar

Generating and Accepting

Chomsky Normal Form

Limitation on Generating Power of Context-Free Grammars

Membership Problem for Context-Free Languages

Problems

5. Pushdown Automata

Pushdown Automaton

Equivalence of Pushdown Automaton and Context-Free Grammar

Problems

Part III Computability

6.Turing Machine

Turing Machine

Variants of Turing Machines

Nondeterministic Turing Machines

Church-Turing Thesis

Problems

7. Universality of Turing Machine and Its Limitations

Universal Turing Machine

Undecidability of the Halting Problem

Reduction

Undecidability of Post Correspondence Problem

Problems

Part IV Complexity of Computation.

8. Computational Complexity Based on Turing Machines

Time Complexity

Problems that Are Solvable in Polynomial Time and those the have not been solved in Polynomial Time

P and NP

Problems

9. Computational Complexity Based on Boolean Circuits

Boolean Functions and Boolean Circuits

Finite Functions and Finite Circuits

Boolean Circuit Family to Stimulate Deterministic Turing Machine

Finite Circuit Family to Stimulate Nondeterministic Turing Machine

Satisfiability Problems

Reducing Circuit Satisfiability Problem to Formula Satisfiability Problem

Problems

10 NP-Completeness

NP-Completeness

NP-Complete Problems

Problems

Part V Conclusions and Exercise Solutions.

11. Solutions

Chapter 2

Chapter 3

Chapter 4

Chapter 5

Chapter 6

Chapter 7

Chapter 8

Chapter 9

Chapter 10

12. Concluding Remarks.