| Setmana | Data | Tema de la classe |
|---|---|---|
| 1 | 10/02/2025 |
Overview of the course, administrative part. Introduction (math background, formal languages, proofs techniques). Solution of some exercises from Problem Set 0 (in groups in class). |
11/02/2025 |
Regular languages (DFAs, \lambda-NFAs, examples, cartesian product and some closure properties). Construction of DFAs using RACSO. |
|
| 2 | 17/02/2025 |
Proof techniques: contradiction, cases, induction, pigeonhole principle, diagonalization. Solution of some exercises from Problem Set 0 (in groups in class). |
18/02/2025 |
Determinization (subset set construction). Closure under concatenation and Kleene star. Construction of DFAs using RACSO. |
|
| 3 | 24/02/2025 |
Minimization of DFAs (Moore’s algorithm). Students presentations of exercises from Problem Set 1. Homework 1 is due on this class (see the racó for the exercise from Problem Set 1 assigned to you) |
25/02/2025 |
Regular expressions and equivalence with DFAs (Arden’s Lemma). Examples. Construction of DFAs using RACSO. |
|
| 4 | 03/03/2025 |
\{a^n b^n \mid n\in \mathbb N\} is not regular. Pumping Lemma for regular languages. Proofs of non regularity through closure properties. Students presentations of exercises from Problem Set 1 |
04/03/2025 |
Context-Free Grammars, parse trees, ambiguity. Closure properties of CFGs. Regulars are included in CFL. Construction of CFGs using RACSO. |
|
| 5 | 10/03/2025 |
Depuration of CFGs. Chomsky Normal Form. Students presentations of exercises from Problem Set 1. |
11/03/2025 |
Cocke-Younger-Kasami parsing algorithm. Construction of CFGs using RACSO. |
|
| 6 | 17/03/2025 |
\{a^n b^n c^n \mid n\in \mathbb N\} is not context-free. Pumping Lemma for CFL. Non context-freeness using closure operations. Students presentations of exercises from Problem Set 2. Homework 2 is due on this class (see the racó for the exercise from Problem Set 2 assigned to you) |
18/03/2025 |
Push-down automata. Equivalence with CFGs. Construction of CFGs using RACSO. |
|
| 7 | 24/03/2025 |
Closure of CFL under intersection with regular languages and inverse homomorphism. Students presentations of exercises from Problem Set 2. |
25/03/2025 |
Students presentations of exercises from Problem Set 2. Past exam exercsies on RACSO. |
|
| 08/04/2026 | Midterm 1 | |
| 8 | 14/04/2025 |
Turing Machines: basic properties, Church-Turing Thesis, Gödel numbering, Universal TM. |
15/04/2025 |
Definition of \mathbf{R} (decidable languages), \mathbf{RE} (semi-decidable languages), and \mathbf{coRE}. Undecidability of \mathtt{K} (\mathtt{K}\notin \mathbf{R}). Construction of PDAs using RACSO. |
|
| 9 | 21/04/2025 |
\mathbf{RE} \cap \mathbf{coRE} = \mathbf{R}. Projection theorem for \mathbf{RE} (and analogue for \mathbf{coRE}). Students presentations of exercises from Problem Set 3. Homework 3 is due on this class (see the racó for the exercise from Problem Set 3 assigned to you) |
22/04/2025 |
Many-one reductions. Proving undecidability through reductions. Examples. Construction of PDAs using RACSO. |
|
| 10 | 28/04/2025 |
Undecidable properties of CFGs (statements only). Arithmetic hierarchy. Students presentations of exercises from Problem Set 3. |
29/04/2025 |
Recap of \mathbf{P}, \mathbf{NP}, \mathbf{coNP}, \mathbf{EXP}. Construction of PDAs using RACSO. |
|
| 11 | 05/05/2025 |
\mathbf{NP}-completeness and polynomial-time reductions. Students presentations of exercises from Problem Set 3. |
06/05/2025 |
Cook-Levin Theorem. Reductions from \mathtt{SAT}. Construction of reductions from \mathtt{K} using RACSO. |
|
| 12 | 12/05/2025 |
More reductions from \mathtt{SAT}. Students presentations of exercises from Problem Set 4. Homework 4 is due on this class (see the racó for the exercise from Problem Set 4 assigned to you) |
13/05/2025 |
\mathbf{NP}-intermediate problems (factoring, graph isomorphism, discrete log). Ladner’s Theorem. Construction of reductions from \mathtt{K} using RACSO. |
|
| 13 | 19/05/2025 |
Time-constructible functions. Time-hierarchy theorem. \mathbf{P}\neq \mathbf{EXP}. Students presentations of exercises from Problem Set 4. |
20/05/2025 |
Classes \Sigma^P_2 and \Pi^P_2. The Polynomial Hierarchy (via quantifiers). Properties. Construction of reductions from \mathtt{K} using RACSO. |
|
| 14 | 26/05/2025 |
Definition of the PH via oracle machines. Turing reductions. Students presentations of exercises from Problem Set 4. |
27/05/2025 |
Relativization of \mathbf{P} = \mathbf{NP}: the limits of diagonalization. Past exam exercsies on RACSO. |
|
| 05/06/2026 | Midterm 2 | |
| 15/06/2026 | Final exam |
Calendari del curs 2025/2026 Q2
Cases, Rafel, i Lluís Màrquez. 2003. Llenguatges, gramàtiques i autòmats : curs bàsic. 2a ed. Edicions UPC.
Hopcroft, John E., Rajeev Motwani, i Jeffrey D. Ullman. 2007. Introduction to Automata Theory, Languages, and Computation. 3rd edition. Pearson Addison Wesley.
Sipser, Michael. 2013. Introduction to the theory of computation. 3rd edition. Cengage Learning.
Alerta
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.
In the table below, the notation \S refers to chapters, for instance (Sipser 2013, \S 2.3) refers to chapter 2 section 3 of (Sipser 2013)’s book.
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).