Course Schedule 2026/2027 Q1 (group 21)

Theory (T): Tue 18–20 (A6106)

Ilario Bonacina: Office: \Omega-223
Office hours: Wed 11:00 – 13:00 Book here

Problems/Laboratory (P/L): Thu 18–20 (A6102/A5S111)

Arnau Messegue Buisan: Office: \Omega-224
Office hours: send email

In theory classes (T), the lecturer introduces the basic theoretical foundations of each topic and solves some problems. Students deepen the theory during their personal study time using the resources indicated by the lecturer (books, videos and other complementary materials).

In problem solving classes (P) and laboratory classes (L), students explain their solutions to problems which have been assigned to them in advance. The teacher takes part of the explanation in order to correct mistakes or make improvements. Also, the teacher takes notes about students presentations in order to take them into account in the final evaluation of the subject. In laboratory classes students solve problems in front of the computer that are checked automatically.

All announcements will be done through the racó.
For administrative questions, contact the coordinators of the course (Ilario Bonacina, Antoni Lozano) .

Date		Topic
08 Sept	T	Overview of the course, administrative part. Introduction: math background, formal languages, proofs techniques (contradiction, cases, induction, pigeonhole principle). Solution of some exercises from Problem Set 0 (in groups in class).
10 Sept	P	Solution of some exercises from Problem Set 0 (in groups in class).
15 Sept	T	Regular languages (DFAs, \lambda-NFAs, examples, cartesian product and some closure properties). Determinization (subset set construction). Solution of some exercises from Problem Set 1 (in groups in class).
17 Sept	L	Construction of DFAs using RACSO. Students presentations of exercises from RACSO.
22 Sept	T	Minimization of DFAs (Moore’s algorithm). \{a^n b^n \mid n\in \mathbb N\} is not regular and proofs of non-regularity via distinguishing extensions. Solution of some exercises from Problem Set 1 (in groups in class).
24 Sept		No class
29 Sept	T	Regular expressions and equivalence with DFAs (Arden’s Lemma). Examples. Pumping Lemma for regular languages. Non regularity using closure properties. Solution of some exercises from Problem Set 1 (in groups in class).
01 Oct	P	Students presentations of exercises from Problem Set 1.
06 Oct	T	Context-Free Grammars, parse trees, ambiguity. Closure properties of CFGs. Regulars are included in CFL. Solution of some exercises from Problem Set 2 (in groups in class).
08 Oct	L	Construction of DFA and CFGs using RACSO. Students presentations of exercises from RACSO.
13 Oct	T	Depuration of CFGs and Chomsky Normal Form. Cocke-Younger-Kasami parsing algorithm. Solution of some exercises from Problem Set 2 (in groups in class).
15 Oct	P	Students presentations of exercises from Problem Set 2.
20 Oct	T	\{a^n b^n c^n \mid n\in \mathbb N\} is not context-free. Pumping Lemma for CFL. Non context-freeness using closure properties. Solution of some exercises from Problem Set 2 (in groups in class).
22 Oct	L	Construction of CFGs using RACSO. Students presentations of exercises from RACSO.
27 Oct	T	Push-down automata. Equivalence with CFGs. Deterministic CFLs. Turing Machines: one tape, multi tape, nondeterminism, basic properties. Equivalence with high level algorithms and Church-Turing Thesis.
29 Oct		No class
02 Nov		Partial Exam 1 (10:30-13:30)
03 Nov		No class
05 Nov	L	Construction of PDAs using RACSO. Students presentations of exercises from RACSO.
10 Nov	T	Gödel numbering, Universal TM. Definition of \mathbf{R} (decidable languages), \mathbf{RE} (semi-decidable languages), and \mathbf{coRE}. Diagonalization and undecidability of \mathtt{K} (\mathtt{K}\notin \mathbf{R}). Solution of some exercises from Problem Set 3 (in groups in class).
12 Nov	P	Students presentations of exercises from Problem Set 3.
17 Nov	T	\mathbf{RE} \cap \mathbf{coRE} = \mathbf{R}. Projection theorem for \mathbf{RE} (and analogue for \mathbf{coRE}). Arithmetic hierarchy. Many-one reductions. Proving undecidability through reductions. Undecidable properties of CFGs (statements only). Examples. Solution of some exercises from Problem Set 3 (in groups in class).
19 Nov	L	Construction of reductions from \mathtt{K} using RACSO. Students presentations of exercises from RACSO.
24 Nov	T	Recap of \mathbf{P}, \mathbf{NP}, \mathbf{coNP}, \mathbf{EXP}. Time-constructible functions. Universal TM (revised). Solution of some exercises from Problem Set 4 (in groups in class).
26 Nov	P	Students presentations of exercises from Problem Set 3.
01 Dec	T	\mathbf{NP}-completeness (Cook-Levin Theorem) and polynomial-time reductions. Reductions from \mathtt{SAT}. Examples. Solution of some exercises from Problem Set 4 (in groups in class).
03 Dec	L	Construction of PDAs and reductions from K using RACSO. Students presentations of exercises from RACSO.
08 Dec		No class
10 Dec	P	Students presentations of exercises from Problem Set 4.
15 Dec	T	\mathbf{NP}-intermediate problems (factoring, graph isomorphism, discrete log). Ladner’s Theorem. Time-hierarchy theorem. \mathbf{P}\neq \mathbf{EXP}. Solution of some exercises from Problem Set 4 (in groups in class).
17 Dec	P	Students presentations of exercises from Problem Set 4.
23 Dec		Partial Exam 2 (11:00–14:00)
18 Jan		Final Exam (08:00–11:00)