Introduction to Theory of Computation
From Wikiversity - Reading time: 1 min
 |
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
[edit | edit source]Lectures
[edit | edit source]- 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
[edit | edit source]Textbooks
[edit | edit source]Free textbook:
- An Introduction to the Theory of Computation , by Eitan Gurari
Problem sets
[edit | edit source]Exams problems
[edit | edit source]Licensed under CC BY-SA 3.0 | Source: https://en.wikiversity.org/wiki/Introduction_to_Theory_of_Computation16 views | Status: cached on July 24 2025 04:00:37↧ Download this article as ZWI file
EncycloReader
is supported by the 
KSF