1. Introduction, Finite Automata, Regular Expressions
1:00:342. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
1:03:273. Regular Pumping Lemma, Conversion of FA to Regular Expressions
1:10:024. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
1:09:225. CF Pumping Lemma, Turing Machines
1:13:596. TM Variants, Church-Turing Thesis
1:14:497. Decision Problems for Automata and Grammars
1:16:518. Undecidability
1:17:02Lecture 9: Reducibility (18.404J)
1:16:37Lecture 10: Computation History Method (18.404J)
1:21:41Lecture 11: Recursion Theorem and Logic (18.404J)
1:17:32Lecture 12: Time Complexity (18.404J)
1:25:37Lecture 14: P and NP, SAT, Poly-Time Reducibility (18.404J)
1:19:23Lecture 15: NP-Completeness (18.404J)
1:25:53Lecture 16: Cook-Levin Theorem (18.404J)
1:18:27Lecture 17: Space Complexity, PSPACE, Savitch's Theorem (18.404J)
1:20:10Lecture 18: PSPACE-Completeness (18.404J)
1:17:36Lecture 19: Games, Generalized Geography (18.404J)
1:19:38Lecture 20: L and NL, NL = coNL (18.404J)
1:20:06Lecture 21: Hierarchy Theorems (18.404J)
1:21:57Lecture 22: Provably Intractable Problems, Oracles (18.404J)
1:22:50Lecture 23: Probabilistic Computation, BPP (18.404J)
1:23:411. Introduction, Finite Automata, Regular Expressions
This inaugural lecture for MIT's Theory of Computation course introduces finite automata, regular languages, and regular expressions. It formally defines these concepts and proves closure properties for regular languages under union and concatenation.
MIT 18.404J Theory of Computation, Fall 2020
Instructor: Michael Sipser
View the complete course: https://ocw.mit.edu/18-404JF20
YouTube Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP60_JNv2MmK3wkOt9syvfQWY