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
176Pages
This note covers Induction, Recursion, Program correctness, Regular languages and finite automata.
Author(s): University of Toronto
75Pages
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
345Pages
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
227Pages
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 Finite-state Automata, Pushdown Automata, and Turing Machines and Language Classes. Finally focus shifts to Computational Complexity, discussing NP-Completeness, Approximation Algorithms, and the Hardness of Approximation.
Author(s): Kyle Burke
114Pages
This PDF covers the following topics related to Theory of Computation : Mechanical Computation, Background, Languages and graphs, Automata, Computational Complexity.
Author(s): Jim Hefferon
439Pages
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
698Pages
This note covers the following topics: Properties of binary operations, Concantenation properties, Finite automata, Formal Languages, Pumping Lemma.
Author(s): S R Engineering College
155Pages
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
NAPages
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
NAPages
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
NAPages
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
NAPages
