Advertisement
Introduction to the Theory of Computation
This note explains the following topics: Automata and Language Theory, Finite automata, regular expressions, push-down automata, context-free grammars, pumping lemmas, Computability Theory, Turing machines, Church-Turing thesis, decidability, halting problem, reducibility, recursion theorem, Complexity Theory, Time and space measures, hierarchy theorems, complexity classes P, NP, PSPACE, complete problems, P versus NP conjecture, quantifiers and games, provably hard problems, probabilistic computation.
Author(s): Prof. Sofya Raskhodnikova
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
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 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
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, Finite-State Machines and Pushdown Automata, Computability, Algebraic and Combinatorial Circuits, Parallel Computation, Computational Complexity, Complexity Classes, Circuit Complexity, Space–Time Tradeoffs, Memory-Hierarchy Tradeoffs, VLSI Models of Computation.
Author(s): John E. Savage, Brown University
698 Pages
Introduction to Theory of Computation Lecture Notes
This note explains the following topics: Discrete mathematics, Deterministic Finite Automata, Nondeterministic Finite Automata, Equivalence of DFA and NFA, Nondeterministic Finite Auotmata, egular expressions and finite automata, Non-regular languages and Pumping Lemma, Myhill-Nerode Theorem, Context-free languages and Ambiguity, Closure Properties, Pumping Lemma and non-CFLs, Closure Properties and non-CFL Languages, Decidable and Recognizable Languages.
Author(s): Mahesh Viswanathan
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
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
Introduction to Theory of Computation
This is a free textbook for an undergraduate course on the Theory of Computation, which have been teaching at Carleton University since 2002.Topics covered includes: Finite Automata and Regular Languages, Context-Free Languages, Turing Machines and the Church-Turing Thesis, Decidable and Undecidable Languages and Complexity Theory.
Author(s): Anil Maheshwari and ichiel Smid
246 Pages
Great Ideas in Theoretical Computer Science Lecture Notes
This course note provides a challenging introduction to some of the central ideas of theoretical computer science. It attempts to present a vision of computer science beyond computers: that is, CS as a set of mathematical tools for understanding complex systems such as universes and minds.
Author(s): Prof. Scott Aaronson
NA PagesAdvertisement
