Introduction to Theory of Computation by Wikiversity
This note describes the following topics: Finite State Machines, Closure and Nondeterminism, The Pumping Lemma, Minimizing FSMs, Context Free Languages, CFLs and compilers, Recitation, Pushdown Machines, CFGs and NPDMs, CYK algorithm, Undecidability and CFLs, Turing Machines, Halting Problem, Decidability, Complexity Theory, Quantified Boolean Formula, Savitch's Theorem, Space Hierarchy, Recursion Theorem.
Author(s): Wikiversity
NA Pages 
Lecture Notes of Introduction to the Theory of Computation
This note exlains the following topics: foundational concepts like strings and DFAs, then progresses to regular expressions, nondeterministic automata, and formal language theory, Advanced topics include Turing machines, decidability, and language-related problems it offers a comprehensive look at formal languages, automata, and computability.
Author(s): Margaret Fleck and Sariel Har Peled
345 Pages
Theory of Computation by Jim Hefferon
This PDF covers the following topics related to Theory of Computation : Mechanical Computation, Background, Languages and graphs, Automata, Computational Complexity.
Author(s): Jim Hefferon
439 Pages
Lecture Notes Theory of Computation
This note covers the following topics: Properties of binary operations, Concantenation properties, Finite automata, Formal Languages, Pumping Lemma.
Author(s): S R Engineering College
155 Pages
Theory of Computation Lectures
This note covers the following topics: Sets, functions and other preliminaries, Formal Languages, Finite Automata , Regular Expressions, Turing Machines, Context-Free Languages, Rice's Theorem, Time complexity, NP-Completeness, Space Complexity , Log Space, Oracle machines and Turing Reducibility, Probabilistic Complexity, Approximation and Optimisation, Complexity Hierarchy Theorems.
Author(s): UNSW Sydne
NA Pages
Theory of Computation Lecture Notes
This note covers the following topics: Mathematical Perliminaries, Automata Theory, Combinatorics and Graph Theory, DFAs to Regular Expressions- Brzozowski’s Algebraic Method, Myhill-Nerode and DFA Minimization, Group Theory, Turing Machines and Computability Theory, Complexity Theory.
Author(s): Michael Levet
114 Pages
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
Theory Of Computation Lecture Notes
This lecture note covers the following topics: Theory Of Computation, Introduction To Automata, Finite Automata, Regular Expressions And Languages, Properties Of Regular Language, Context-free Grammars And Languages, Applications Of Context-free Grammars, Pushdown Automata, Properties of Context-Free Languages.
Author(s): Prof. D. Chandrasekhar Rao, Prof. Kishore Kumar Sahu and Prof. Pradipta Kumar Das
120 Pages
Introduction to Theoretical Computer Science or Theory of Computation
This note covers the following topics: introduction to theoretical computer science, language, regular language, finite automata, language accepted by dfa, nondeterministic finite automata, equivalence of nfa, regular language and fa, application of fa, nonregular languages, context free languages, turing machines, computability and complexity.
Author(s): Pavan Kumar Anumula, Andrea Di Fabio and Jia Zhu
NA Pages
Computation Theory Lecture notes
The aim of this course note is to introduce several apparently different formalisations of the informal notion of algorithm; to show that they are equivalent; and to use them to demonstrate that there are incomputable functions and algorithmically undecidable problems.
Author(s): Prof Anuj Dawar
93 Pages
A Computational Introduction to Number Theory and Algebra (V. Shoup)
This book introduces the basic concepts from computational number theory and algebra, including all the necessary mathematical background. Covered topics are: Basic properties of the integers, Congruences, Computing with large integers, Euclid’s algorithm, The distribution of primes, Abelian groups, Rings, Finite and discrete probability distributions, Probabilistic algorithms, Probabilistic primality testing, Finding generators and discrete logarithms in Zp, Quadratic reciprocity and computing modular square roots, Modules and vector spaces, Matrices, Subexponential-time discrete logarithms and factoring, Polynomial arithmetic and applications.
Author(s): Victor Shoup
NA Pages
