Skip to content
lectern.tv
MIT 18.404J: Theory of Computation →0/22
1

1. Introduction, Finite Automata, Regular Expressions

1:00:34
2

2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA

1:03:27
3

3. Regular Pumping Lemma, Conversion of FA to Regular Expressions

1:10:02
4

4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion

1:09:22
5

5. CF Pumping Lemma, Turing Machines

1:13:59
6

6. TM Variants, Church-Turing Thesis

1:14:49
7

7. Decision Problems for Automata and Grammars

1:16:51
8

8. Undecidability

1:17:02
9

Lecture 9: Reducibility (18.404J)

1:16:37
10

Lecture 10: Computation History Method (18.404J)

1:21:41
11

Lecture 11: Recursion Theorem and Logic (18.404J)

1:17:32
12

Lecture 12: Time Complexity (18.404J)

1:25:37
13

Lecture 14: P and NP, SAT, Poly-Time Reducibility (18.404J)

1:19:23
14

Lecture 15: NP-Completeness (18.404J)

1:25:53
15

Lecture 16: Cook-Levin Theorem (18.404J)

1:18:27
16

Lecture 17: Space Complexity, PSPACE, Savitch's Theorem (18.404J)

1:20:10
17

Lecture 18: PSPACE-Completeness (18.404J)

1:17:36
18

Lecture 19: Games, Generalized Geography (18.404J)

1:19:38
19

Lecture 20: L and NL, NL = coNL (18.404J)

1:20:06
20

Lecture 21: Hierarchy Theorems (18.404J)

1:21:57
21

Lecture 22: Provably Intractable Problems, Oracles (18.404J)

1:22:50
22

Lecture 23: Probabilistic Computation, BPP (18.404J)

1:23:41

5. CF Pumping Lemma, Turing Machines

Michael SipserMIT

Donner Professor of Mathematics

1:13:59·2021·undergraduate level

This lecture proves the Context-Free Language Pumping Lemma, demonstrating its utility in classifying languages that are not context-free. It then formally introduces Turing Machines, including the definition of deciders.

Theory & AlgosComputational ComplexityTheory of ComputationPumping LemmaTuring Machines

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 · Lecture 4

4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion

Next · Lecture 6

6. TM Variants, Church-Turing Thesis

Seminar notes & discussion

Sign in to comment

No public seminar notes on this lecture yet.