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 handout version perhaps, as it saves trees) and bring them with you in class.

Notes (handout) |
Notes (overhead presentation) |
Relevant textbook material |
---|---|---|

Mathematical preliminaries; Alphabets and Languages | Math; Alphabets and Languages | Chapter 1 |

Finite automata | Finite automata | Chapter 2 |

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) |

Some Turing-comlete formalisms | Turing-comlete formalisms |