Introduction to Theory of Computation
 |
Educational level: this is a tertiary (university) resource. |
 |
Completion status: this resource is a stub, so not much has been done yet. |
 |
Subject classification: this is a mathematics resource. |
 |
Subject classification: this is an information technology resource. |
Lecture notes
Lectures
- Finite State Machines
- Closure and Nondeterminism
- The Pumping Lemma
- Minimizing FSMs
- Recitation 1
- Context Free Languages
- CFLs and compilers
- Recitation 2
- Pushdown Machines
- Recitation 3
- CFGs and NPDMs
- More lemmas, CYK algorithm
- Undecidability and CFLs
- Recitation 4
- The Bullseye (Hierarchy of Languages)
- Turing Machines
- Recitation 5
- The Halting Problem
- Decidability
- Complexity Theory, Quantified Boolean Formula
- Savitch's Theorem, Space Hierarchy
- Decidability/Complexity Relationship, Recursion Theorem
Handouts
Textbooks
Free textbook:
- An Introduction to the Theory of Computation , by Eitan Gurari