Slides

• Regular Languages
  • Finite Automata: 1
  • Regular Expressions: 2
  • Nondeterminism: 3a | 3b
  • Properties of Regular Languages: 4a | 4b
  • Applications of Finite Automata: 5
• Context-Free Languages
  • Context-Free Grammars: 6a | 6b
  • Pushdown Automata: 7
  • Grammars and Equivalencies: 8a | 8b
  • Properties of Context-free Languages: 9a | 9b
  • Deterministic Parsing: 10a | 10b | 10c
• Turing Machines
  • Turing Machines: 11
  • Variations of Turning Machines: 12
  • Decidable Problems and Recursive Languages: 13a | 13b
• Undecidability
  • Diagonalization and the Halting Problem: 14a | 14b
  • More Undecidable Problems: 15a | 15b
  • Recursive Functions: 16
• Complexity Theory
  • Time Complexity: 17a | 17b
  • Space Complexity: 18
  • NP-Completeness: 19a | 19b