Slides for CMU-Q 15-453 Formal Languages, Automata and Computation for Spring 2011.

These slides are based on “Introduction to the Theory of Computation” by Sipser.

  1. Lecture 1 – Introduction

  2. Lecture 2 – Finite State Automata

  3. Lecture 3 – Nondeterminism and Nondeterministic Finite Automata

  4. Lecture 4 – Regular Expressions and Their Equivalence to NFAs

  5. Lecture 5 – DFA's to Regular Expressions, DFA minimization, Closure Properties or Regular Languages

  6. Lecture 6 – Pumping Lemma for Regular Languages

  7. Lecture 7 – Context Free Languages – 1

  8. Lecture 8 – Context Free Languages – 2

  9. Lecture 9 - Push Down Automata

  10. Lecture 10 – Push Down Automata (cont'd), Closure Properties of CFLs

  11. Lecture 11 – Pumping Lemma for CFL's

  12. Lecture 12 – Turing Machines -1

  13. Lecture 13 - Turing Machines -2

  14. Lecture 14 - Turing Machines -3

  15. Lecture 15 - Decidability

  16. Lecture 16 – Reducibility

  17. Lecture 17 – Post Correspondence Problem

  18. Lecture 18 – Advanced Topics

  19. Lecture 19 – Complexity

  20. Lecture 20 – NP-Completeness

  21. Lecture 21 – Showing Problems NP-Complete

  22. Lecture 22 – Space Complexity