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 
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
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 languagerelated problems it offers a comprehensive look at formal languages, automata, and computability.
Author(s): Margaret Fleck and Sariel Har Peled
345 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
Lecture Notes Theory of Computation
This lecture note from S R Engineering College offers a detailed introduction to key concepts in the Theory of Computation. It begins with Properties of Binary Operations, exploring fundamental mathematical operations and their essential properties like associativity and commutativity. The section on Concatenation Properties covers how strings can be joined and the characteristics of such operations, including associativity and the identity element. Finite Automata are thoroughly discussed, explaining both deterministic and nondeterministic NFA models, and their role in recognizing regular languages. The notes also cover Formal Languages, categorizing them into regular, contextfree, contextsensitive, and recursively enumerable types based on complexity. Finally, the Pumping Lemma is introduced as a critical tool for proving the nonregularity and noncontextfreeness of languages by demonstrating how strings in these languages can be decomposed and manipulated.
Author(s): S R Engineering College
155 Pages
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, Savitchs Theorem, Space Hierarchy, Recursion Theorem.
Author(s): Wikiversity
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
