Teaching material.

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

[M2] Lecture Notes for Formal Languages. Diego Calvanese. 2007. Available on the course web page as scanned pages in pdf.

1. Basic notions [M1: Chapter 1]
   • basic notions about relations, functions, and their properties
   • basic notions about formal languages
2. Finite state automata [M1: Chapter 2]
   • deterministic finite automata
   • non-deterministic finite automata
   • finite automata with epsilon-transitions
3. Regular expressions [M1: Chapter 3]
   • properties of regular expressions
   • relationship between regular expressions and finite automata
4. Properties of regular languages [M1: Chapter 4]
   • closure properties of regular languages
   • proving languages not to be regular
   • decision problems for regular languages
   • minimizing finite state automata
5. Chomsky grammars and context-free languages
   • classification of grammars [M2]
   • context-free grammars [M1: Chapter 5]
   • normal forms for context-free grammars [M1: Section 7.1]