# 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 edit

## Lectures edit

- 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

## Textbooks edit

Free textbook:

*An Introduction to the Theory of Computation*, by Eitan Gurari