Home
MIT 18.404
Theory of Computation
Lecture 1: Introduction, Finite Automata, Regular Expressions
§
Finite Automata
§
(Regular) Languages
§
Regular Operations and Regular Expressions
Lecture 2: Nondeterminism, Closure Properties, Regular Expressions
§
Nondeterministic Finite Automata
§
Regular Expressions are Regular Languages
Lecture 3: Regular Expressions, The Pumping Lemma
§
Generalized NFAs
§
Regular Languages are Regular Expressions
§
Proving Nonregularity
Lecture 4: Context-Free Grammars and Pushdown Automata
§
Context-Free Grammars: URLs
§
Context-Free Grammars: PEMDAS
§
Context-Free Grammars: Ambiguous PEMDAS
§
Pushdown Automata
§
CFLs are PDA Languages
Lecture 5: Context-Free Pumping Lemma, Turing Machines
§
Context-Free Languages: Miscellaneous
§
Context-Free Pumping Lemma
§
Turing Machines
Lecture 6: TM Variants, Church-Turing Thesis
§
Turing Machines (Recap) & The Church-Turing Thesis
§
Multi-Tape Turing Machines
§
Nondeterministic Turing Machines
§
Enumerators (Turing Machines with Printers)
Lecture 7: Decision Problems for Automata and Grammars
§
Encodings
§
Algorithms on Automata
§
Algorithms on Grammars and Turing Machines
Lecture 8: Undecidability
§
A
T
M
A_{\mathrm{TM}}
A
TM
Undecidability
§
Turing-Unrecognizable
Lecture 9: Reducibility
§
Reducibility
§
Mapping Reducibility