Introduction, Finite Automata, Regular Expressions
1:00:34Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
1:03:27Regular Pumping Lemma, Conversion of FA to Regular Expressions
1:10:02Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
1:09:22CF Pumping Lemma, Turing Machines
1:13:59TM Variants, Church-Turing Thesis
1:14:49Decision Problems for Automata and Grammars
1:16:51Undecidability
1:17:02Reducibility
1:16:37Computation History Method
1:21:41Recursion Theorem and Logic
1:17:32Time Complexity
1:25:37P and NP, SAT, Poly-Time Reducibility
1:19:23NP-Completeness
1:25:53Cook-Levin Theorem
1:18:27Space Complexity, PSPACE, Savitch's Theorem
1:20:10PSPACE-Completeness
1:17:36Games, Generalized Geography
1:19:38L and NL, NL = coNL
1:20:06Hierarchy Theorems
1:21:57Provably Intractable Problems, Oracles
1:22:50Probabilistic Computation, BPP
1:23:41Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
This lecture introduces Nondeterministic Finite Automata (NFAs), proving their equivalence to Deterministic Finite Automata (DFAs) and demonstrating the closure properties of regular languages under concatenation and Kleene star. It concludes with methods for converting regular expressions into NFAs.
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
Introduction, Finite Automata, Regular Expressions
Next · Lecture 3Regular Pumping Lemma, Conversion of FA to Regular Expressions