Skip to content
lectern.tv
Computability, Zero-Knowledge & Differential Privacy →0/6
1

Introduction, Finite Automata, Regular Expressions

Michael Sipser · 1:00:34

2

Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA

Michael Sipser · 1:03:27

3

Introduction to Cryptography

Christof Paar · 1:17:24

4

Proofs, Knowledge, and Computation: Zero-Knowledge Interactive Systems

Silvio Micali · 1:03:26

5

What Needs to Be Added to Machine Learning? PAC Learning and Reasoning

Leslie G. Valiant · 54:36

6

Differential Privacy: Fundamentals to Forefront

Cynthia Dwork · 59:33

Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA

Michael SipserMIT

Donner Professor of Mathematics

1:03:27·2021·undergraduate level
Path step 2: Introduces nondeterminism and closure constructions that foreshadow NP verification.

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.

Theory & AlgosTheory of ComputationAutomata TheoryRegular Languages

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

Previous · Step 1

Introduction, Finite Automata, Regular Expressions

Next · Step 3

Introduction to Cryptography

Comments

Add a comment...Sign in