The notes will be very sparse; I will only put in them definitions and the like (and maybe some worked, tedious exercises). The main matter will be discussed on the blackboard; these notes are just a mean to save me (and you too) some writing (and so some time). You are strongly advised to print them (the 4-up version perhaps, as it saves trees) and bring them with you in class.
| Notes (4-up) | Notes (1-up) | Relevant textbook material |
|---|---|---|
| Mathematical preliminaries; Alphabets and Languages | Math; Alphabets and Languages | Chapter 1 |
| Finite automata | Finite automata | Chapter 2 (most) |
| Context-free languages | Context-free languages | Chapter 3 (except Sections 3.6 and 3.7) |
| Determinism and parsing | Determinism and parsing | Sections 3.6 and 3.7 |
| Turing machines | Turing machines | Chapter 4 (most) |
| Computability | Computability | Chapter 5 (less Section 5.7) |
| Complexity | Complexity | Chapters 6 and 7 (less Section 7.4) |
| Comping with NP-completness | Comping with NP-completness | Section 7.4 |