Theory of Computation by Kyle Burke

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

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

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

Introduction to Computational Theory Lecture Notes

This note covers the following topics: Languages, Finite Automata, Regular Languages and Sets, Context-Free Grammars, Pushdown Automata and Context-Free Languages, Turing Machines, The Chomsky Hierarchy, P and NP.

Author(s): BYU Computer Science Department

NA Pages

Advanced Theory in Computation

This note covers the following topics: Analysis of Algorithms, String Matching, Amortized Analysis, Knuth-Morris-Pratt Algorithm, Pattern-Matching Machine, Boyer-Moore Algorithm, Horspool Algorithm, Suffix Trees, Dictionary Techniques, Ziv-Lempel Coding, Randomized Algorithms, Reservation-Price-Policy, Portfolio Selection, Statistical Adversaries.

Author(s): Seoul National University

NA Pages

Theory of Computation Tutorials

This note explains the theoretical computer science areas of formal languages and automata, computability and complexity. Topics covered include: regular and context-free languages, finite automata and pushdown automata, Turing machines, Church's thesis, computability - halting problem, solvable and unsolvable problems, space and time complexity, classes P, NP and PSPACE, NP-Completenes.

Author(s): The Australian National University, Canberra

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 Computation Theory

This course is an introduction to the Theory of Computation. Topics covered includes: Background Mathematics, Models of Computation, Context-Free Grammars, Automata, The Chomsky Hierarchy.

Author(s): Konrad Slind

231 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

The Theory of Languages and Computation

This note covers the following topics: Automata, Set Theory, The Natural numbers and Induction, Foundations of Language Theory, Operations on Languages, Deterministic Finite Automata, Formal Languages, Computability, Computations of Turing Machines, The Primitive Recursive Functions, The Partial Recursive Functions, DNA Computing, Analog Computing and Scientific Computing.

Author(s): Jean Gallier and Andrew Hicks

109 Pages