## An Introduction to the Theory of Computation

Download An Introduction to the Theory of Computation by Eitan Gurari, This book explores some of the more important terminologies and queries regarding programs, computers, problems, and computation. The exploration reduces in several cases to a study of mathematical theories, like those of automata and formal languages; theories that are fascinating also in their own right. These theories offer abstract models that are easier to explore, as a result of their formalisms avoid irrelevant details. Download the pdf from below to explore all topics and start learning.

BOOK CONTENTS-

1 GENERAL CONCEPTS
1.1 Alphabets, Strings, and Representations
1.2 Formal Languages and Grammars
1.3 Programs
1.4 Problems
1.5 Reducibility among Problems
Exercises
Bibliographic Notes
2 FINITE-MEMORY PROGRAMS
2.1 Motivation
2.2 Finite-State Transducers
2.3 Finite-State Automata and Regular Languages
2.4 Limitations of Finite-Memory Programs
2.5 Closure Properties for Finite-Memory Programs
2.6 Decidable Properties for Finite-Memory Programs
Exercises
Bibliographic Notes
3 RECURSIVE FINITE-DOMAIN PROGRAMS
3.1 Recursion
3.2 Pushdown Transducers
3.3 Context-Free Languages
3.4 Limitations of Recursive Finite-Domain Programs
3.5 Closure Properties for Recursive Finite-Domain Programs
3.6 Decidable Properties for Recursive Finite-Domain Programs
Exercises
Bibliographic Notes
4 GENERAL PROGRAMS
4.1 Turing Transducers
4.2 Programs and Turing Transducers
4.3 Nondeterminism versus Determinism
4.4 Universal Turing Transducers
4.5 Undecidability
4.6 Turing Machines and Type 0 Languages
4.7 Post's Correspondence Problem
Exercises
Bibliographic Notes
5 RESOURCE-BOUNDED COMPUTATION
5.1 Time and Space
5.2 A Time Hierarchy
5.3 Nondeterministic Polynomial Time
5.4 More NP-Complete Problems
5.5 Polynomial Space
5.6 P-Complete Problems
Exercises
Bibliographic Notes
6 PROBABILISTIC COMPUTATION
6.1 Error-Free Probabilistic Programs
6.2 Probabilistic Programs That Might Err
6.3 Probabilistic Turing Transducers
6.4 Probabilistic Polynomial Time
Exercises
Bibliographic Notes
7 PARALLEL COMPUTATION
7.1 Parallel Programs
7.2 Parallel Random Access Machines
7.3 Circuits
7.4 Uniform Families of Circuits
7.5 Uniform Families of Circuits and Sequential Computations
7.6 Uniform Families of Circuits and PRAM's
Exercises
Bibliographic Notes
A MATHEMATICAL NOTIONS
A.1 Sets, Relations, and Functions
A.2 Graphs and Trees
B BIBLIOGRAPHY