Notes on Computational Complexity Theory
This note provides an introduction to the theory of computational complexity. Topics covered includes: Models of computation, Time and space complexity classes, Nonterminism and NP, Diagonalization, Oracles and relativization, Alternation, Space complexity, Natural proofs, Randomized classes, Counting classes, Descriptive complexity and Interactive proofs.
Author(s): James Aspnes
180 Pages 
This note contains below topics, Strings and formal languages, Deterministic and nondeterministic finite automata, Regular expressions, Context free languages, Turing machines, Undecidability.
Author(s): Jeff Erickson, University of Illinois Urbana-Champaign
155 Pages
Introduction to the Theory of Computing
This pdf includes overview and mathematical foundations, Regular operations and regular expressions, Proving languages to be nonregular, Further discussion of regular languages, Parse trees, ambiguity, and Chomsky normal form, Pushdown automata, Turing machines, Variants of Turing machines, Stack machines, Universal Turing machines and undecidable languages, Further discussion of computability.
Author(s): University of Waterloo
227 Pages
Theory of Computation by Kyle Burke
This pdf begins with an overview of resources, organization and motivation and preview of CS theory covering the Limits of Computation, the Undecidability of the Halting Problem.The Automata and Machines including Deterministic and Nondeterministic Finitestate Automata, Pushdown Automata, and Turing Machines and Language Classes. Finally focus shifts to Computational Complexity, discussing NPCompleteness, Approximation Algorithms, and the Hardness of Approximation.
Author(s): Kyle Burke
114 Pages
Models of Computation by John E Savage
This PDF Models of Computation by John E. Savage covers the following topics related to Computation Theory, The Role of Theory in Computer Science, General Computational Models, Logic Circuits, Machines with Memory, FiniteState Machines and Pushdown Automata, Computability, Algebraic and Combinatorial Circuits, Parallel Computation, Computational Complexity, Complexity Classes, Circuit Complexity, SpaceTime Tradeoffs, MemoryHierarchy Tradeoffs, VLSI Models of Computation.
Author(s): John E. Savage, Brown University
698 Pages
Introduction to Computational Theory Lecture Notes
This note covers the following topics, Languages, Finite Automata, Regular Languages and Sets, ContextFree Grammars, Pushdown Automata and ContextFree Languages, Turing Machines, The Chomsky Hierarchy, P and NP.
Author(s): BYU Computer Science Department
NA Pages
Introduction to Theory of Computation Lecture Notes
These lecture notes give an introduction to the more fundamental parts of the theory of computation and begin by presenting finite automata, starting with deterministic and nondeterministic finite automata, their equivalence, and practical implications of these concepts. The lecture notes include sections on regular expressions and their relationship to finite automata, nonregular languages, and the Pumping Lemma to prove nonregularity. MyhillNerode Theorem, For understanding recognition of languages. The notes go further to present contextfree languages, including their ambiguity and properties of closure. The pumping lemma for contextfree languages is also discussed, while decidable and recognizable languages are informed by a deep underpinning in computational theory.
Author(s): Mahesh Viswanathan
NA Pages
