Calendari del curs
Aquesta pàgina s’actualitzarà freqüentment amb els temes actuals i futurs. Qualsevol contingut marcat amb gris clar és provisional i pot estar subjecte a canvis.
A la taula següent, la notació \S fa referència als capítols; per exemple, (Sipser 2013, \S 2.3) fa referència al capítol 2, secció 3 del llibre (Sipser 2013).
Dt 08–10 (A5-104), Dj 12–14 (A5S111)
Professors: Enrique Romero
| # | Data | Tema de la classe | Referències |
|---|---|---|---|
1 |
09/09/2025 |
30 min: Overview of the course, administrative part; 1.30hr theory: Math background; Strings and languages; Pigeonhole principle; Cantor Diagonalization |
(Sipser 2013, \S 0 and \S 4.2 The diagonalization method (pp. 202 until the end of Theorem 4.17) |
2 |
16/09/2025 |
2hr problems: Student solutions of Homework 1 Homework 1 is due on this class (see the racó for the exercise assigned to you) |
|
3 |
18/09/2025 |
1hr theory: Finite Automata (DFAs), formalization, some closure properties (union, intersection, the product construction); 1hr lab: examples of DFAs using RACSO |
(Sipser 2013, \S 1.1) |
4 |
23/09/2025 |
2hr problems: Student solutions of Homework 2 Homework 2 is due on this class (see the racó for the exercise assigned to you) |
|
5 |
25/09/2025 |
1hr theory: NFAs, determinization of NFAs; more closure properties; 1hr lab: construction of DFAs using RACSO; minimization of DFAs (Moore’s algorithm) In (Sipser 2013) the minimization of DFAs is only done in Problem 1.51, 1.52, and 7.42. |
(Sipser 2013, \S 1.2) |
6 |
30/09/2025 |
2hr problems: Student solutions of Homework 2 |
|
7 |
02/10/2025 |
2hr lab: construction of DFAs using RACSO |
|
8 |
07/10/2025 |
2hr theory: regular expressions and equivalence with NFAs/DFAs; Pumping Lemma; \{a^nb^n\mid n\in \mathbb N\} is not regular; proving non-regularity using closure properties |
(Sipser 2013, \S 1.3 and \S 1.4) |
9 |
09/10/2025 |
2hr lab: exercises on regular operations on RACSO |
|
10 |
14/10/2025 |
2hr problems: Student solutions of Homework 3 Homework 3 is due on this class (see the racó for the exercise assigned to you) |
|
11 |
16/10/2025 |
1ht theory: Context-free grammars (CFG); Ambiguity; 1hr lab: construction of CFGs using RACSO |
(Sipser 2013, \S 2.1) |
12 |
21/10/2025 |
2hr problems: Student solutions of Homework 4 Homework 4 is due on this class (see the racó for the exercise assigned to you) |
|
13 |
23/10/2025 |
2hr lab: construction of CFGs using RACSO; |
|
14 |
28/10/2025 |
1hr problems: Student solutions of Homework 4; 1hr theory: pumping lemma for CFL; \{a^nb^nc^n \mid n\in \mathbb N\} is not context-free |
(Sipser 2013, \S 2.3) |
15 |
03/11/2025 10:30 – 12:30 |
Midterm 1 |
|
16 |
06/11/2025 |
No class |
|
17 |
11/11/2025 |
2hr theory: Turing Machines, basic properties, Church-Turing Thesis, Gödel numbering, Universal TM |
(Sipser 2013, \S 3) |
18 |
13/11/2025 |
1 hr theory: Pushdown-Automata, formalization, equivalence betwen PDAs and CFGs; 1 hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2 and \S 2.4) |
19 |
18/11/2025 |
1hr problems: Student solutions of Homework 5 1hr theory: RE \cap coRE = R, projection theorem Homework 5 is due on this class (see the racó for the exercise assigned to you) |
(Sipser 2013, \S 4) |
20 |
21/11/2025 |
1 hr theory: closure of CFL under intersection with regular languages and inverse homomorphism; 1 hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2 and \S 2.4) |
21 |
25/11/2025 |
2hr problems: Student solutions of Homework 5 |
|
22 |
27/11/2025 |
1.30hr theory: K \in RE\setminus R, reductions 30min lab: construction of reductions from K using RACSO; |
(Sipser 2013, \S 5) |
23 |
02/12/2025 |
2hr problems: Student solutions of Homework 6 Homework 6 is due on this class (see the racó for the exercise assigned to you) |
|
24 |
04/12/2025 |
1hr theory: Rice Theorem 1hr lab: construction of reductions from K using RACSO; (Sipser 2013) proves Rice’s Theorem only in Problem 5.28. |
|
25 |
09/12/2025 |
1hr problems: Student solutions of Homework 6 1hr theory: recap of P, EXP, NP |
(Sipser 2013, \S 7.1, \S 7.2, \S 7.3, \S 7.4) |
26 |
11/12/2025 |
2hr lab: construction of reductions to CFGs using RACSO |
|
27 |
16/12/2025 |
2hr problems: Student solutions of Homework 7 Homework 7 is due on this class (see the racó for the exercise assigned to you) |
|
28 |
18/12/2025 |
2hr theory: NP-completeness, polynomial-time reductions, Cook-Levin Theorem |
(Sipser 2013, \S 7.4 and \S 7.5) (Hopcroft, Motwani, i Ullman 2007, \S 10) |
29 |
09/01/2026 08:00 – 11:00 |
Midterm 2 |
|
30 |
19/01/2026 11:30 – 14:30 |
Final Exam |
Dt 12–14 (A5105), Dv 10–12 (A5S111)
Professors: Enrique Romero i Ilario Bonacina
| # | Data | Tema de la classe | Referències |
|---|---|---|---|
1 |
09/09/2025 |
30 min: Overview of the course, administrative part; 1.30hr theory: Math background; Strings and languages; Pigeonhole principle; Cantor Diagonalization |
(Sipser 2013, \S 0 and \S 4.2 The diagonalization method (pp. 202 until the end of Theorem 4.17) |
2 |
16/09/2025 |
2hr problems: Student solutions of Homework 1 Homework 1 is due on this class (see the racó for the exercise assigned to you) |
|
3 |
19/09/2025 |
1hr theory: Finite Automata (DFAs), formalization, some closure properties (union, intersection, the product construction); 1hr lab: examples of DFAs using RACSO |
(Sipser 2013, \S 1.1) |
4 |
23/09/2025 |
2hr problems: Student solutions of Homework 2 Homework 2 is due on this class (see the racó for the exercise assigned to you) |
|
5 |
26/09/2025 |
1hr theory: NFAs, determinization of NFAs; more closure properties; 1hr lab: construction of DFAs using RACSO; minimization of DFAs (Moore’s algorithm) In (Sipser 2013) the minimization of DFAs is only done in Problem 1.51, 1.52, and 7.42. |
(Sipser 2013, \S 1.2) |
6 |
30/09/2025 |
2hr problems: Student solutions of Homework 2 |
|
7 |
03/10/2025 |
2hr lab: construction of DFAs using RACSO |
|
8 |
07/10/2025 |
2hr theory: regular expressions and equivalence with NFAs/DFAs; Pumping Lemma; \{a^nb^n\mid n\in \mathbb N\} is not regular; proving non-regularity using closure properties |
(Sipser 2013, \S 1.3 and \S 1.4) |
9 |
10/10/2025 |
2hr lab: exercises on regular operations on RACSO |
|
10 |
14/10/2025 |
2hr problems: Student solutions of Homework 3 Homework 3 is due on this class (see the racó for the exercise assigned to you) |
|
11 |
17/10/2025 |
1ht theory: Context-free grammars (CFG); Ambiguity; 1hr lab: construction of CFGs using RACSO |
(Sipser 2013, \S 2.1) |
12 |
21/10/2025 |
2hr problems: Student solutions of Homework 4 Homework 4 is due on this class (see the racó for the exercise assigned to you) |
|
13 |
24/10/2025 |
2hr lab: construction of CFGs using RACSO; |
|
14 |
28/10/2025 |
2hr problems: Student solutions of Homework 4; |
(Sipser 2013, \S 2.3) |
15 |
03/11/2025 10:30 – 12:30 |
Midterm 1 |
|
16 |
07/11/2025 |
1hr theory: Pushdown-Automata, formalization, equivalence betwen PDAs and CFGs; 1hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2 and \S 2.4) |
17 |
11/11/2025 |
1hr theory: Student solutions of Homework 4; pumping lemma for CFL; \{a^nb^nc^n \mid n\in \mathbb N\} is not context-free 1hr theory: Turing Machines, basic properties, Church-Turing Thesis, Gödel numbering, Universal TM |
(Sipser 2013, \S 3) |
18 |
14/11/2025 |
1hr theory: closure of CFL under intersection with regular languages and inverse homomorphism; 1hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2) |
19 |
18/11/2025 |
1hr problems: Student solutions of Homework 5 1hr theory: RE \cap coRE = R, projection theorem Homework 5 is due on this class (see the racó for the exercise assigned to you) |
(Sipser 2013, \S 4) |
20 |
21/11/2025 |
1.30hr theory: K \in RE\setminus R, reductions 30min lab: construction of reductions from K using RACSO; |
(Sipser 2013, \S 5) |
21 |
25/11/2025 |
2hr problems: Student solutions of Homework 5 |
|
22 |
28/11/2025 |
1hr theory: Rice Theorem 1hr lab: construction of reductions from K using RACSO; (Sipser 2013) proves Rice’s Theorem only in Problem 5.28. |
|
23 |
02/12/2025 |
2hr problems: Student solutions of Homework 6 Homework 6 is due on this class (see the racó for the exercise assigned to you) |
|
24 |
05/12/2025 |
2hr lab: construction of reductions to CFGs using RACSO |
|
25 |
09/12/2025 |
1hr problems: Student solutions of Homework 6 1hr theory: recap of P, EXP, NP |
(Sipser 2013, \S 7.1, \S 7.2, \S 7.3, \S 7.4) |
26 |
12/12/2025 |
2hr theory: NP-completeness, polynomial-time reductions, Cook-Levin Theorem |
(Sipser 2013, \S 7.4 and \S 7.5) (Hopcroft, Motwani, i Ullman 2007, \S 10) |
27 |
16/12/2025 |
2hr problems: Student solutions of Homework 7 Homework 7 is due on this class (see the racó for the exercise assigned to you) |
|
28 |
19/12/2025 |
2hr theory: Time Hierarchy Theorem, P \neq EXP, TM with oracles |
(Sipser 2013, Theorem 9.10 and corollaries (pp. 369) and \S 9.2) |
29 |
09/01/2026 08:00 – 11:00 |
Midterm 2 |
|
30 |
19/01/2026 11:30 – 14:30 |
Final Exam |
Dt 18–20 (A5203), Dj 18–20 (A5S111)
Professors: Ilario Bonacina
| # | Data | Tema de la classe | Referències |
|---|---|---|---|
1 |
09/09/2025 |
30 min: Overview of the course, administrative part; 1.30hr theory: Math background; Strings and languages; Pigeonhole principle; Cantor Diagonalization |
(Sipser 2013, \S 0 and \S 4.2 The diagonalization method (pp. 202 until the end of Theorem 4.17) |
2 |
16/09/2025 |
2hr problems: Student solutions of Homework 1 Homework 1 is due on this class (see the racó for the exercise assigned to you) |
|
3 |
18/09/2025 |
1hr theory: Finite Automata (DFAs), formalization, some closure properties (union, intersection, the product construction); 1hr lab: examples of DFAs using RACSO |
(Sipser 2013, \S 1.1) |
4 |
23/09/2025 |
2hr problems: Student solutions of Homework 2 Homework 2 is due on this class (see the racó for the exercise assigned to you) |
|
5 |
25/09/2025 |
1hr theory: NFAs, determinization of NFAs; more closure properties; 1hr lab: construction of DFAs using RACSO; minimization of DFAs (Moore’s algorithm) In (Sipser 2013) the minimization of DFAs is only done in Problem 1.51, 1.52, and 7.42. |
(Sipser 2013, \S 1.2) |
6 |
30/09/2025 |
2hr problems: Student solutions of Homework 2 |
|
7 |
02/10/2025 |
2hr lab: construction of DFAs using RACSO |
|
8 |
07/10/2025 |
2hr theory: regular expressions and equivalence with NFAs/DFAs; Pumping Lemma; \{a^nb^n\mid n\in \mathbb N\} is not regular; proving non-regularity using closure properties |
(Sipser 2013, \S 1.3 and \S 1.4) |
9 |
09/10/2025 |
2hr lab: exercises on regular operations on RACSO |
|
10 |
14/10/2025 |
2hr problems: Student solutions of Homework 3 Homework 3 is due on this class (see the racó for the exercise assigned to you) |
|
11 |
16/10/2025 |
1ht theory: Context-free grammars (CFG); Ambiguity; 1hr lab: construction of CFGs using RACSO |
(Sipser 2013, \S 2.1) |
12 |
21/10/2025 |
2hr problems: Student solutions of Homework 4 Homework 4 is due on this class (see the racó for the exercise assigned to you) |
|
13 |
23/10/2025 |
2hr lab: construction of CFGs using RACSO; |
|
14 |
28/10/2025 |
1hr problems: Student solutions of Homework 4; 1hr theory: pumping lemma for CFL; \{a^nb^nc^n \mid n\in \mathbb N\} is not context-free |
(Sipser 2013, \S 2.3) |
15 |
03/11/2025 10:30 – 12:30 |
Midterm 1 |
|
16 |
06/11/2025 |
No class |
|
17 |
11/11/2025 |
2hr theory: Turing Machines, basic properties, Church-Turing Thesis, Gödel numbering, Universal TM |
(Sipser 2013, \S 3) |
18 |
13/11/2025 |
1 hr theory: Pushdown-Automata, formalization, equivalence betwen PDAs and CFGs; 1 hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2 and \S 2.4) |
19 |
18/11/2025 |
1hr problems: Student solutions of Homework 5 1hr theory: RE \cap coRE = R, projection theorem Homework 5 is due on this class (see the racó for the exercise assigned to you) |
(Sipser 2013, \S 4) |
20 |
21/11/2025 |
1hr theory: closure of CFL under intersection with regular languages and inverse homomorphism; 1hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2) |
21 |
25/11/2025 |
2hr problems: Student solutions of Homework 5 |
|
22 |
27/11/2025 |
1.30hr theory: K \in RE\setminus R, reductions 30min lab: construction of reductions from K using RACSO; |
(Sipser 2013, \S 5) |
23 |
02/12/2025 |
2hr problems: Student solutions of Homework 6 Homework 6 is due on this class (see the racó for the exercise assigned to you) |
|
24 |
04/12/2025 |
1hr theory: Rice Theorem 1hr lab: construction of reductions from K using RACSO; (Sipser 2013) proves Rice’s Theorem only in Problem 5.28. |
|
25 |
09/12/2025 |
1hr problems: Student solutions of Homework 6 1hr theory: recap of P, EXP, NP |
(Sipser 2013, \S 7.1, \S 7.2, \S 7.3, \S 7.4) |
26 |
11/12/2025 |
2hr lab: construction of reductions to CFGs using RACSO |
|
27 |
16/12/2025 |
2hr problems: Student solutions of Homework 7 Homework 7 is due on this class (see the racó for the exercise assigned to you) |
|
28 |
18/12/2025 |
2hr theory: NP-completeness, polynomial-time reductions, Cook-Levin Theorem |
(Sipser 2013, \S 7.4 and \S 7.5) (Hopcroft, Motwani, i Ullman 2007, \S 10) |
29 |
09/01/2026 08:00 – 11:00 |
Midterm 2 |
|
30 |
19/01/2026 11:30 – 14:30 |
Final Exam |
Dt 16–18 (A5203), Dc 15–17 (A5S111)
Professors: Antoni Lozano
| # | Data | Tema de la classe | Referències |
|---|---|---|---|
1 |
09/09/2025 |
30 min: Overview of the course, administrative part; 1.30hr theory: Math background; Strings and languages; Pigeonhole principle; Cantor Diagonalization |
(Sipser 2013, \S 0 and \S 4.2 The diagonalization method (pp. 202 until the end of Theorem 4.17) |
2 |
10/09/2025 |
1hr theory: Finite Automata (DFAs), formalization, some closure properties (union, intersection, the product construction); 1hr lab: examples of DFAs using RACSO |
(Sipser 2013, \S 1.1) |
3 |
16/09/2025 |
2hr problems: Student solutions of Homework 1 Homework 1 is due on this class (see the racó for the exercise assigned to you) |
|
4 |
17/09/2025 |
1hr theory: NFAs, determinization of NFAs; more closure properties; 1hr lab: construction of DFAs using RACSO; minimization of DFAs (Moore’s algorithm) In (Sipser 2013) the minimization of DFAs is only done in Problem 1.51, 1.52, and 7.42. |
(Sipser 2013, \S 1.2) |
5 |
23/09/2025 |
2hr problems: Student solutions of Homework 2 Homework 2 is due on this class (see the racó for the exercise assigned to you) |
|
6 |
30/09/2025 |
2hr problems: Student solutions of Homework 2 |
|
7 |
01/10/2025 |
2hr lab: construction of DFAs using RACSO |
|
8 |
07/10/2025 |
2hr theory: regular expressions and equivalence with NFAs/DFAs; Pumping Lemma; \{a^nb^n\mid n\in \mathbb N\} is not regular; proving non-regularity using closure properties |
(Sipser 2013, \S 1.3 and \S 1.4) |
9 |
08/10/2025 |
2hr lab: exercises on regular operations on RACSO |
|
10 |
14/10/2025 |
2hr problems: Student solutions of Homework 3 Homework 3 is due on this class (see the racó for the exercise assigned to you) |
|
11 |
15/10/2025 |
1ht theory: Context-free grammars (CFG); Ambiguity; 1hr lab: construction of CFGs using RACSO |
(Sipser 2013, \S 2.1) |
12 |
21/10/2025 |
2hr problems: Student solutions of Homework 4 Homework 4 is due on this class (see the racó for the exercise assigned to you) |
|
13 |
22/10/2025 |
2hr lab: construction of CFGs using RACSO; |
|
14 |
28/10/2025 |
1hr problems: Student solutions of Homework 4; 1hr theory: pumping lemma for CFL; \{a^nb^nc^n \mid n\in \mathbb N\} is not context-free |
(Sipser 2013, \S 2.3) |
15 |
29/10/2025 |
1hr theory: Pushdown-Automata, formalization, equivalence betwen PDAs and CFGs; 1hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2 and \S 2.4) |
16 |
03/11/2025 10:30 – 12:30 |
Midterm 1 |
|
17 |
11/11/2025 |
2hr theory: Turing Machines, basic properties, Church-Turing Thesis, Gödel numbering, Universal TM |
(Sipser 2013, \S 3) |
18 |
12/11/2025 |
1hr theory: closure of CFL under intersection with regular languages and inverse homomorphism; 1hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2) |
19 |
18/11/2025 |
1hr problems: Student solutions of Homework 5 1hr theory: RE \cap coRE = R, projection theorem Homework 5 is due on this class (see the racó for the exercise assigned to you) |
(Sipser 2013, \S 4) |
20 |
19/11/2025 |
1.30hr theory: K \in RE\setminus R, reductions 30min lab: construction of reductions from K using RACSO; |
(Sipser 2013, \S 5) |
21 |
25/11/2025 |
2hr problems: Student solutions of Homework 5 |
|
22 |
26/11/2025 |
1hr theory: Rice Theorem 1hr lab: construction of reductions from K using RACSO; (Sipser 2013) proves Rice’s Theorem only in Problem 5.28. |
|
23 |
02/12/2025 |
2hr problems: Student solutions of Homework 6 Homework 6 is due on this class (see the racó for the exercise assigned to you) |
|
24 |
03/12/2025 |
2hr lab: construction of reductions to CFGs using RACSO |
|
25 |
09/12/2025 |
1hr problems: Student solutions of Homework 6 1hr theory: recap of P, EXP, NP |
(Sipser 2013, \S 7.1, \S 7.2, \S 7.3, \S 7.4) |
26 |
10/12/2025 |
2hr theory: NP-completeness, polynomial-time reductions, Cook-Levin Theorem |
(Sipser 2013, \S 7.4 and \S 7.5) (Hopcroft, Motwani, i Ullman 2007, \S 10) |
27 |
16/12/2025 |
2hr problems: Student solutions of Homework 7 Homework 7 is due on this class (see the racó for the exercise assigned to you) |
|
28 |
17/12/2025 |
2hr theory: Time Hierarchy Theorem, P \neq EXP, TM with oracles |
(Sipser 2013, Theorem 9.10 and corollaries (pp. 369) and \S 9.2) |
29 |
09/01/2026 08:00 – 11:00 |
Midterm 2 |
|
30 |
19/01/2026 11:30 – 14:30 |
Final Exam |