Tutorial · 34 chapters
Theory of Computation
Automata, regular expressions, context-free grammars, pushdown automata, Turing machines, decidability and complexity, with solved problems.
Mission log
01Introduction to Theory of Computation02Alphabets, Strings & Languages03Finite Automata04Deterministic Finite Automata (DFA)05Designing DFAs: Solved Problems06Nondeterministic Finite Automata (NFA)07NFA to DFA Conversion (Subset Construction)08Epsilon-NFA & Epsilon-Closure09DFA Minimization10Moore & Mealy Machines11Regular Expressions12Regular Expression to Finite Automata13Finite Automata to Regular Expression (Arden's Theorem)14Regular Grammars15Closure Properties of Regular Languages16Pumping Lemma for Regular Languages17Context-Free Grammars18Derivations, Parse Trees & Ambiguity19Simplification of CFGs20Chomsky Normal Form21Greibach Normal Form22CYK Algorithm23Pushdown Automata24Equivalence of PDA & CFG25Pumping Lemma for Context-Free Languages26Closure & Decision Properties of CFLs27Turing Machines28Variants of Turing Machines29Chomsky Hierarchy & Linear Bounded Automata30Decidability: Recursive & Recursively Enumerable Languages31Halting Problem & Undecidability32Reductions & Rice's Theorem33Post Correspondence Problem34Complexity Classes: P, NP & NP-Complete
