Teaching material.

[M1] Introduction to Automata Theory, Languages, and Computation (2nd edition). J.E. Hopcroft, R. Motwani, J.D. Ullman. Addison Wesley, 2003.

[M2] Lecture Notes for Theory of Computing. Diego Calvanese. 2006. Available on the course web page as scanned pages in pdf.

1. Basic notions [M1: Chapter 1]
   • formal proofs (deductive proofs, proofs by contradiction, equivalences about sets, inductive proofs)
   • basic notions about formal languages
2. Regular languages
   • finite automata [M1: Chapter 2]
   • regular expressions [M1: Chapter 3]
   • properties of regular languages [M1: Chapter 4]
3. Context-free languages
   • context-free grammars [M1: Chapter 5]
   • pushdown automata [M1: Chapter 6]
   • properties of context-free languages [M1: Chapter 7]
4. Turing Machines and undecidability
   • The "basic" TM, extended TMs, restricted TMs [M1: Chapter 8]
   • recursive enumerability [M1: Chapter 9]
   • undecidable problems [M1: Chapter 9]
5. Computational complexity [M1: Chapter 10]
   • the classes P and NP
   • NP-completeness and NP-complete problems
   • polynomial space and the polynomial hierarchy