Theory of Computation Tutorials
This set of tutorials goes into the heart of the theory of computer science with formal languages and automatons, computability, and complexity. Topics to be discussed are regular and contextfree languages, finite automata, and pushdown automata. Consequently, resulting tutorials treat topics like Turing machines, Churchs thesis, and the problem of undecidability, whose examples include the and quot,halting problem and quot, in the exploration of the limits of computability. They look into complexity classes such as P, NP, and PSPACE, look into NPcompleteness, or provide an indepth treatment along with a wide introduction to the theoretical foundations of computer science.
Author(s): The Australian National University, Canberra
NA Pages 
Theory of Computation by Frank Stephan
This note explains the following topics, sets and regular expressions, Grammars and the chomsky hierarchy, Finite automata, Nondeterministic finite automata, Combining languages, Normal forms and algorithms, Deterministic membership testing, Nondeterministic membership testing, Models of computation, Complexity considerations, Undecidable problems, Undecidability and formal languages.
Author(s): Frank Stephan
176 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
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
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
Theory of Computation Tutorials
This set of tutorials goes into the heart of the theory of computer science with formal languages and automatons, computability, and complexity. Topics to be discussed are regular and contextfree languages, finite automata, and pushdown automata. Consequently, resulting tutorials treat topics like Turing machines, Churchs thesis, and the problem of undecidability, whose examples include the and quot,halting problem and quot, in the exploration of the limits of computability. They look into complexity classes such as P, NP, and PSPACE, look into NPcompleteness, or provide an indepth treatment along with a wide introduction to the theoretical foundations of computer science.
Author(s): The Australian National University, Canberra
NA Pages
